第24屆2009年中小學(xué)生計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽小學(xué)組含答案

1、2009年寧波市第24屆中小學(xué)生計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽小學(xué)組初賽試題（說(shuō)明：答案請(qǐng)寫(xiě)在答題卷上。考試時(shí)間120分鐘，滿(mǎn)分100分）一、選擇題（每題有且僅有一個(gè)正確答案，選對(duì)得1.5分，選錯(cuò)、不選或多選均不得分）1、若已知一個(gè)棧的入棧順序是1，2，3，n，其輸出序列為P1，P2，P3，Pn，若P1是n，則Pi是( )A)i B)n-1 C)n-i+1 D)不確定2、滿(mǎn)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（ ）。A. N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 13、二叉樹(shù)T，已知其前序遍歷序列為1 2 4 3 5 7 6，中序遍歷序列為4 2 1 5 7 3

2、 6，則其后序遍歷序列為（ ）。A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 14、完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為11，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（ ）。A. 4 B.3 C.5 D. 2 E. 65、布爾型(boolean)和字符型(char)變量所占用的存儲(chǔ)空間大小的關(guān)系是（A）布爾型大 （B）字符型大 （C）一樣大 （D）因操作系統(tǒng)而異6、用八位二進(jìn)制可以表示的最大十進(jìn)制數(shù)是：（A）99999999 （B）11111111 （C）255 （D）2567、有一個(gè)10行10列的對(duì)稱(chēng)矩陣，采

3、用壓縮存儲(chǔ)方式來(lái)存儲(chǔ)該矩陣的上三角元素（行優(yōu)先次序），第1行第1列的存儲(chǔ)地址為s，每個(gè)元素占用2個(gè)存儲(chǔ)空間，則第8行第8列元素的首地址為： （A）s+100 （B）s+98 （C）s+72 （D）s+708、已知一棵二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為100，則有二個(gè)子女的結(jié)點(diǎn)數(shù)為：（A） 101 （B） 100 （C） 99 （D） 不能確定9、已知一棵二叉樹(shù)的前序遍歷為JFDECBHAIG，中序遍歷結(jié)果為DFEJAHBICG，則這棵二叉樹(shù)的深度為： （A） 6 （B）5 （C）4 （D）310、在Pascal語(yǔ)言中，表達(dá)式 （23 or 2 xor 5）的值是（ ）。A18 B1 C23 D3211、將數(shù)

4、組 1, 2, 4, 3, 5, 6, 7, 8 中的元素用插入排序的方法按從大到小的順序排列，需要比較的次數(shù)是：（A）7（B）27（C）28（D）6412、算式(2009)16-(2008)10+(2007)8的結(jié)果是：（A）(16170)8 （B）(7234)10 （C）(1C36)16 （D）(1110000111000)213、計(jì)算機(jī)內(nèi)部使用的數(shù)是：（A）二進(jìn)制數(shù)      （B） 八進(jìn)制數(shù) （C） 十進(jìn)制數(shù)     （D） 十六進(jìn)制數(shù)14、當(dāng)n大于100萬(wàn)時(shí),下列程序段哪個(gè)運(yùn)行最快（D）k:=1;j:=n

5、;x:=a1;while k<j do begin while (k<j)and(aj>x)do dec(j); if k<j then begin ak:=aj;inc(k);end; while (k<j)and(ak<x)do inc(k); if k<j then begin aj:=ak;dec(j);end;end;（C）sum:=0;k:=1;while k<=n do begin for j:= 1 to n do sum:=sum+1; k:=k*2;end;（B）sum:=0;k:=1;while k<=n do beg

6、in for j:= 1 to k do sum:=sum+1; k:=k+2;end;（A）max:=0;for k:=1 to n-1 do for j:=k+1 to n do if max<abs(ak-aj) then max:=abs(ak-aj) 15、當(dāng)原始待排序數(shù)據(jù)為從小到大排列時(shí)，運(yùn)行時(shí)間比原始數(shù)據(jù)為亂序時(shí)快的算法是： （A）選擇排序 （B）歸并排序 （C）插入排序 （D）快速排序 16、關(guān)于算法的下列敘述不正確的是：（A）算法的每一步必須沒(méi)有歧義，不能有半點(diǎn)含糊（B）算法必須有輸入（C）同一問(wèn)題可能存在多種不同的算法（D）同一算法可以用多種不同的形式來(lái)描述17、FO

