1、精選第二十屆全國青少年信息學奧林匹克競賽初賽 提高組 C 語言試題一、單項選擇題(每題 1.5 分，共 22.5 分)。1. 以下哪個是面向對象的高級語言 ( ).A. 匯編語言 B. C+ C. FORTRAN D. Basic2. 1TB代表的字節數量是().A. 2的 10次方 B. 2的 20次方 C. 2的 30次方 D. 2的 40次方3. 二進制數 00100100 和 00010101 的和是 ( ).A. 00101000 B. 001010100 C. 01000101 D. 001110014. TCP協議屬于哪一層協議().A. 應用層 B. 傳輸層 C. 網絡層 D.

2、 數據鏈路層5. 下列幾個 32 位 IP 地址中，書寫錯誤的是 ( ).A. 162.105.128.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.16. 在無向圖中，所有定點的度數之和是邊數的 ( )倍 .A. 0.5 B. 1 C. 2 D. 47. 對長度位 n 的有序單鏈表，若檢索每個元素的概率相等，則順序檢索到表中任一元素的 平均檢索長度為 ( ).A. n/2 B. (n+1)/2 C. (n-1 )/2D. n/48. 編譯器的主要功能是 ().A. 將一種高級語言翻譯成另一種高級語言B. 將源程序翻譯成指令C. 將低級語言翻譯成高級

3、語言D. 將源程序重新組合9. 二進制數 111.101 所對應的十進制數是 ( ).A. 5.625 B. 5.5 C. 6.125 D. 7.62510. 若有變量 int a, float x, y, 且 a=7, x=2.5, y=4.7, 則表達式 x+a%3*(int)(x+y)%2/4 的值大約是().A. 2.500000 B. 2.750000 C. 3.500000 D. 0.00000011. 有以下結構體說明和變量定義，如圖所示，指針p、q、r 分別指向一個鏈表中的三個續結點。struct node data next data next data next int d

4、ata;struct node *next;f pf qf r *p,*q,*r;現要將 q 和 r 所指結點的先后位置交換， 同時要保持鏈表的連續， 以下程序段中錯誤的是 ().A. q->next = r->next; p-> next = r; r->next = q;B. p->next = r; q->next = r->next; r->next = q;C. q->next = r->next; r->next = q; p->next = r;D. r->next = q; q->next =

5、r->next; p->next = r;12. 同時查找 2n 個數中的最大值和最小值，最少比較次數為 ( ).A. 3(n-2)/2 B. 4n-2 C. 3n-2 D. 2n-2G中刪去()條邊.13. 設 G 是有 6 個結點的完全圖，要得到一顆生成樹，需要從A. 6 B. 9 C. 10 D. 1514. 以下時間復雜度不是0(n2)的排序方法是().A. 插入排序 B. 歸并排序 C. 冒泡排序 D. 選擇排序15. 以下程序實現了找第二小元素的算法。輸入時n個不等的數構成的數組S,輸出S中第二小的數SecondMin。在最壞的情況下，該算法需要做()次比較。if (S

6、1 < S2) FirstMin = S1;SecondMin = S2; else FirstMin = S2;SecondMin = S1;for (i = 3; i <=n; i+)if (S1 < SecondMin)if (S1 < FirstMin)SecondMin = FirstMin;FirstMin = S1; else SecondMin = S1;A. 2n B. n-1 C. 2n-3 D. 2n-2二、不定項選擇題(每題1.5分，共 7.5分)。1. 若邏輯變量A、C為真，B、D為假，以下邏輯運算表達式真的有().A. (BV CV D)V

7、DA AB. (- AA B)V C)A BC. (AA B)V (CA DV -A)D. AA (DV -C)A B2. 下列 ()軟件屬于操作系統軟件。A. Microsoft WordB. Windows XPC. AndroidD. Mac 0S XE. 0racle3. 在 N0I 比賽中，對于程序設計題，選手提交的答案不得包含下列哪些內容().A. 試圖訪問網絡B. 打開或創建題目規定的輸入 /輸出文件之外的其他文件C. 運行其他程序D. 改變文件系統的訪問權限E. 讀寫文件系統的管理信息4. 以下哪些結構可以用來存儲圖 ().A. 鄰接矩陣 B. 棧 C. 鄰接表 D. 二叉樹5

8、. 下列各無符號十進制整數中，能用八位二進制表示的數有 ().A. 296 B. 133 C. 256 D. 199三、問題求解。1. 有數字 1,1,2,4,8,8 所組成的不同的四位數的個數是 .2. 如圖所示，圖中每條邊上的數字表示該邊的長度，則從A到E的最短距離是 . 四、閱讀程序寫結果 (共 4 題，每題 8 分，共 32 分 )。 1. #include <stdio.h>int main() int a,b,I,tot,c1,c2; scanf( “ %d%d” , &a, &d);tot = 0;for (i=a; i<=b; i+) c1=i

