第二十屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽初賽提高組C語言試題(附答案).doc

第二十屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽初賽提高組C語言試題一、單項(xiàng)選擇題（每題1.5分，共22.5分）。1. 以下哪個(gè)是面向?qū)ο蟮母呒?jí)語言( ). A. 匯編語言 B. C+ C. FORTRAN D. Basic2. 1TB代表的字節(jié)數(shù)量是( ). A. 2的10次方 B. 2的20次方 C. 2的30次方 D. 2的40次方3. 二進(jìn)制數(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. 下列幾個(gè)32位IP地址中，書寫錯(cuò)誤的是( ). A. 162.105.128.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.16. 在無向圖中，所有定點(diǎn)的度數(shù)之和是邊數(shù)的( )倍. A. 0.5 B. 1 C. 2 D. 47. 對(duì)長(zhǎng)度位n的有序單鏈表，若檢索每個(gè)元素的概率相等，則順序檢索到表中任一元素的平均檢索長(zhǎng)度為( ). A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/48. 編譯器的主要功能是( ). A. 將一種高級(jí)語言翻譯成另一種高級(jí)語言 B. 將源程序翻譯成指令 C. 將低級(jí)語言翻譯成高級(jí)語言 D. 將源程序重新組合9. 二進(jìn)制數(shù)111.101所對(duì)應(yīng)的十進(jìn)制數(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, 則表達(dá)式 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分別指向一個(gè)鏈表中的三個(gè)續(xù)結(jié)點(diǎn)。 struct node data next data next data next int data; struct node *next; p q r *p,*q,*r;現(xiàn)要將q和r所指結(jié)點(diǎn)的先后位置交換，同時(shí)要保持鏈表的連續(xù)，以下程序段中錯(cuò)誤的是( ). 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. 同時(shí)查找2n 個(gè)數(shù)中的最大值和最小值，最少比較次數(shù)為( ). A. 3(n-2)/2 B. 4n-2 C. 3n-2 D. 2n-213. 設(shè)G是有6個(gè)結(jié)點(diǎn)的完全圖，要得到一顆生成樹，需要從G中刪去( )條邊. A. 6 B. 9 C. 10 D. 1514. 以下時(shí)間復(fù)雜度不是O(n2)的排序方法是( ). A. 插入排序 B. 歸并排序 C. 冒泡排序 D. 選擇排序15. 以下程序?qū)崿F(xiàn)了找第二小元素的算法。輸入時(shí)n個(gè)不等的數(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二、不定項(xiàng)選擇題（每題1.5分，共7.5分）。1. 若邏輯變量A、C為真，B、D為假，以下邏輯運(yùn)算表達(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比賽中，對(duì)于程序設(shè)計(jì)題，選手提交的答案不得包含下列哪些內(nèi)容( ). A. 試圖訪問網(wǎng)絡(luò) B. 打開或創(chuàng)建題目規(guī)定的輸入/輸出文件之外的其他文件 C. 運(yùn)行其他程序 D. 改變文件系統(tǒng)的訪問權(quán)限 E. 讀寫文件系統(tǒng)的管理信息4. 以下哪些結(jié)構(gòu)可以用來存儲(chǔ)圖( ). A. 鄰接矩陣 B. 棧 C. 鄰接表 D. 二叉樹5. 下列各無符號(hào)十進(jìn)制整數(shù)中，能用八位二進(jìn)制表示的數(shù)有( ). A. 296 B. 133 C. 256 D. 199三、問題求解。1. 有數(shù)字1,1,2,4,8,8所組成的不同的四位數(shù)的個(gè)數(shù)是_.2. 如圖所示，圖中每條邊上的數(shù)字表示該邊的長(zhǎng)度，則從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ù)組）只使用兩個(gè)棧結(jié)構(gòu)stack1和stack2，模擬對(duì)數(shù)組的隨機(jī)讀取。作為棧結(jié)構(gòu)，stack1和stack2只能訪問棧頂（最后一個(gè)有效元素）。棧頂指針top1和top2均指向棧頂元素的下一個(gè)位置。 輸入第一行包含的兩個(gè)整數(shù)，分別是數(shù)組長(zhǎng)度n和訪問次數(shù)m，中間用單個(gè)空格隔開。第二行包含n個(gè)整數(shù)，一次歌出數(shù)組各項(xiàng)（數(shù)組下標(biāo)從0到a-1）。第三行包含m個(gè)整數(shù)，需要訪問的數(shù)組下標(biāo)。對(duì)于每次訪問，輸出對(duì)應(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ù)矩陣，就最大的子矩陣和（子矩陣不能為空）。 輸入第一行包含兩個(gè)整數(shù)M和N,即矩陣的行數(shù)和列數(shù)。之后M行，每行N個(gè)整數(shù)，描述整個(gè)矩陣。程序最終輸出最大的子矩陣和。（第一空2分，其余3分，共14分）#include const int SIZE=100;int matrixSIZE+1SIZE+1;int rowsumSIZE+1SIZE+1; /rowsumij記錄第i行前j個(gè)數(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分，共計(jì)8分；每題全部答對(duì)得4分）1. _ 102 _ 2. _ 15 _三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)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分，共計(jì)20