7、R語(yǔ)句中的循環(huán)變量，其類(lèi)型必須是：（A）整型 （B）實(shí)型 （C）自定義類(lèi)型 （D）有序類(lèi)型18、在下面各獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域作出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是：（A）沃爾夫獎(jiǎng) （B）圖靈獎(jiǎng) （C）諾貝爾獎(jiǎng) （D）菲爾茲獎(jiǎng)19、棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，它有壓入（push）和彈出（pop）兩種操作。二個(gè)元素AB通過(guò)入棧和出棧操作，可以有AB和BA兩種可能?，F(xiàn)在3個(gè)元素ABC依次進(jìn)棧，出棧序列最終有幾種可能？（A）3 （B）4 （C）5 （D）620、以下哪項(xiàng)不屬于計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽（A）NOIP （B）電子作品制作 （C）ACM大學(xué)生程序設(shè)計(jì)競(jìng)賽 （D）寧波市中小學(xué)生程序設(shè)計(jì)競(jìng)賽二問(wèn)題

8、求解（每小題5分，共10分）1、已知a, b, c, d, e, f, g七個(gè)人中，a會(huì)講英語(yǔ)；b會(huì)講英語(yǔ)和漢語(yǔ)；c會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)；d會(huì)講漢語(yǔ)和日語(yǔ)；e會(huì)講意大利語(yǔ)和德語(yǔ)；f會(huì)講俄語(yǔ)、日語(yǔ)和法語(yǔ)；g會(huì)講德語(yǔ)和法語(yǔ)。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以，請(qǐng)以“a b”開(kāi)頭寫(xiě)出你的安排方案： _ 。2、某班有30個(gè)同學(xué)報(bào)名參加100米、400米、800米三項(xiàng)比賽，已知有15人報(bào)了100米，8人報(bào)了400米，6人報(bào)了800米，且其中有3人這三個(gè)項(xiàng)目都報(bào)了。問(wèn)該班最少有_人一項(xiàng)都沒(méi)有報(bào)過(guò)？最多有_人一項(xiàng)都沒(méi)有報(bào)過(guò)？三、閱讀程序?qū)懡Y(jié)果（每題8分，共32分）1、

9、program nbxx09_1;var a,b,s:longint;begin readln(a); s:=a; b:=0; while a<>0 do begin b:=b*10+a mod 10; a:=a div 10; end; s:=s+b; writeln(s);end.輸入：123456789 輸出： 2、program nbXX09_2;varu:array0.3of integer;a,b,c,x,y,z:integer;beginread(u0,u1,u2,u3);a:=u0+u1+u2+u3-5; b:=u0*(u1-u2div u3+8);c:=u0*u1

10、 div u2*u3;x:=(a+b+2)*3-u(c+3)mod 4;y:=(c*100-13)div a div(ub mod 3*5); z:=(a+b+c-x-y)*2;if(x+y)mod 2=0)then z:=(a+b+c+x+y)div 2;writeln(x+y-z);end.輸入：2 5 7 4 輸出： 3、program nbXX09_3;var a,work:array1.100 of integer; i,j,x,d,max:integer;begin readln(max); for i:=1 to max do begin read(ai); worki:=ai;

11、 end; d:=max div 2; while d>=1 do begin for i:=d+1 to max do begin x:=worki; j:=i-d; while (j>0) and (x<workj) do begin workj+d:=workj; dec(j,d); end; workj+d:=x; end; d:=d div 2; end; for i:= max downto 1 do if ai=worki then write('1') else write('0'); writeln;end.輸出： _ 輸入：