9、/10; c2=i%10; if (c1+c2)%3 =0)tot+;Printf( “ %dn",tot);Return 0;輸入： 7 31 輸出： 2. #include <stdio.h>Int fun(int n, int minNum, int maxNum) int tot, i; if (n=0) retuen 1; tot=0;for(i=minNum; i<=maxNum; i+) tot+=fun(n -1, i=1, maxNum);return tot;int mian()int n, m;Scanf( “ %d%d” , &n,&

10、amp;m); printf( “ %dn ” , fum(m,1,n);return 0; 輸入： 6 3 輸出： #include <stdio.h> #include <string.h> const int SIZE=100;const int LENGTH=25;/ strcmp(a,b) <0:a 的字典序小于 b/ strcmp(a,b) =1:a 和 b 一樣/ strcmp(a,b) >0:a 的字典序大于 bint main()char dictSIZELENGTH+1;int rankSIZE; int indSIZE; int i,j

11、,n,tmp; scanf( “ %d” ,&n); for (i=1;i<=n;i+) rank i=i indi=i; scanf( “ %s” , dicti); for(i=1;i<n;i+) for(j=1;j<=n -i;j+)if(strcmp(dictindj,dictindj+1)>0) tmp=indj;indj=indj+1; indj+1=tmp; for(i=1;i<=n;i+) rankindi=i; for(i=1:i<=n;i+) ptintf(%d ” ,ranki); printf( “ n ” ); return

12、 0; 輸入： 7 aaa aba bbb aaa aaa ccc aa 輸出： #niclude <stdio.h> const int SIZE=100; int aliveSIZE; int n;int next(int num) do num+; if(num>n) num=1;while (alivenum=0);return num;int main()int m,i,j,num;scanf( “ %d%d” ,&n,&m);for(i=1;i<=n;i+)alivei=1;num=1;for(i=1;i<=n;j+) for(j+1;

13、j<=m;j+) num=next(num); printf(“ %d” ,num);alivenum=0;if(i<n) num=next(num);printf(n);return 0;輸入： 11 3輸出： 五、完善程序1.(雙棧模擬數組)只使用兩個棧結構 stackl和stack2，模擬對數組的隨機讀取。作為棧結構， stack1 和 stack2 只能訪問棧頂(最后一個有效元素) 。棧頂指針 top1 和 top2 均指向 棧頂元素的下一個位置。輸入第一行包含的兩個整數，分別是數組長度n和訪問次數m,中間用單個空格隔開。第二行包含 n 個整數，一次歌出數組各項(數組下標從

14、 0 到 a-1 )。第三行包含 m 個整數， 需要訪問的數組下標。對于每次訪問,輸出對應的數組元素。#include <stdio.h> consr int SIZE=100;int stack1SIZE,stack2SIZE;int top1,top2;int n,m,i,j;void clearStack()int I;for(i=top1;i<SIZE;i+) stacki=0;for(i=top2;i<SIZE;i+)stacki=0;int main()scanf(%d,%d ” ,&n,&m);for(i=0i<n;i+)scanf(

15、 “ %d” ,&stack1i);top1=(1);top2= (2);for(j=0j<m;j+) scanf( “ %d” ,&i); while(i<top1 -1)top1- -;(3) ;top2+;while(i>top1 -1)top2- -;(4) ;top1+; clearstack();printf( “ %dn” ,stack1(5) );return 0;(最大矩陣和 )給出 M 行 N 列的整數矩陣，就最大的子矩陣和(子矩陣不能為空) 。輸入第一行包含兩個整數M和N,即矩陣的行數和列數。之后M行，每行N個整數，描述整個矩陣。程序最終

16、輸出最大的子矩陣和。 (第一空 2 分，其余 3 分，共 14分) #include <stdio.h>const int SIZE=100;int matrixSIZE+1SIZE+1;int rowsumSIZE+1SIZE+1; /rowsumij 記錄第 i 行前 j 個數的和int m,n,i,j,first,last,area,ans;int main()scanf( “ %d %d” ,&m,&n);for(i=1;i<=m;i+) for(j=1;j<=n;j+) scanf( “ %d” ,&matrixij);ans=matr

17、ix (1) ; for(i=1;i<=m;i+)(2) ;for(i=1;i<=m;i+) for(j=1;j<=n;j+) rowsumij= (3) ;for(first=1;first<=n;first+) for(last=first;last<=n;last+)(4) ;for(i=1;i<=m;i+)area+= （5） ;if（area>ans）ans=area;if（area<0）area=0;printf（ “ %dn ” ,ans）;return 0;二、問題求解（共 2 題，每題 4 分，共計 8 分；每題全部答對得 4 分） 1. 102 2. 15 三、閱讀程序寫結果（共 4 題，每題 8 分，共計 32 分）1. _ 8 _ 2. 20 3. _2 5 6 3 4 7 1 4. _ 3 6 9 1 5 10 4 11 8 2 7