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

1、第二十屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽初賽提高組C語(yǔ)言試題一、單項(xiàng)選擇題（每題1.5分，共22.5分）。1. 以下哪個(gè)是面向?qū)ο蟮母呒?jí)語(yǔ)言（）.A. 匯編語(yǔ)言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地址中，書(shū)

2、寫錯(cuò)誤的是（）.A. 162.105.128.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.16. 在無(wú)向圖中，所有定點(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）/2C. （n-1）/2 D. n/48. 編譯器的主要功能是（）.A. 將一種高級(jí)語(yǔ)言翻譯成另一種高級(jí)語(yǔ)言B. 將源程序翻譯成指令C. 將低級(jí)語(yǔ)言翻譯成高級(jí)語(yǔ)言D. 將源程序重新組合9. 二進(jìn)制數(shù)111.101所對(duì)應(yīng)的十進(jìn)制數(shù)是（）

3、.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)體說(shuō)明和變量定義，如圖所示，指針p、q、r分別指向一個(gè)鏈表中的三個(gè)續(xù)結(jié)點(diǎn)。struct node data next data n extdata n extint data; 一 | struct node *next;f pf qf r *p,*q,*

4、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é)

5、點(diǎn)的完全圖，要得到一顆生成樹(shù)，需要從G中刪去()條邊.A. 6 B. 9 C. 10 D. 1514. 以下時(shí)間復(fù)雜度不是 0(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 SecondMi

6、n) 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. (B V C V D) V D A AB. (- A A B) V C) A BC. (A A B) V (C A D V -A)D. A A (D V -C) A B2. 下列 ()軟件屬于操作系統(tǒng)軟件。A. Microsoft WordB. Wind

7、ows XPC. AndroidD. Mac 0S XE. 0racle3. 在 N0I 比賽中，對(duì)于程序設(shè)計(jì)題，選手提交的答案不得包含下列哪些內(nèi)容().A. 試圖訪問(wèn)網(wǎng)絡(luò)B. 打開(kāi)或創(chuàng)建題目規(guī)定的輸入 /輸出文件之外的其他文件C. 運(yùn)行其他程序D. 改變文件系統(tǒng)的訪問(wèn)權(quán)限E. 讀寫文件系統(tǒng)的管理信息4. 以下哪些結(jié)構(gòu)可以用來(lái)存儲(chǔ)圖（）.A.鄰接矩陣B.棧 C.鄰接表 D.二叉樹(shù)5. 下列各無(wú)符號(hào)十進(jìn)制整數(shù)中，能用八位二進(jìn)制表示的數(shù)有（）.A. 296 B. 133 C. 256 D. 199三、問(wèn)題求解。1. 有數(shù)字1,124,8,8所組成的不同的四位數(shù)的個(gè)數(shù)是 .2. 如圖所示，圖中每條邊

8、上的數(shù)字表示該邊的長(zhǎng)度，則從A到E的最短距離是 四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共32分）1. #i nclude int mai n() int a,b,l,tot,c1,c2;scanf( %d%d ”&a, &d); tot = 0;for (i=a; i=b; i+)c仁 i/10; c2=i%10;if (c1+c2)%3 =0) tot+;Printf( %dn,tot);Retur n 0;輸入：7312. #include maxNum)Int fun(int n, int minNum, int int tot, i;if (n=0)retuen 1;tot=0;for

9、(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 的字典序大于 int main()char dictSIZELENGTH+1; int rankSIZE;int indSIZE;int

10、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

11、 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è)棧

12、結(jié)構(gòu) stackl和stack2，模擬對(duì)數(shù)組的隨機(jī)讀取。作為棧結(jié)構(gòu)， stack1 和 stack2 只能訪問(wèn)棧頂 （最后一個(gè)有效元素） 。棧頂指針 top1 和 top2 均指向棧 頂元素的下一個(gè)位置。輸入第一行包含的兩個(gè)整數(shù)，分別是數(shù)組長(zhǎng)度n和訪問(wèn)次數(shù)m,中間用單個(gè)空格隔開(kāi)。第二行包含n個(gè)整數(shù)，一次歌出數(shù)組各項(xiàng)（數(shù)組下標(biāo)從0到a-1）。第三行包含 m個(gè)整數(shù),需要訪問(wèn)的數(shù)組下標(biāo)。對(duì)于每次訪問(wèn)，輸出對(duì)應(yīng)的數(shù)組元素。#i nclude consr int SIZE=100;int stack1SIZE,stack2SIZE;int top1,top2;int n,m,i,j;void clear

13、Stack()int I;for(i=top1;iSIZE;i+)stacki=0;for(i=top2;iSIZE;i+)stacki=0;int mai n()sca nf(%d,%d ”&n,& m);for(i=0i n; 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ù)矩陣，就最大的子矩陣和（子矩陣不能

14、為空）。輸入第一行包含兩個(gè)整數(shù) M和N,即矩陣的行數(shù)和列數(shù)。之后 M行，每行N個(gè)整數(shù)，描述 整個(gè)矩陣。程序最終輸出最大的子矩陣和。（第一空2分，其余3分，共14分）#i nclude 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,a ns;int mai n()scanf( %d %d ，&m,&n);for(i=1;i=m;i+)for(j=1;j=n ;j+)scanf( %d”,&matrixij);a

15、n s=matrix(1);for(i=1;i=m;i+)(21.;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;ia ns) an s=area;if(area0) area=0;printf( %dn ”,a ns);return 0;、問(wèn)題求解（共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