初賽試題信息學(xué)命題

1、信息學(xué)競(jìng)賽初賽模擬試題（十六）（初中組 PASCAL 語(yǔ)言，兩小時(shí)完成）請(qǐng)將正確在答卷上填寫(xiě)，在本試題卷上作答無(wú)效一、 選擇題：（選出每題正確的一個(gè)代碼，填在橫線上，每題 1.5 分，共 30 分）1、執(zhí)行下列二進(jìn)制算術(shù)加運(yùn)算 11001001（ ）。D. 10100010A. 11101111B. 11110000C. 000000012、假設(shè) a1，a2，a3 是變量，且值均為 True，則下列表達(dá)式中值為 False 的是A. NOT a1 AND NOT a2C. (NOT a1 OR a2)AND (a2 OR a3)B. a1 OR a2 AND a3D. False OR a1

2、AND a2 OR NOT a33、若一個(gè)問(wèn)題的求解既可以用遞歸算法，也可以用遞推算法，則往往用算法。A.先遞歸后遞推 B. 先遞推后遞歸 C.遞歸D.遞推4、表達(dá)式 8 MOD (2*(5-3*(4*(5 DIV 2)DIV 10)的值是A. 0B. 1C. 2D. 35、貪婪法是一種的算法。 A.不求最優(yōu)，只求滿意C.求取全部可行解B.只求最優(yōu)D.求取全部最優(yōu)解6、稱(chēng)一種語(yǔ)言為低級(jí)程序語(yǔ)言是由于它。A.離機(jī)器特性近 C.編程難度低B.離自然語(yǔ)言近 D.通用性強(qiáng)7、排序方法中，從未排序序列中依次取出元素與已排序序列(初始時(shí)為空)中的元素作比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為.A.

3、 歸并排序B. 二分法排序C. 冒泡排序D.排序8、若進(jìn)棧序列為 3,5,7,9,進(jìn)棧過(guò)程中可以出棧，則不可能是一個(gè)出棧序列。A. 7,5,3,9B. 9,7,5,3C.7,5,9,3D. 9,5,7,39、中綴表達(dá)式(a-b)*(cd)的后綴表達(dá)式是.A. abcd*-B. ab-cdC. ab-*cdD. a-bcd *10、字符A、B、C 依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成多少個(gè)不同的字符串？A. 5B. 4C. 6D. 111、一個(gè)字長(zhǎng)的二進(jìn)制位數(shù)是A.8B.16C.32D.隨計(jì)算機(jī)系統(tǒng)而不同的12、當(dāng)a=1,b=3,c=5,d=4 時(shí)，執(zhí)行下面一段程序后，

4、x 的值為if(ab)thenif(cd)then x=1 elseif(ac)thenif(b1）則 fun(4)的值是A.25B.30C.33D. 2817、在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)A.C.B. 右子結(jié)點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)和右子結(jié)點(diǎn)D.結(jié)點(diǎn)、右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)在數(shù)組 A1.101中,對(duì) 1k101,若 Ak是葉子結(jié)點(diǎn),則18、一棵含有 101 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)k 的最小值是。A. 51B.50C. 49D.48時(shí)要占個(gè)字節(jié)，設(shè) I 從 0 變化到，J 從變化到 1，19、已知數(shù)組 A 中，每個(gè)元素 AI,J在分配內(nèi)存時(shí)是從地址SB 開(kāi)始連續(xù)按行分配的試問(wèn)：A4,8的起始地址為A.

5、 SB+141B. SB+180C. SB+142D. SB+18120、下面關(guān)于圖的的敘述中正確的是。A.B.C.用相鄰矩陣法用相鄰矩陣法用鄰接表法圖，占用的圖，占用的圖，占用的圖，占用的空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)?？臻g大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)?？臻g大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)?？臻g大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)。D. 用鄰接表法二、問(wèn)題解答：(4+6=10 分)1、 將一支鉛筆、一枝原子筆和一個(gè)橡皮擦分別放入A、B、C 三位的筆盒中，每個(gè)筆盒只能放一種文具，且三個(gè)筆盒內(nèi)放的文具都不相同。下列三句敘述中只有一句為真，其余二句為假。試問(wèn)哪一句為真

