第二十屆全國青少年信息學奧林匹克競賽初賽提高組C語言試題一、單項選擇題（每題1.5分，共22.5分）。1. 以下哪個是面向?qū)ο蟮母呒壵Z言( ). A. 匯編語言 B. C+ C. FORTRAN D. Basic2. 1TB代表的字節(jié)數(shù)量是( ). A. 2的10次方 B. 2的20次方 C. 2的30次方 D. 2的40次方3. 二進制數(shù)00100100和00010101的和是( ). A. 00101000 B. 001010100 C. 01000101 D. 001110014. TCP協(xié)議屬于哪一層協(xié)議( ). A. 應(yīng)用層 B. 傳輸層 C. 網(wǎng)絡(luò)層 D. 數(shù)據(jù)鏈路層5. 下列幾個32位IP地址中，書寫錯誤的是( ). A. 162.105.128.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.16. 在無向圖中，所有定點的度數(shù)之和是邊數(shù)的( )倍. A. 0.5 B. 1 C. 2 D. 47. 對長度位n的有序單鏈表，若檢索每個元素的概率相等，則順序檢索到表中任一元素的平均檢索長度為( ). A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/48. 編譯器的主要功能是( ). A. 將一種高級語言翻譯成另一種高級語言 B. 將源程序翻譯成指令 C. 將低級語言翻譯成高級語言 D. 將源程序重新組合9. 二進制數(shù)111.101所對應(yīng)的十進制數(shù)是( ). 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. 有以下結(jié)構(gòu)體說明和變量定義，如圖所示，指針p、q、r分別指向一個鏈表中的三個續(xù)結(jié)點。 struct node data next data next data next int data; struct node *next; p q r *p,*q,*r;現(xiàn)要將q和r所指結(jié)點的先后位置交換，同時要保持鏈表的連續(xù)，以下程序段中錯誤的是( ). 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 = r-next; p-next = r;12. 同時查找2n 個數(shù)中的最大值和最小值，最少比較次數(shù)為( ). A. 3(n-2)/2 B. 4n-2 C. 3n-2 D. 2n-213. 設(shè)G是有6個結(jié)點的完全圖，要得到一顆生成樹，需要從G中刪去( )條邊. A. 6 B. 9 C. 10 D. 1514. 以下時間復雜度不是O(n2)的排序方法是( ). A. 插入排序 B. 歸并排序 C. 冒泡排序 D. 選擇排序15. 以下程序?qū)崿F(xiàn)了找第二小元素的算法。輸入時n個不等的數(shù)構(gòu)成的數(shù)組S，輸出S中第二小的數(shù)SecondMin。在最壞的情況下，該算法需要做( )次比較。 if (S1 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. (BCD)DA B. (- AB)C)B C. (AB)(CD-A) D. A(D-C)B2. 下列( )軟件屬于操作系統(tǒng)軟件。 A. Microsoft Word B. Windows XP C. Android D. Mac OS X E. Oracle3. 在NOI比賽中，對于程序設(shè)計題，選手提交的答案不得包含下列哪些內(nèi)容( ). A. 試圖訪問網(wǎng)絡(luò) B. 打開或創(chuàng)建題目規(guī)定的輸入/輸出文件之外的其他文件 C. 運行其他程序 D. 改變文件系統(tǒng)的訪問權(quán)限 E. 讀寫文件系統(tǒng)的管理信息4. 以下哪些結(jié)構(gòu)可以用來存儲圖( ). A. 鄰接矩陣 B. 棧 C. 鄰接表 D. 二叉樹5. 下列各無符號十進制整數(shù)中，能用八位二進制表示的數(shù)有( ). A. 296 B. 133 C. 256 D. 199三、問題求解。1. 有數(shù)字1,1,2,4,8,8所組成的不同的四位數(shù)的個數(shù)是_.2. 如圖所示，圖中每條邊上的數(shù)字表示該邊的長度，則從A到E的最短距離是_.四、閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共32分)。1. #include int main() int a,b,I,tot,c1,c2; scanf(“%d%d”, &a, &d); tot = 0; for (i=a; i=b; i+) c1=i/10; c2=i%10; if (c1+c2)%3 =0) tot+;Printf(“%dn,tot);Return 0;輸入：7 31輸出：_2. #include 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,&m);printf(“%dn”, fum(m,1,n);return 0;輸入： 6 3輸出：_3. #include #include const int SIZE=100;const int LENGTH=25;/ strcmp(a,b) 0:a的字典序大于bint main() char dictSIZELENGTH+1; int rankSIZE; int indSIZE; int i,j,n,tmp;scanf(“%d”,&n);for (i=1;i=n;i+)rank i=iindi=i;scanf(“%s”, dicti);for(i=1;in;i+)for(j=1;j0)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 0;輸入：7aaaababbbaaaaaacccaa輸出：_4. #niclude const int SIZE=100;int aliveSIZE;int n;int next(int num)donum+;if(numn)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;j=m;j+)num=next(num);printf(“%d”,num);alivenum=0;if(in)num=next(num);printf(n);return 0;輸入： 11 3輸出：_ 五、 完善程序1（雙棧模擬數(shù)組）只使用兩個棧結(jié)構(gòu)stack1和stack2，模擬對數(shù)組的隨機讀取。作為棧結(jié)構(gòu)，stack1和stack2只能訪問棧頂（最后一個有效元素）。棧頂指針top1和top2均指向棧頂元素的下一個位置。 輸入第一行包含的兩個整數(shù)，分別是數(shù)組長度n和訪問次數(shù)m，中間用單個空格隔開。第二行包含n個整數(shù)，一次歌出數(shù)組各項（數(shù)組下標從0到a-1）。第三行包含m個整數(shù)，需要訪問的數(shù)組下標。對于每次訪問，輸出對應(yīng)的數(shù)組元素。#include consr int SIZE=100;int stack1SIZE,stack2SIZE;int top1,top2;int n,m,i,j;void clearStack()int I;for(i=top1;iSIZE;i+)stacki=0;for(i=top2;iSIZE;i+)stacki=0;int main()scanf(%d,%d”,&n,&m);for(i=0in;i+)scanf(“%d”,&stack1i);top1=_（1）_;top2=_（2）_;for(j=0jm;j+)scanf(“%d”,&i);while(itop1-1)top2- -; (4) ;top1+;clearstack();printf(“%dn”,stack1 (5) );return 0;2. (最大矩陣和)給出M行N列的整數(shù)矩陣，就最大的子矩陣和（子矩陣不能為空）。 輸入第一行包含兩個整數(shù)M和N,即矩陣的行數(shù)和列數(shù)。之后M行，每行N個整數(shù)，描述整個矩陣。程序最終輸出最大的子矩陣和。（第一空2分，其余3分，共14分）#include const int SIZE=100;int matrixSIZE+1SIZE+1;int rowsumSIZE+1SIZE+1; /rowsumij記錄第i行前j個數(shù)的和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=matrix (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;ians) ans=area; if(area0) area=0; printf(“%dn”,ans); return 0;二、問題求解（共2題，每題4分，共計8分；每題全部答對得4分）1. _ 102 _ 2. _ 15 _三、閱讀程序?qū)懡Y(jié)果（共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 _四、完善程序（共2題，每題10分，共計20