12、871 88 149 32 66 90 144 994、program nbXX09_4;var p:array1.10000of longint; n,i,x:longint;function find(x:longint):longint;begin if px=x then find:=x else begin px:=find(px); find:=px; end;end;begin readln(n,x); for i:=1 to n do read(pi); writeln(find(x); for i:=1 to n-1 do write(pi,' '); /兩數(shù)

13、之間輸出一個(gè)空格 writeln(pn);輸出： _ _end.輸入：5 5 3 3 3 2 4四程序填空（前5空，每空2分，后6空，每空3分，共28分）1、“高效”排序以下程序?qū)崿F(xiàn)輸入n個(gè)數(shù)，使用類(lèi)似冒泡排序的方法，依次比較相鄰的兩個(gè)數(shù)，如果前一個(gè)數(shù)比后一個(gè)大，則交換兩者，最終將輸入的n個(gè)數(shù)從小到大排序后輸出。程序在運(yùn)行中發(fā)現(xiàn)某遍掃描后，沒(méi)有數(shù)據(jù)交換發(fā)生，說(shuō)明已經(jīng)有序了，此時(shí)將退出掃描。請(qǐng)將程序補(bǔ)充完整。program nbcz09_5;var n,i,j,tmp:longint; a:array1.10000of longint; flag:boolean; /flag=true表示有交換

14、發(fā)生，flag=false表示沒(méi)有交換begin readln(n); for i:=1 to n do read(ai); i:=1; _; while flag and (i<=n-1) do begin flag:=false; for j:=1 to _ do if aj>aj+1 then begin /前一個(gè)比后一個(gè)大 tmp:=aj; _ _; aj+1:=tmp; _; end; _; end; for i:=1 to n-1 do write(ai,' '); writeln(an);end.2、數(shù)獨(dú)游戲在n行n列的方格中，每個(gè)格子填入一個(gè)1n之間

15、的數(shù)字，使得每行中沒(méi)有重復(fù)數(shù)字，每列上也沒(méi)有重復(fù)數(shù)字。如圖1所示是一個(gè)3行3列的合法的安排方案。12圖41221圖311圖21223圖131312游戲開(kāi)始可以規(guī)定某些格子已經(jīng)有給定的數(shù)字。如圖2所示，在2行2列的方格中，規(guī)定1行1列和2行2列的數(shù)字均為1，則得到唯一的如圖3所示的方案。但如果規(guī)定1行1列數(shù)字為1，2行2列數(shù)字為2，則無(wú)法得到任何合法的方案（如圖4所示）下面的程序求9行9列的一個(gè)安排方案，程序首先讀入若干個(gè)已知格子上的數(shù)字，找到一個(gè)合理的安排方案后輸出。如果沒(méi)有任何合法方案，則輸出“No Solution!”(注意引號(hào)不用輸出)。程序填充格子的次序依次為：1行1列、1行2列、1行

16、9列、2行1列、2行2列、2行9列、9行1列、9行2列、9行9列。請(qǐng)你將空白處的程序補(bǔ)充完整。program nbxx09_6;var h:array1.9,1.9of boolean;/hi,j表示數(shù)字j是否出現(xiàn)在第i行 v:array1.9,1.9of boolean; /vi,j表示數(shù)字j是否出現(xiàn)在第i列 change:array1.9,1.9of boolean;/changei,j表示第i行第j列是否為規(guī)定的數(shù)字 a:array1.9,1.9of integer;/保存方案 i,j,k,n,x:integer;procedure print;/輸出找到的方案var i,j:integ

17、er;begin for i:=1 to 9 do begin for j:=1 to 8 do write(ai,j,' '); writeln(_); end;end;procedure search(i,j:integer); /從i行j列開(kāi)始填充var k:integer;begin if (_) then begin print; halt; /結(jié)束程序 end; if changei,j then begin for k:=1 to 9 do if (not hi,k) and(not vj,k) then begin hi,k:=true; vj,k:=true;

18、 _; if j<9 then search(i,j+1) else search(_); hi,k:=false; vj,k:=false; end end else begin if j<9 then search(i,j+1) else search(_); end;end;begin for i:=1 to 9 do for j:=1 to 9 do begin hi,j:=false; /第i行沒(méi)有數(shù)字j出現(xiàn) vi,j:=false; /第i列沒(méi)有數(shù)字j出現(xiàn) ai,j:=0; /第i行第j列沒(méi)有數(shù)字填入 changei,j:=true; /第i行第j列允許填充(沒(méi)有給定的輸入數(shù)字) end; readln(n); for k:=1 to n do begin readln(i,j,x); ai,j:=x; /第i行第j列給定的數(shù)字為x hi,x:=true; /第i行出現(xiàn)數(shù)字x vj,x:=true; /第j列出現(xiàn)數(shù)字x changei,j:=false; /第i行第j列不允許填充(已有給定的輸入數(shù)字) end; search(_); writeln(_);