2009年寧波市第24屆中小學生計算機程序設計競賽選擇題（1.5每題）以下不屬于程序的基本結構的是：順序結構 選擇分支結構循環(huán)結構 樹形結構由2個a，2個b和2個c構成的所有字符串中，包含子串“abc”的共有（）個。20 8 16 243、假設A=TRUE,B=TRUE,C=TRUE,D=FALSE，邏輯運算表達式AandBorCandD的值是：falsetrue 0 14、下列數(shù)種最大的數(shù)是（）（11111）2 （F）16 （30）10 （35）85、布爾型（boolean）和字符型（char）變量所占用的存儲的空間大小關系是（）布爾型大 字符型大 一樣大 因操作系統(tǒng)而異6、用八位二進制可以表示的最大二進制數(shù)是：（）99999999 11111111 255 2657、有一個10行10列的對稱矩陣，采用壓縮存儲方式來存儲該矩陣的上三角元素（行優(yōu)先次序），第1行第1列的存儲地址為s，每個元素占用2個存儲空間，則第8行第8列元素的首地址為：（）s+100 s+98 s+72 s+708、已知一棵二叉樹的前序遍歷為JFDECBHAIG，中序遍歷結果為DFEJAHBICG，則這棵二叉樹的深度為： 6 5 4 39、已知一棵二叉樹的葉子節(jié)點數(shù)為100，在有二個子女的結點數(shù)為：101 100 99 不能確定10、算術表達式（3a+1）÷5在程序設計中表達為 (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的結果是：（）（16170）8 (7234)10 (1C36)16 (1110000111000)213、計算機內部使用的數(shù)是：二進制數(shù) 八進制數(shù) 十進制數(shù) 十六進制數(shù)14、當n大于100萬時，下列程序段哪個運行最快：(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、當原始待排序數(shù)據(jù)為從小到大排列時，運行時間比原來數(shù)據(jù)為亂序時快的算法是：選擇排序 歸并排序 插入排序 快速排序16、關于算法的下列敘述不正確的是：A、算法的每一步必須沒有歧義，不能有半點含糊B、算法必須有輸入C、同一問題可能存在多種不同的算法D、同一算法可以用多種不同的形式來描述17、for語句中的循環(huán)變量，其類型必須是：A、整型 B、實型 C、自定義類型D有序類型18、下列各種獎項中，為計算機領域作出杰出貢獻的科學家設立的獎項是：A沃爾夫獎 B圖靈獎 C諾貝爾獎 D菲爾茲獎19、棧是一種后進先出的數(shù)據(jù)結構，他有壓入（push）和彈出（pop）兩種操作。二個元素AB通過入棧和出棧操作，可以有AB和BA兩種可能。現(xiàn)在3個元素ABC依次進棧、出棧序列最終有幾種可能（）A3 B4 C5 D620、以下哪項不屬于計算機程序設計競賽（）find:=p[x];end;end;beginreadln(n,x);fori:=1tondoread(p[i]);writeln(find(x));fori:=1ton-1dowrite(p[i],’‘);//兩數(shù)之間輸出一個空格writeln(p[n]);end.輸入：5533324輸出：程序填空（前5空，每空2分，后6空，每空3分，共28分）1、“高效”排序以下程序實現(xiàn)輸入n個數(shù)，使用類似冒泡排序的方法，依次比較相鄰的兩個數(shù)，如果前一個數(shù)比后一個數(shù)大，則交換兩者，最終將輸入的n個數(shù)從小到大排序后輸出。程序運行中發(fā)現(xiàn)某遍掃描后，沒有數(shù)據(jù)交換發(fā)生，說明已經有序了，此時將退出掃描。請將程序補充完整。programnbxx09_5;varn,i,j,tmp:longint;a:array[1..10000]oflongint;flag:boolean;//flag=true表示有交換發(fā)生，flag=false表示沒有交換beginreadln(n);fori:=1tondoread(a[i]);i:=1;①whileflagand(i<=n-1)dobeginflag:=false;forj:=1to②doifa[j]>a[j+1]thenbegin//前一個比后一個大tmp:=a[j];③a[j+1]:=tmp;④end;⑤end;fori:=1ton-1dowrite(a[i],’‘);writeln(a[n]);end.數(shù)獨游戲在n行n列的方格中，每個格子填入一個1——n之間數(shù)字，使得每行中沒有重復數(shù)字，每列上也沒有重復數(shù)字。如圖1所示是一個3行3列的合法安排方案。12323131211122112圖4圖3圖2圖1圖4圖3圖2圖1游戲開始可以規(guī)定某些格子已經有給定的數(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ù)字，找到一個合理的安排方案后輸出。如果沒有任何合法方案，則輸出‘NoSolution!”(注意引號不用輸出)程序填充格子的次序依次為：1行1列，1行2列，……1行9列，2行1列，2行2列，……2行9列，9行1列，9行2列，……，9行9列。請你將空白處的程序補充完整。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列開始填充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行沒有數(shù)字j出現(xiàn)v[i,j]:=false;//第i列沒有數(shù)字j出現(xiàn)a[i,j]:=0;//第i行第j列沒有數(shù)字填入change[i,j]:=true;//第i行第j列允許填充（沒有給定的輸入數(shù)字）end;readln(n);fork:=1tondobeg