009年寧波市第24屆中小學(xué)生計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽

2009年寧波市第24屆中小學(xué)生計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽選擇題（1.5每題）以下不屬于程序的基本結(jié)構(gòu)的是：順序結(jié)構(gòu) 選擇分支結(jié)構(gòu)循環(huán)結(jié)構(gòu) 樹(shù)形結(jié)構(gòu)由2個(gè)a，2個(gè)b和2個(gè)c構(gòu)成的所有字符串中，包含子串“abc”的共有（）個(gè)。20 8 16 243、假設(shè)A=TRUE,B=TRUE,C=TRUE,D=FALSE，邏輯運(yùn)算表達(dá)式AandBorCandD的值是：falsetrue 0 14、下列數(shù)種最大的數(shù)是（）（11111）2 （F）16 （30）10 （35）85、布爾型（boolean）和字符型（char）變量所占用的存儲(chǔ)的空間大小關(guān)系是（）布爾型大 字符型大 一樣大 因操作系統(tǒng)而異6、用八位二進(jìn)制可以表示的最大二進(jìn)制數(shù)是：（）99999999 11111111 255 2657、有一個(gè)10行10列的對(duì)稱矩陣，采用壓縮存儲(chǔ)方式來(lái)存儲(chǔ)該矩陣的上三角元素（行優(yōu)先次序），第1行第1列的存儲(chǔ)地址為s，每個(gè)元素占用2個(gè)存儲(chǔ)空間，則第8行第8列元素的首地址為：（）s+100 s+98 s+72 s+708、已知一棵二叉樹(shù)的前序遍歷為JFDECBHAIG，中序遍歷結(jié)果為DFEJAHBICG，則這棵二叉樹(shù)的深度為： 6 5 4 39、已知一棵二叉樹(shù)的葉子節(jié)點(diǎn)數(shù)為100，在有二個(gè)子女的結(jié)點(diǎn)數(shù)為：101 100 99 不能確定10、算術(shù)表達(dá)式（3a+1）÷5在程序設(shè)計(jì)中表達(dá)為 (3a+1)/5 (3*a+1)\5 (3*a+1)/511、將數(shù)組{1、2、4、3、5、6、7、8}中的元素用插入排序的方法從大到小的順序排列，需要比較的次數(shù)是：7 27 28 6412、算式（2009）16-（2008）10-（2007）8的結(jié)果是：（）（16170）8 (7234)10 (1C36)16 (1110000111000)213、計(jì)算機(jī)內(nèi)部使用的數(shù)是：二進(jìn)制數(shù) 八進(jìn)制數(shù) 十進(jìn)制數(shù) 十六進(jìn)制數(shù)14、當(dāng)n大于100萬(wàn)時(shí)，下列程序段哪個(gè)運(yùn)行最快：(A).max:=0;(A).max:=0;fork:=1ton-1doforj:=k+1tondoifmax<abs(a[k]-a[j])thenmax:=abs(a[k]-a[j])(B).sum:=0;k:=1;whilek<=ndobeginforj:=1tokdosum:=sum+1;k:=k+2;end;(C).sum:=0;k:=1;whilek<=ndobeginforj:=1tondosum:=sum+1;k:=k*2;end;(D).k:=1;j:=n;x:=a[1];whilek<jdobeginwhile(k<j)and(a[j]>x)dodec(j);ifk<jthenbegina[k]:=a[j];inc(k);end;while(k<j)and(a[k]<x)doinc(k);ifk<jthenbegina[j]:=a[k];dec(j);end;end;15、當(dāng)原始待排序數(shù)據(jù)為從小到大排列時(shí)，運(yùn)行時(shí)間比原來(lái)數(shù)據(jù)為亂序時(shí)快的算法是：選擇排序 歸并排序 插入排序 快速排序16、關(guān)于算法的下列敘述不正確的是：A、算法的每一步必須沒(méi)有歧義，不能有半點(diǎn)含糊B、算法必須有輸入C、同一問(wèn)題可能存在多種不同的算法D、同一算法可以用多種不同的形式來(lái)描述17、for語(yǔ)句中的循環(huán)變量，其類型必須是：A、整型 B、實(shí)型 C、自定義類型D有序類型18、下列各種獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)領(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兩種可能。現(xiàn)在3個(gè)元素ABC依次進(jìn)棧、出棧序列最終有幾種可能（）A3 B4 C5 D620、以下哪項(xiàng)不屬于計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽（）find:=p[x];end;end;beginreadln(n,x);fori:=1tondoread(p[i]);writeln(find(x));fori:=1ton-1dowrite(p[i],’‘);//兩數(shù)之間輸出一個(gè)空格writeln(p[n]);end.輸入：5533324輸出：程序填空（前5空，每空2分，后6空，每空3分，共28分）1、“高效”排序以下程序?qū)崿F(xiàn)輸入n個(gè)數(shù)，使用類似冒泡排序的方法，依次比較相鄰的兩個(gè)數(shù)，如果前一個(gè)數(shù)比后一個(gè)數(shù)大，則交換兩者，最終將輸入的n個(gè)數(shù)從小到大排序后輸出。程序運(yùn)行中發(fā)現(xiàn)某遍掃描后，沒(méi)有數(shù)據(jù)交換發(fā)生，說(shuō)明已經(jīng)有序了，此時(shí)將退出掃描。請(qǐng)將程序補(bǔ)充完整。programnbxx09_5;varn,i,j,tmp:longint;a:array[1..10000]oflongint;flag:boolean;//flag=true表示有交換發(fā)生，flag=false表示沒(méi)有交換beginreadln(n);fori:=1tondoread(a[i]);i:=1;①whileflagand(i<=n-1)dobeginflag:=false;forj:=1to②doifa[j]>a[j+1]thenbegin//前一個(gè)比后一個(gè)大tmp:=a[j];③a[j+1]:=tmp;④end;⑤end;fori:=1ton-1dowrite(a[i],’‘);writeln(a[n]);end.數(shù)獨(dú)游戲在n行n列的方格中，每個(gè)格子填入一個(gè)1——n之間數(shù)字，使得每行中沒(méi)有重復(fù)數(shù)字，每列上也沒(méi)有重復(fù)數(shù)字。如圖1所示是一個(gè)3行3列的合法安排方案。12323131211122112圖4圖3圖2圖1圖4圖3圖2圖1游戲開(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)有任何合法方案，則輸出‘NoSolution!”(注意引號(hào)不用輸出)程序填充格子的次序依次為：1行1列，1行2列，……1行9列，2行1列，2行2列，……2行9列，9行1列，9行2列，……，9行9列。請(qǐng)你將空白處的程序補(bǔ)充完整。programnbxx09_6;varh:array[1..9,1..9]ofboolean;//h[i,j]表示數(shù)字j是否出現(xiàn)在第i行v:array[1..9,1..9]ofboolean;//v[i,j]表示數(shù)字j是否出現(xiàn)在第i列change:array[1..9,1..9]ofboolean;//change[i,j]表示第i行第j列是否為規(guī)定的數(shù)字a:array[1..9,1..9]ofinteger;//保存方案i,j,k,n,x:integer;procedureprint;//輸出找到的方案vari,j:integer;beginfori:=1to9dobeginforj:=1to8dowrite(a[i,j],’‘);writeln(⑥);end;end;proceduresearch(i,j:integer);//從i行j列開(kāi)始填充vark:integer;beginif(⑦)thenbeginprint;halt;end;ifchange[i,j]thenbeginfork:=1to9doif(noth[i,k])and(notv[j,k])thenbeginh[i,k]:=true;v[j,k]:=true;⑧；ifj<9thensearch(i,j+1);elsesearch(⑨)；h[i,k]:=false;v[j,k]:=false;end;endelsebeginifj<9thensearch(i,j+1)elsesearch(⑨)；end;end;beginfori:=1to9doforj:=1to9dobeginh[i,j]:=false;//第i行沒(méi)有數(shù)字j出現(xiàn)v[i,j]:=false;//第i列沒(méi)有數(shù)字j出現(xiàn)a[i,j]:=0;//第i行第j列沒(méi)有數(shù)字填入change[i,j]:=true;//第i行第j列允許填充（沒(méi)有給定的輸入數(shù)字）end;readln(n);fork:=1tondobeg