6、？A 的筆盒中放的是鉛筆。B 的筆盒中沒(méi)有鉛筆。C 的筆盒中沒(méi)有橡皮擦。2、喜歡收集布偶，她將紅、藍(lán)、黃色的趴趴熊、kitty 貓、狗布偶各 1 只（共 9 只）排成三行三列的方陣，然后請(qǐng)北北來(lái)猜。提示說(shuō)：紅色的動(dòng)物都在第一列。黃色的動(dòng)物都不在第三列。kitty 貓只能在四個(gè)角或正中間。趴趴熊只能在第一行最上面二個(gè)位置或在第三行最下面一個(gè)位置。第二行最下面一個(gè)位置放的是顏色的布偶。三、看程序?qū)懡Y(jié)果：(8+10+12=30 分)1.var x,y:eger;function(x,y:eger):eger;var r:eger; beginrepeatr:=x mod y; x:=y;y:=r;

7、until r=0;:=x;end;beginx:=80;y:=98;wrin(x*y div(x,y);end.輸出：2. const n=12; var i,j:eger; list:array0.n ofbegineger;for i:=1 to n do read(listi); for i:=2 to n dobeginlist0:=listi; j:=i-1;while list0listj do beginlistj+1:=listj; dec(j);end; listj+1:=list0;end;for i:=1 to n do wriend.isti:5);輸入：67 98

8、7823 2332 2323 64 90 -34 121 -98 22 67輸出：3. var i,j,k,n:eger;a:array1.100,1.100 of beginreadln(n); k:=1;i:=1;j:=1;ai,j:=1;while kn doeger;beginif (i=1) and (j mod 2=1) then inc(j) else if (j=1) and (i mod 2=0) then inc(i)else if (i+j) mod 2=0 then begin dec(i);inc(j);end else if (i+j) mod 2=1 then b

9、egin inc(i);dec(j);end;inc(k);ai,j:=k;end;wrin(i,/,j);end.輸入：1999輸出：四、程序填空：(12+18=30 分)1、一個(gè)數(shù)如果正好等于其因子之和，就稱(chēng)其為“完數(shù)”。例如 6 的因子是 1，2，3，并且 6=1+2+3，所以 6 是一個(gè)“完數(shù)”。下面的程序可以輸出 2n 之間的所有完數(shù)之和。其中n 為 21000 之間的任意整數(shù)。請(qǐng)將程序填寫(xiě)完全。PROGRAM bs1；VAR a，n，s:eger；FUNCTION func(n:eger)：；VAR s，k: BEGINs:=0；eger；FOR k:=1 TO DOIF n MO

10、D k=0 THENs:= ；IF THENfunc:=TrueELSEEND；func:=FalseBEGINs:=0；Readln(n)； FOR a:=2 TO n DOIF func THEN Wrin(s)END.s:=s+a；2.本程序的功能是將中綴表示的算術(shù)表達(dá)式轉(zhuǎn)換成后綴表示。如中綴表達(dá)式(A-(B*C+D)*E)/(F+G)的后綴表示為ABC*D+E*-FG+/為了方便，假定變量名為單個(gè)英語(yǔ)字母，運(yùn)算符只有/（均為雙目運(yùn)算符，左結(jié)合），并假定所提供的算術(shù)表達(dá)式非空且語(yǔ)法是正確的。另外，中綴表示形式中無(wú)空格符，但整個(gè)算術(shù)表達(dá)式以空格符結(jié)束。各數(shù)組意義如下：POLISH其后綴表示

11、;s是一個(gè)后進(jìn)先出棧。函數(shù) PRIOR(CHAR)返回符號(hào) CHAR 的優(yōu)先級(jí)，各符號(hào)的優(yōu)先級(jí)如下表示：CHAR* /+ -()PRIOR(CHAR) 4321label 10; var input:string;polish,s:array1.100 of char;k,p,i:eger;function prior(ch:char) :begineger;if (ch=*) or (ch=/) then prior:=4;if (ch=+) or (ch=-) then prior:=3; if ch=( then prior:=2;if ch=) then prior:=1; end;procedure a; begin;end; procedure b; begin ;end;begininput:=(A-(B*C+D)*E)/(F+G); k:=0;p:=0;i:=1;while i=length(input) do beginif (inputi=+) or (inputi=-) or (inputi=*) or (inputi=/) then beginwhile p0 dobeginif end;a;then b e