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

1、2009年寧波市第24屆中小學生計算機程序設(shè)計競賽小學組初賽試題（說明：答案請寫在答題卷上?？荚嚂r間120分鐘，滿分100分）一、選擇題（每題有且僅有一個正確答案，選對得1.5分，選錯、不選或多選均不得分）1、若已知一個棧的入棧順序是1，2，3，n，其輸出序列為P1，P2，P3，Pn，若P1是n，則Pi是( )A)i B)n-1 C)n-i+1 D)不確定2、滿二叉樹的葉結(jié)點個數(shù)為N，則它的結(jié)點總數(shù)為（ ）。A. N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 13、二叉樹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、完全二叉樹的結(jié)點個數(shù)為11，則它的葉結(jié)點個數(shù)為（ ）。A. 4 B.3 C.5 D. 2 E. 65、布爾型(boolean)和字符型(char)變量所占用的存儲空間大小的關(guān)系是（A）布爾型大 （B）字符型大 （C）一樣大 （D）因操作系統(tǒng)而異6、用八位二進制可以表示的最大十進制數(shù)是：（A）99999999 （B）11111111 （C）255 （D）2567、有一個10行10列的對稱矩陣，采

3、用壓縮存儲方式來存儲該矩陣的上三角元素（行優(yōu)先次序），第1行第1列的存儲地址為s，每個元素占用2個存儲空間，則第8行第8列元素的首地址為： （A）s+100 （B）s+98 （C）s+72 （D）s+708、已知一棵二叉樹的葉子結(jié)點數(shù)為100，則有二個子女的結(jié)點數(shù)為：（A） 101 （B） 100 （C） 99 （D） 不能確定9、已知一棵二叉樹的前序遍歷為JFDECBHAIG，中序遍歷結(jié)果為DFEJAHBICG，則這棵二叉樹的深度為： （A） 6 （B）5 （C）4 （D）310、在Pascal語言中，表達式 （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、計算機內(nèi)部使用的數(shù)是：（A）二進制數(shù)      （B） 八進制數(shù) （C） 十進制數(shù)     （D） 十六進制數(shù)14、當n大于100萬時,下列程序段哪個運行最快（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、當原始待排序數(shù)據(jù)為從小到大排列時，運行時間比原始數(shù)據(jù)為亂序時快的算法是： （A）選擇排序 （B）歸并排序 （C）插入排序 （D）快速排序 16、關(guān)于算法的下列敘述不正確的是：（A）算法的每一步必須沒有歧義，不能有半點含糊（B）算法必須有輸入（C）同一問題可能存在多種不同的算法（D）同一算法可以用多種不同的形式來描述17、FO

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

8、求解（每小題5分，共10分）1、已知a, b, c, d, e, f, g七個人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們的座位安排在圓桌旁，使得每個人都能與他身邊的人交談？如果可以，請以“a b”開頭寫出你的安排方案： _ 。2、某班有30個同學報名參加100米、400米、800米三項比賽，已知有15人報了100米，8人報了400米，6人報了800米，且其中有3人這三個項目都報了。問該班最少有_人一項都沒有報過？最多有_人一項都沒有報過？三、閱讀程序?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、之間輸出一個空格 writeln(pn);輸出： _ _end.輸入：5 5 3 3 3 2 4四程序填空（前5空，每空2分，后6空，每空3分，共28分）1、“高效”排序以下程序?qū)崿F(xiàn)輸入n個數(shù)，使用類似冒泡排序的方法，依次比較相鄰的兩個數(shù)，如果前一個數(shù)比后一個大，則交換兩者，最終將輸入的n個數(shù)從小到大排序后輸出。程序在運行中發(fā)現(xiàn)某遍掃描后，沒有數(shù)據(jù)交換發(fā)生，說明已經(jīng)有序了，此時將退出掃描。請將程序補充完整。program nbcz09_5;var n,i,j,tmp:longint; a:array1.10000of longint; flag:boolean; /flag=true表示有交換

14、發(fā)生，flag=false表示沒有交換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 /前一個比后一個大 tmp:=aj; _ _; aj+1:=tmp; _; end; _; end; for i:=1 to n-1 do write(ai,' '); writeln(an);end.2、數(shù)獨游戲在n行n列的方格中，每個格子填入一個1n之間

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

16、9列、2行1列、2行2列、2行9列、9行1列、9行2列、9行9列。請你將空白處的程序補充完整。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列開始填充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行沒有數(shù)字j出現(xiàn) vi,j:=false; /第i列沒有數(shù)字j出現(xiàn) ai,j:=0; /第i行第j列沒有數(shù)字填入 changei,j:=true; /第i行第j列允許填充(沒有給定的輸入數(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(_);