資源簡介

信
息
學(xué)
練
習(xí)
本

一、數(shù)學(xué)趣題
1、在一樁盜竊案中，有兩個嫌疑犯甲和乙，另有四個證人正在受到詢問。
第一個證人說：“我只知道甲未盜竊。”
第二個證人說：“我只知道乙未盜竊。”
第三個證人的證詞中至少有一個是真的。
第四個證人最后說：“我可以肯定第三個證人的證詞是假的。”
通過調(diào)查研究，已證實第四個證人說了實話，那么盜竊犯是誰？
2、甲、乙、丙三人被蒙上眼睛，、告訴他們每人頭上都帶了一頂帽子，帽子的顏色不是紅的就是綠的，在這以后，就去掉蒙眼睛的布，要求每個人如果看見別人（一個人或兩個人）戴的帽子就舉手，并且誰能斷定自己頭上帽子的顏色，誰就馬上離開房間。三人碰巧戴的都是紅帽子，因此三人都舉了手，幾分鐘后，丙首先走開了，他是怎么推導(dǎo)出自己頭上帽子的顏色的？
3、三只口袋里分別裝有兩個紅球、兩個白球、一紅一白球，但口袋外貼的標(biāo)簽都是錯的，請從一只口袋里取出一只球，使你能根據(jù)這個球的顏色說出三只口袋里球的顏色。
4、有9只乒乓球，他們的大小形狀一樣，其中有一個次品比其他正品的重量輕一點。你能不能用一臺天平稱兩次（不用砝碼），就把次品挑出來。
5、在國際飯店的宴會桌旁，甲、乙、丙、丁四位朋友進(jìn)行有趣的交談，用了中、英、法、日四種語言，知道的情況如下：
（1）甲、乙、丙各會兩種語言，丁只會一種語言；
（2）有一種語言四人中有三人都會；
（3）甲會日語，丁不會日語，乙不會英語；
（4）甲、丙，丙與丁不能直接交談，乙與丙可以直接交談；
（5）沒有人既會日語又會法語。
問：甲、乙、丙、丁各會什么語言？
6、如果在81個零件中混雜了一個重量較輕的次品，用天平（不用砝碼）最少稱幾次才能把次品找出來？
7、某校數(shù)學(xué)競賽，A、B、C、D、E這五位同學(xué)取得了前五名，老師對他們說：“祝賀你們?nèi)〉昧撕贸煽儯銈儾乱幌旅谓Y(jié)果。”
A說：“B是第三，C是第五”。
B說：“D是第二，E是第四。”
C說：“A是第一，E是第四。”
D說：“C是第一，B是第二。”
E說：“D是第二，A是第三。”
老師說他們每個都只猜對了一半，那么這五個人實際名次如何呢？
二、排列與組合問題
1、寫出從A,B,C,D四個元素中任取兩個元素的所有排列.
2、用0到9這10個數(shù)字可組成多少個無重復(fù)數(shù)字的三位數(shù)
3、甲、乙、丙、丁四人并排站成一排，如果甲、乙必須站在一起，則不同的排法共有 種.
4、從1到9這9個數(shù)字中任選5個,可以組成多少個符合下列條件的五位數(shù).
（1）奇數(shù);（2）能被25整除;
5、7人排成一排,按下列要求,求各有多少種不同的排法.
(1)甲不能排在首位,乙不能排在末位;
(2)甲、乙兩人間恰好間隔兩人;
6、將N個紅球和M個黃球排成一行。例如：N=2，M=3可得到以下6種排法：
紅紅黃黃黃 紅黃紅黃黃 紅黃黃紅黃
黃紅紅黃黃 黃紅黃紅黃 黃黃黃紅紅
問題：當(dāng)N=4，M=3時有多少種不同排法 (不用列出每種排法)
7、平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同三角形？
三、閱讀程序
1、program t1;
var
g,m: integer;
k,t: real;
begin
k:=0;
g:=0;
for m:=1 to 49 do
begin
g:=g+1;
k:=k+1/(g*(g+1));
end;
writeln ( k: 10: 2 )
end.
輸出：______
3、program t3;
var
n, i, t: longint;
tem: integer;
s: string;
begin
readln(n); s:='1';
repeat
i:= length(s);
while s[i] ='1' do
begin
s[i]:= '0' ;dec(i);
end;
if i>0 then s[i]:='1'
else s:= '1' +s;
val(s,t,tem);
until t mod n = 0;
writeln(n,'*',t div n,'=',s);
end.
輸入：6
輸出：______
5、program t5;
var m,n,i,p,k:integer;
r:array[1..200] of integer;
b: boolean;
begin
m:=6;n:=2;
for i:=1 to m-1 do r[i]:=i+1;
r[m]:=1;i:=0;p:=1;b:=true;
while b do
begin
i:=i+1;k:=p;p:=r[p];
if k=p then
begin
writeln(p);
b:=false;
end
else if i=n+1 then
begin
write(p,' ');i:=0;
p:=r[p];r[k]:=p;
end
end
end.
輸出：________
7、program t7；
var n，k，s：longint；
begin
n:=1000000000；
k:=0；
s:=1；
while s <= n do
begin
k:=k+1;
n:=n-s;
s:=s+6*k
end;
writeln (k)
end.
輸出：_______
四、完善程序
1、以下程序是將一組整數(shù)按從小到大的順序排列。排序的方法是將長度為n的數(shù)a分為兩個長度分別為(n div 2)與(n-n div 2)的子數(shù)組a1，a2。然后遞歸調(diào)用排序過程，將a1，a2分別排序，最后將a1，a2歸并成數(shù)組a。例如a=(3，1，2，4)，那么a1=(3，1)，a2=(2，4)。調(diào)用排序過程將a1，a2排序，得到a1=(1，3)，a2=(2，4)，然后進(jìn)行合并排序。
從鍵盤輸入數(shù)的長度n以及n個整數(shù)，存在數(shù)組a中，調(diào)用子過程sort進(jìn)行排序，最后輸出排序結(jié)果。
program wsh；
const maxn=100；．
type arr：array[1..maxn] of integer；
var
a：array[1..maxn] of integer； n，i：integer；
procedure sort(n:integer; var a:arr);
var
i, p1, p2, n1, n2: integer;
a1,a2 :arr;
begin
if n = 1 then exit;
fillchar(a1,sizeof(a1) ,0);
fillchar(a2,sizeof(a2) ,0);
n1:=0; n2:=0;
n1:=n div 2; n2:=(____(1)____);
for i:= 1 to n1 do a1[i]:=a[i];
for i:= 1 to n2 do a2[i]:=____(2)____;
____(3)____;
sort(n2, a2);
p1:=1; p2:=1; n:=0;
while (p1 <= n1) and (____(4)____) do
begin
n:=n+1;
if ____(5)____
then begin a[n]:=a1[p1] ;inc(p1); end
else begin ____(6)____; inc(p2) ;end;
end;
if p1 <= n1
then for i:= ____(7)____ to n1 do begin n:=n+1;a[n]:=a1[i] end
else for i:=p2 to n2 do begin n:=n+1; a[n]:=a2[i]; end;
end;
begin
write('n = ');
readln (n);
for i:= 1 to n do read(a[i]);
readln;
sort(n,a);
for i:=1 to n do write(a[i],'');
writeln;
end.
2、有n(1≤n≤100)個同學(xué)種m(1≤n≤m≤100)種小樹苗，例如：4個同學(xué)（1、2、3、4）每小時種4種樹苗（A、B、C、D）的數(shù)量估算如下表所示，編程輸出每人種1種苗所用的總時間最少的安排方案和所花費的時間。
學(xué) 生 A B C D
1 5 2 4 5
2 4 3 5 3
3 5 2 4 2
4 3 2 3 3
program wsh;
const
maxn=100; maxm = 100;
var
a: array[1..maxn, 1..maxm] of integer;
m, n: integer;
i, j, t: integer;
procedure work(k,t1: integer);
var i: integer;
begin
if ____(1)____ then
begin
if t1 < t then t1:=t;
exit;
end;
for i:= ___(2)___ to ___(3)___ do
work(k+1,___(4)___);
end;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do read (a[i,j]);
readln
end;
t:= maxint;
work(1,0);
writeln(t)
end.
3、下列程序是對冒泡排序的一種改進(jìn)，數(shù)組elem中有n個元素elem[1]、elem[2]…、elem[n]。要排序的關(guān)鍵字是key。先從一端開始掃描，進(jìn)行比較、交換，然后改變下一趟的掃描方向進(jìn)行同樣的處理。請完善下面的過程。
program wsh;
type
Td = record
key: integer;
inf: real;
end;
var
elem:array[1..1000] of Td;
n, i: integer;
procedure shakesort(n: integer);
var
i, t, h: integer;
c: boolean;
temp: Td;
begin
h:=1; t:=n;
repeat
____(1)____;
for i:=h to t-1 do
if elem[i].key > elem[i+1].key then begin
temp:=elem[i]; elem[i]:=elem[i+1];
elem[i+1]:=temp; ____(2)____;
end;
____(3)____;
for i:=t-1 downto h do
if elem[i].key > elem[i+1].key then begin
temp:=elem[i]; elem[i]:=elem[i+1];
elem[i+1]:=temp; ____(4)____;
end ;
____(5)____;
until c ;
end;
begin{主過程}
…{略}
end．
4、[問題描述]在n個元素的集合S中，找最大和最小元素(設(shè)n的值為2m)．
[解題思路]把集合S分成兩個子集S1和S2，每個子集有n/2個元素．應(yīng)用遞歸過程search(S，Y，MAX，MIN)(S中有2k個元素)，過程返回一對(MAX，MIN)值，為最大和最小元素，最后，把S1和S2中的最大和最小元素進(jìn)行比較，從而得到S中的最大和最小元素．
[程序]
program wsh;
type data = array[1..256] of byte;
jh = set of byte;
var s,ss:jh;
a:data;
i ,j, d,largest, smallest: byte;
function sq(k: byte): byte;
begin
if k =1 then sq:=2 else sq:=2*sq(k-1);
end;
procedure seareh(x:jh; y:byte; var max,rain:byte);
var k,p,w,nxl,nx2,ni1,ni2,n: byte;
m:array[1..2] of byte;
s1 ,s2:jh;
begin
if y = 2 then
begin
p:=0;
for k:=1 to i do
if ___(1)___ then
begin
p:=p+1;m[p]:=___(2)___;
end;
if ___(3)___ then
begin
w:=m[1];m[1]:=m[2];m[2]:=w;
end;
max:= m[1] ;min:= m[2] ;exit;
end
else
begin
si:=[];n:=O;y:=___(4)___;
for k:=1 to i do
if ___(5)___ then
begin
n:=n+1;if n <= y then s1:=___(6)___;
end;
s2:=___(7)___;
search(s1,y,nx1,ni1);search(s2,y,nx2,ni2);
if nx1 > nx2 then max:=nx1 else max:=nx2;
if ni1 < ni2 then min:=ni1 else min:=ni2;
end
end;
begin
i:=0;s:=[];ss:=[];
for j:=1 to 7 do ss:=ss+[sq(j)];
writeln('enter 2︿n data:');
repeat
while not eoln do
begin
i:=i + 1; read(d);
if ___(8)___ then i:= i - 1
else begin
a[i]:=d;s:=s+[a[i]];
end;
end; readln;
until i in ss;
search(s,i,largest,smallest);
writeln('largest-data：'，largest，'smallest-data：'，smallest)
end．
5、[問題描述]將一個含有運算符為：(、)、+、-、*、/、︿(乘冪運算)、~(求負(fù)運算)的中綴表達(dá)式，如：((1+2)*5)︿2-(3+5)/2轉(zhuǎn)化為后綴表達(dá)式，如：12+5*2︿35+2/-．
[解題思路]將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，首先規(guī)定運算符的優(yōu)先數(shù)如下：
┌───┬───┬───┬─────┬──────┬───┬───┐
│運算符│ ( │ ) │ +，－ │ * ，/ │ ~ │ ~ │
├───┼───┼───┼─────┼──────┼───┼───┤
│優(yōu)先數(shù)│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │
└───┴───┴───┴─────┴──────┴───┴───┘
1．若輸入是運算量，則將該運算量輸出；
2．若是左括號“(”，則將該符號的優(yōu)先數(shù)壓入設(shè)置的運算符堆棧e[p]中去；
3．輸入運算符優(yōu)先數(shù)是2，3，4，5時，如果棧空，則將運算符的優(yōu)先數(shù)進(jìn)棧。如果棧不空，則將它與棧頂元素進(jìn)行比較，倘若優(yōu)先數(shù)大于棧頂元素的優(yōu)先數(shù)，則進(jìn)棧；小于頂元的，則頂元退棧并輸出該運算符，然后再繼續(xù)比較，直到大于頂元或棧空時進(jìn)棧；
4．若是右括號“)”，同時棧頂元又為左括號“(”，則棧頂元退棧，并抹去右括號“)”．否則轉(zhuǎn)3處理；
5．輸入完而棧非空，則將棧內(nèi)內(nèi)容逐一退棧并輸出。所有輸出的結(jié)果就為后綴表達(dá)式。
過程中用到的相關(guān)數(shù)據(jù)結(jié)構(gòu)如下：
type arraydata = array[1..100] of string[20];
const fh:array[1..8] of string[1]
=('(',')','+','-','*','/','~','︿');
b:array[1..8] of byte =(0,1,2,2,3,3,4,5);
var d: arraydata; {存儲運算量及運算符號}
i,j,m,k: byte;
[過程程序]
procedure hzbds(var d: arraydata; var m: byte );
var: array [ 1'-. 100 ] of byte;
i,p,k ,bi:byte; bl: boolean;
begin
p:=O;k:=1;bj:=0;
while k<=m do
begin
if ___(1)___ then
begin
p:=p+1;e[p]:=1
end
else begin
for i:=2 to 8 do
if ___(2)___ then
begin
b1:= true;
repeat
if ___(3)___ then
begin
p:= p+1 ;e[p]:=i;bj:= 1 ;b1:= false
end
else if ____(4)___ then
if e[p] < >1 then
begin
p:=p+1;e[p]:=i;bj:=1;b1:=false
end
else if d[k] < >')' then
begin
p:=p+1;e[p]:=i;bj:=1;b1:=false
end
else begin
___(5)___;bj:= 1 ;b1:= false;
end
else begin
write(fh[e[p]] ,' ') ;p:=p-1
end;
until b1 = false;
end
if ___(6)___ then write(d[k] ,' ') else bj:=0;
end;
k:=k+1
end
b1:= true;
repeat
if p=0 then b1:= false
else begin
___(7)___;p:=p-1;
end
until b1 = false;
writeln;
end;
信息學(xué)初賽模擬試題（1）
（pascal語言）限時2小時完成，滿分100分
一、選擇題：（共20小題，1-15小題為單選題，每題1分；16-20小題為多選題，每題2分。共25分）
1.對存儲器按字節(jié)進(jìn)行編址，若某存儲器芯片共有10根地址線的引腳，則該存儲器芯片的存儲容量為( )。
(A) 512B (B) 1KB (C) 2KB (D)4KB (E)8KB
2.在待排序的數(shù)據(jù)表已經(jīng)為有序時，下列排序算法中花費時間反而多的是( )。
(A)堆排序 (B)希爾排序 (C)冒泡排序 (D)快速排序 (E)二分排序
3.某數(shù)列有1000個各不相同的單元，由低至高按序排列，現(xiàn)要對該數(shù)列進(jìn)行二分法檢索，在最壞的情況下，需要檢索( )單元。
(A)1000 (B)10 (C)100 (D)500 (E) 300
4.已知數(shù)組a中，每個元素a[i,j]在存儲時要占3個字節(jié)，設(shè)i從1變化到8，j從1變化到10，分配內(nèi)存實是從地址sa開始連續(xù)按行存儲分配的。試問：a[5，8]的起始地址為( )。
(A)sa+141 (B)sa+180 (C)sa+222 (D)sa+225 (E)sa+155
5.在pascal語言過程調(diào)用時，數(shù)值形參得到的是實際參數(shù)的( )。
(A) 數(shù)值 (B) 地址 (C)值 (D)變量 (E)以上都不是
6.一個24*24點陣的漢字字形信息所占的字節(jié)數(shù)為( )。
(A) 2 (B) 8 (C) 24 (D) 32 (E) 72
7. 在微機系統(tǒng)中，最基本的輸入輸出模塊BIOS存放在( ) 中。
(A) RAM (B) ROM (C) 硬盤 (D)寄存器 (E)控制器
8. 十進(jìn)制算術(shù)表達(dá)式:3*512+5*64+2*8+1的運算中,用二進(jìn)制表示為( )。
(A)1011010001 (B) 10110100011 (C) 11101010001 (D) 11110100011 (E)111000
9.設(shè)棧S的初始狀態(tài)為空,現(xiàn)對序列{1,2,3,4,5}在棧S上,依次進(jìn)行如下操作(從元素1開始,出棧后不再進(jìn)棧):進(jìn)棧,出棧,進(jìn)棧,進(jìn)棧,出棧,出棧。試問出棧的元素序列是( )。
(A){1,2,3} B) {1,3,2} C) {3,2,1} D) {2,3,1} (E)以上都不對
10.E-mail郵件本質(zhì)上是一個( )
　(A)文件 　(B)電報 　(C)電話 　(D)傳真 (E)電訊
11.一棵二叉樹的高度為h，所有結(jié)點的度為0，或為2，則此樹最少有( )個結(jié)點
　(A)2h-1 　(B)2h-1 　(C)2h+1 　(D)h+1 (E)h*h+1
12.無向圖G=(V，E)，其中V={a,b,c,d,e,f}
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}對該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點序列正確的是( )
(A)a,b,e,c,d,f　(B)a,c,f,e,b,d　(C)a,e,b,c,f,d　(D)a,b,e,d,f,c (E)以上都不對
13.pascal 編譯程序是( )
（A）. 把pascal 源程序轉(zhuǎn)換成可運行的EXE文件的程序
（B）. 把pascal 源程序轉(zhuǎn)換成等價的目標(biāo)碼的程序
（C）. 生成和修改一個pascal語言源程序的等程序
（D）. 把pascal的目標(biāo)碼程序轉(zhuǎn)換成可運行的EXE文件的程序
（E）. 生成一個等價的匯編程序
14. 將三封信投到4個郵筒，最多的投法有（ ）
（A）． 種 （B）． 種 （C）． 種 （D）．34種 E.
15. 電子信函(電子郵件)的特點之一是（ ）。
（A）.比郵政信函，電報，電話，傳真都更快
（B）.在通信雙方的計算機之間建立其直接的通信線路后即可快速傳遞數(shù)字信息
（C）.采用存儲-轉(zhuǎn)發(fā)方式在網(wǎng)絡(luò)上逐步傳遞信息,不象電話那樣直接、及時,但費用低廉
（D）.在通信雙方的計算機都開機工作的情況下即可快速傳遞數(shù)字信息
16. 以下屬于多媒體硬件的是（ ）
（A）．主機 （B）.光驅(qū) （C）.聲卡 （D）. 音箱 （E）. 超級解霸
17. 正確的二維數(shù)組類型說明是( 　)
type ar2=array[1..5,5..1] of integer;
type ar2=array[1..5] of array[5.1] of integer;
type ar2=array[1..5,1..5] of integer;
　　　 (D)type ar2=array[1..5] of array[1..5] of integer
(E)type ar2=array[1..5,1..5] of 0..1
18.下列屬于信息處理的是（ ）
（A）信息加工 （B）信息分類 （C）信息技術(shù) （D）信息采集 （E）信息存儲
19.在windows中,最小化一個應(yīng)用程序窗口后，該程序?qū)ⅲ? ）。
(A)被終止執(zhí)行 (B) 被暫停執(zhí)行 (C)被轉(zhuǎn)入后臺 (D)繼續(xù)執(zhí)行 （E）以上答案都不對
20. 下面的常量說明中，正確的是（ ）
（A）CONST （B）、CONST （C）、CONST （D）、CONST （E）CONST
t = true b, C = 45 M = 100，15 N = 1 OR 2 a= ’A’
二、問題求解：（第1小題5分，第2-3小題各4分,共13分）
[問題1]: 在所有三位數(shù)中，各位數(shù)字從高位到低位順次減小的數(shù)共有 個。
[問題2]："銀條"
一位銀礦勘探員無力預(yù)付3月份的房租。他有一根長31英寸的純銀條，因此他和女房東達(dá)成如下協(xié)議。他說，他將把銀條切成小段。3月份的第一天，他給女房東1英寸長的一段，然后每天給她增加1英寸，以此作為抵押。勘探員預(yù)期到3月份的最后一天，他能全數(shù)付清租金，而屆時女房東將把銀條小段全部還給他。3月份有31天，一種辦法是把銀條切成31段，每段長1英寸。可是這處花很多功夫。勘探員希望既履行協(xié)議，又能使銀條的分段數(shù)目盡量減少。例如，他可以第一天給女房東1英寸的一段，第二天再給1英寸的一段，第三開他取回這兩段1英寸的而給她3英寸的一段。假設(shè)銀條的各段是按照這種方式來回倒換的話，勘探員至少需要把他的銀條切成______段？
[問題3]:"換不開的鈔票"
錢柜里有1.15美分，一位顧客提出：把1美元的鈔票換成硬幣，但出納小姐說換不開，后來這位顧客提出：把50美分的鈔票換成硬幣，但出納小姐又說換不開，而實際上，出納小姐也無法把25美分、10美分、5美分的鈔票換成硬幣。請問錢柜里到底有哪些硬幣？他們分別有多少枚？
答：_________________。
三、寫出程序的運行結(jié)果：（每小題6分，共30分）
1. program text1;
const n=6;m=3;
var i,j,k:integer;
begin
for i:=-n to n do
begin
k:=n-abs(i);
write(' ': 39-k);
for j:=-k to k do
if abs(j)>k-m
then write(n-(i+n)div 2)
else write(' ');
writeln;
end;
end.
輸出的結(jié)果為：
2. PROGAM text2；
VAR a:ARRAY[1..10] OF Char；
k:Integer； ch:Char；
BEGIN
FOR k:=1 TO 10 DO a[k]:=Chr(Ord('A')+k)；
FOR k:=1 TO 10 DO
BEGIN
ch:=a[k]；
a[k]:=a[11-k]；
a[11-k]:=ch；
END；
FOR k:=1 TO 10 DO Write(a[k])；
Writeln
END.
輸出的結(jié)果為：
3. program text3(input,output);
Var m,n,p:integer;
x:real;
procedure mm(var m:integer;x:real);
var n:integer;
begin
m:=m+1;
n:=m+1;
x:=n*3;
p:=n;
end;
begin
m:=8;n:=5;p:=3;x:=1.0;
mm(n,x);
writeln (m:5,n:5,p:5,x:6:1);
end.
輸出的結(jié)果為：
4. program text4;
const n=5;
type ary=array[0..n-1,0..n-1]of integer;
var a:ary;i,j,k:integer;
begin
　for i:=0 to n-1 do
for j:=0 to n-1 do a[i,j]:=0;
k:=1;
　　for i:=1 to n do
　 for j:=n-1 downto i do
　　 　begin
　　　　　a[j,j-i]:=k;
　　　　　k:=k+1;
　　　end;
　　　for i:=0 to n-1 do
begin　
　 for j:=0 to n-1 do
write(a[I,j]:4);
writeln;
end;
　　end.
　　輸出的結(jié)果為：
5.program text5(input,output);
var ch:char;
i,n,sum:integer;
begin sum:=0;
read(ch);
case ch of
　'A':for i:=4 to 6 do
　　　begin
　　　　　read(n):
　　　　　sum:=sum＋n
　　 end;
　'B'：begin read(n);
　　　　　for i:=1 to n do
　　 　　　begin read(n);sum:=sum＋n end;
　　　　 end;
　'C':repeat
　 read(n);sum:=sum＋n
　 until sum>10;
　'D':begin read(n);
　 　　　while n<=3 do
　 　 　　　begin sum:=sum＋n;read(n) end
　 　　 end
　end;　writeln(sum:4)
end.
當(dāng)程序運行
輸入 A　4　1　2　3　4　5　6　7　8　9時，其輸出為_____________。
(2) 輸入 B　4　1　2　3　4　5　6　7　8　9時，其輸出為_____________。
(3) 輸入 C　4　1　2　3　4　5　6　7　8　9時，其輸出為_____________。
(4) 輸入 D　4　1　2　3　4　5　6　7　8　9時，其輸出為_____________。
四、完善程序（第1題每空2分第2、3題每空3分，共32分）
第1題 孿生素數(shù)是指兩個相差為2的素數(shù)，例如：3和5，5和7，11和13等。
下面程序可輸出15對孿生素數(shù)，其中函數(shù)q判斷整數(shù)a是否為素數(shù)。
program p(output);
var k,n:integer
function q (a:integer):booklean;
var k:integer;
flag:boolean;
begin
flag:___(1)____
k:=2
___(2)____ (k<=a div 2) and flag do
if a mod k=0 then ______(3)_______
else
k:=k+1
q:=flag
end;
begin
n:=0;
k:=2;
repeat
if q(k) and ___(4)___ then
begin
n:=n+1;
writeln(k,k+2)
end;
k:=K+1
until n=5
end.
第二題 已知有類型arr=array[1..16] of string; arr型數(shù)組a中存放著從第1屆到第16屆足球世界杯冠軍國家的名字，下面的函數(shù)可求出歷界世界杯比賽共有幾個國家曾獲得過世界杯冠軍，請?zhí)羁胀瓿伞?br/>Function text2(a:arr):integer;
var k,j,s:integer;
mult:boolean;
begin
___(5)___;
for j:=2 to 16 do
begin
k:=1;
mult:=false;
while not mult and ___(6)___ do
if ___(7)__ then mult:=ture
else k:=k+1;
if not mult then s:=___(8)___
end;
text2:=s
end;
第三題 Fibonacci（裴波那契）數(shù)列的規(guī)律是：前2個數(shù)均為1，從第3個數(shù)開始每個數(shù)等于它前面兩個數(shù)之和，即：1，1，2，3，5，8，13，21，34，55，89，144，233，377，...。已知任意一個大于0的整數(shù)可以表示為若干個互不相同的fibonacci之?dāng)?shù)和。
例如：121=89+21+8+3
下面的程序是由鍵盤輸入一個正整數(shù)n，輸出組成n的互不相同的fibonacci數(shù)。
例如：若輸入121
則輸入121=+89+21+8+3
本程序的算法如下：（n=121為例）
1）尋找小于或等于n的最大的fibonacci數(shù)a（例如89），并以a作為組成n的一個數(shù)輸出。
2）若n≠a則以n-a作為新的任意正整數(shù)（例如32），重復(fù)步驟1.若n=a，則結(jié)束。程序中的函數(shù)find返回小于或等于n的最大的fibonacci數(shù)。
program text3(input,output);
var n:integer;
function find(n:integer):integer;
var a,b,c:integer;
begin
a:=1; b:=1;
repeat
c:=___(9)___; a:=b;b:=c;
until b>=n;
if b=n then find:=___(10)___
else find:=___(11)___
end;
procedure p(n:integer);
var a:integer;
begin
a:=find(n); write('+',a:4);
if ap ___(12)___
end;
begin
readln(n);
write(n:5,'=');
p(n);
writeln
end.
信息學(xué)競賽初賽模擬試題（2）
（初中組PASCAL語言，兩小時完成）
選擇題：（選出每題正確的一個答案代碼，填在橫線上，每題1.5分，共30分）
1、執(zhí)行下列二進(jìn)制算術(shù)加運算11001001+00100111（ ）。
A. 11101111 B. 11110000 C. 00000001 D. 10100010
2、假設(shè)a1，a2，a3是布爾變量，且值均為True，則下列表達(dá)式中值為False的是______
A. NOT a1 AND NOT a2 B. a1 OR a2 AND a3
C. (NOT a1 OR a2)AND (a2 OR a3) D. False OR a1 AND a2 OR NOT a3
3、若一個問題的求解既可以用遞歸算法，也可以用遞推算法，則往往用_____算法。
A.先遞歸后遞推 B. 先遞推后遞歸 C.遞歸 D.遞推
4、表達(dá)式8 MOD (2*(5-3*(4*(5 DIV 2))DIV 10))的值是_____
A. 0 B. 1 C. 2 D. 3
5、貪婪法是一種______的算法。
A.不求最優(yōu)，只求滿意 B.只求最優(yōu)
C.求取全部可行解 D.求取全部最優(yōu)解
6、稱一種語言為低級程序語言是由于它_____。
A.離機器特性近 B.離自然語言近
C.編程難度低 D.通用性強
7、排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素作比較，將其放入已排序序列的正確位置上的方法，稱為_____.
A. 歸并排序 B. 二分法排序 C. 冒泡排序 D.插入排序
8、若進(jìn)棧序列為3,5,7,9,進(jìn)棧過程中可以出棧，則_____不可能是一個出棧序列。
A. 7,5,3,9 B. 9,7,5,3 C.7,5,9,3 D. 9,5,7,3
9、中綴表達(dá)式(a-b)*(cd)的后綴表達(dá)式是_____.
A. abcd*- B. ab-cd C. ab-*cd D. a-bcd *
10、字符A、B、C依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成多少個不同的字符串？_____
A. 5 B. 4 C. 6 D. 1
11、一個字長的二進(jìn)制位數(shù)是_____
A.8 B.16 C.32 D.隨計算機系統(tǒng)而不同的
12、當(dāng)a=1,b=3,c=5,d=4時，執(zhí)行下面一段程序后，x的值為_____
if(a else if(a if(b else x=3;
else x=6;
else x=7;
A. 1 B.2 C. 3 D. 6
13、若一個存儲器的周期為200ns，且每個周期可訪問4個字節(jié)，則該存儲器帶寬為____bit/s。
A.20M B.40M C.80M D.160M
14、在WWW頁面訪問時，瀏覽器通過網(wǎng)絡(luò)與該 IP地址處的WEB服務(wù)器的_____服務(wù)端口間建立一條TCP連接。
A. HTML B. HTTP C. SMTP D. DNS
15、MIDI是一種數(shù)字音樂的國際標(biāo)準(zhǔn)，MIDI文件存儲的____________。
A.不是樂譜而是波形 B.不是波形而指令序列
C.不是指令序列而是波形 D.不是指令序列而是樂譜
16、已知公式：
2 （x=0）
fun（x）= 1 （x=1）
fun（x-1）+x*fun（x-2）（x>1）
則fun(4)的值是_______
A.25 B.30 C.33 D. 28
17、在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒_____
A. 左子結(jié)點 B. 右子結(jié)點
C. 左子結(jié)點和右子結(jié)點 D. 左子結(jié)點、右子結(jié)點和兄弟結(jié)點
18、一棵含有101個結(jié)點的完全二叉樹存儲在數(shù)組A[1..101]中,對1≤k≤101,若 A[k]是葉子結(jié)點,則
k的最小值是______。
51 B. 50 C. 49 D. 48
19、已知數(shù)組A中，每個元素A[I,J]在存儲時要占３個字節(jié)，設(shè)I從0變化到８，J從１變化到1０，分配內(nèi)存時是從地址SB開始連續(xù)按行分配的．試問：A[4,8]的起始地址為_____．
A. SB+141 B. SB+180 C. SB+142 D. SB+181
20、下面關(guān)于圖的存儲的敘述中正確的是______。
A. 用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)。
B. 用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)。
C. 用鄰接表法存儲圖，占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)。
D. 用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)。
二、問題解答：(4+6=10分)
將一支鉛筆、一枝原子筆和一個橡皮擦分別放入A、B、C三位女孩的筆盒中，每個筆盒只能放一種文具，且三個筆盒內(nèi)放的文具都不相同。下列三句敘述中只有一句為真，其余二句為假。試問哪一句為真？_____
①A的筆盒中放的是鉛筆。
②B的筆盒中沒有鉛筆。
③C的筆盒中沒有橡皮擦。
小娟喜歡收集布偶，她將紅、藍(lán)、黃色的趴趴熊、kitty貓、狗布偶各1只（共9只）排成三行三列的方陣，然后請她的北北來猜。小娟提示說：
①紅色的動物都在第一列。
②黃色的動物都不在第三列。
③kitty貓只能在四個角或正中間。
④趴趴熊只能在第一行最上面二個位置或在第三行最下面一個位置。
第二行最下面一個位置放的是_______顏色的______布偶。
三、看程序?qū)懡Y(jié)果：(8+10+12=30分)
1.var x,y:integer;
function gcd(x,y:integer):integer;
var r:integer;
begin
repeat
r:=x mod y;
x:=y;
y:=r;
until r=0;
gcd:=x;
end;
begin
x:=80;y:=98;
writeln(x*y div gcd(x,y));
end.
輸出：
2. const n=12;
var i,j:integer;
list:array[0..n] of integer;
begin
for i:=1 to n do read(list[i]);
for i:=2 to n do
begin
list[0]:=list[i];
j:=i-1;
while list[0]begin
list[j+1]:=list[j];
dec(j);
end;
list[j+1]:=list[0];
end;
for i:=1 to n do write(list[i]:5);
end.
輸入：67 98 7823 2332 2323 64 90 -34 121 -98 22 67
輸出：
3. var i,j,k,n:integer;
a:array[1..100,1..100] of integer;
begin
readln(n);
k:=1;
i:=1;j:=1;a[i,j]:=1;
while kbegin
if (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 begin inc(i);dec(j);end;
inc(k);a[i,j]:=k;
end;
writeln(i,'/',j);
end.
輸入：1999
輸出：
四、程序填空：(12+18=30分)
1、一個數(shù)如果正好等于其因子之和，就稱其為“完數(shù)”。例如6的因子是1，2，3，并且6=1+2+3，所以6是一個“完數(shù)”。下面的程序可以輸出2──n之間的所有完數(shù)之和。其中n為2~1000之間的任意整數(shù)。請將程序填寫完全。
PROGRAM bs1；
VAR a，n，s:Integer；
FUNCTION func(n:Integer)：Boolean；
VAR s，k:Integer；
BEGIN
s:=0；
FOR k:=1 TO ① DO
IF n MOD k=0 THEN s:= ② ；
IF ③ THEN func:=True
ELSE func:=False
END；

BEGIN
s:=0；Readln(n)；
FOR a:=2 TO n DO
IF func ④ THEN s:=s+a；
Writeln(s)
END.
2.本程序的功能是將中綴表示的算術(shù)表達(dá)式轉(zhuǎn)換成后綴表示。如中綴表達(dá)式(A-(B*C+D)*E)/(F+G)的后綴表示為ABC*D+E*-FG+/
為了方便，假定變量名為單個英語字母，運算符只有＋－×/（均為雙目運算符，左結(jié)合），并假定所提供的算術(shù)表達(dá)式非空且語法是正確的。另外，中綴表示形式中無空格符，但整個算術(shù)表達(dá)式以空格符結(jié)束。各數(shù)組意義如下：
POLISH[] 存儲其后綴表示;
s[] 是一個后進(jìn)先出棧。
函數(shù) PRIOR(CHAR)返回符號CHAR的優(yōu)先級，各符號的優(yōu)先級如下表示：
CHAR PRIOR(CHAR)
* / 4
+ - 3
( 2
) 1
label 10;
var
input:string;
polish,s:array[1..100] of char;
k,p,i:integer;
function prior(ch:char) : integer;
begin
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;
begin
input:='(A-(B*C+D)*E)/(F+G)';
k:=0;p:=0;i:=1;
while i<=length(input) do
begin
if (input[i]='+') or (input[i]='-') or (input[i]='*') or (input[i]='/') then
begin
while p<>0 do
begin
if ⑥ then b else goto 10 ;
end;
10: a;
end
else if input[i]='(' then
begin
a;
end
else if input[i]=')' then
begin
while s[p]<>'(' do b;
p:=p-1;
end
else
begin
k:=k+1;
polish[k]:=input[i];
end;
i:=i+1;
end;
while p<>0 do b;
writeln(polish);
end.
2、program t2;
var
a:array[0..8] of char;
i: integer;
begin
for i:= 1 to 8 do a[i]:=char(i * 2 +ord('A'));
for i:= 1 to 4 do begin
a[0]:=a[i];
a[i]:=a[9-i];
a[9-i]:=a[0];
end;
for i:= 1 to 8 do write(a[i]);
writeln;
end.
輸出：______
4、program t4;
var
a,d:array[1..100] of integer;
n ,i ,j ,k,x ,s :integer;
begin
n:=5;a[1]:=1;d[1]:=1;
for i:=1 to n do
begin
s:=i+1;x:=0;
for j:=1 to n+1-i do
begin
k:=s+x;x:=x+1;a[j+1]:=a[j]+k;
write(a[j],' ');
end;
writeln('...');
d[i+1]:=d[i]+i;a[1]:=d[i+1];
end;
end.
輸出：_________
6、program t6;
const a: array[1..14] of longint =(94,32,40,90,99,80,46,21,69,28,64,73,85,54);
var
i, j, k, m,left, right, temp: longint;
begin
m:=8; left:= 1; right:= 14;
while left < right do
begin
k:=a[m]; i:=left; j:=right;
repeat
while k < a[j] do j:=j-1;
while k > a[i] do i:=i+1;
if i <= j then
begin
temp:=a[i]; a[i]:=a[j];
a[j]:=temp; i:=i+1; j:=j -1;
end
until i > j;
if j < m then left:=i;
if i > m then right:=j
end;
writeln(a[m]);
end.
輸出：_______
8、program t8;
var
m ,n,s: longint;
procedure pl(n: longint);
begin
if n< >0 then
begin
pl(n div 2);
s:=(s*2+n mod 2 *m) mod 1023
end
end;
begin
m:=2002; n:=5871;
s:=0; pl(n); writeln(s);
end.
輸出：_______

展開更多......

收起↑