（提高組 PASCAL語言 二小時完成）
審定：全國青少年信息學奧林匹克競賽科學委員會
主管：中國科協、教育部
主辦：中國計算機學會
承辦：江蘇省科協青少年科技中心
●●全部試題答案均要求寫在答卷紙上，寫在試卷紙上壹律無效●●
壹． 選擇壹個正確答案代碼（A/B/C/D），填入每題的括號內（每題1.5分，多選無分，***30分）
1． 微型計算機的問世是由於（ ）的出現。
A）中小規模集成電路 B）晶體管電路 C）（超）大規模集成電路 D）電子管電路
2． 中央處理器（CPU）能訪問的最大存儲器容量取決於（ ）。
A）地址總線 B）數據總線 C）控制總線 D）實際內存容量
3． 十進制書11/128可用二進制數碼序列表示為：（ ）。
A）1011/1000000 B）1011/100000000 C）0.001011 D）0.0001011
4． 算式（2047）10 －（3FF）16 ＋（2000）8的結果是（ ）。
A）（2048）10 B）（2049）10 C）（3746）8 D）（1AF7）16
5． 已知x =（0.1011010）2 ，則[ x / 2 ]補 =（ ）2 。
A）0.1011101 B）11110110 C）0.0101101 D）0.100110
6． IPv4地址是由（ ）位二進制數碼表示的。
A）16 B）32 C）24 D）8
7． 計算機病毒傳染的必要條件是：（ ）。
A）在內存中運行病毒程序 B）對磁盤進行讀寫操作
C）在內存中運行含有病毒的可執行的程序 D）復制文件
8． 在磁盤上建立子目錄有許多優點，下列描述中不屬於建立子目錄優點的是（ ）。
A）便於文件管理 B）解決根目錄中目錄項個數有限問題
C）加快文件查找速度 D）節省磁盤使用空間
9． 在使用E-mail前，需要對Outlook進行設置，其中ISP接收電子郵件的服務器稱為（ ）服務器。
A）POP3 B）SMTP C）DNS D）FTP
10．多媒體計算機是指（ ）計算機。
A）專供家庭使用的 B）裝有CD-ROM的
C）連接在網絡上的高級 D）具有處理文字、圖形、聲音、影像等信息的
11．微型計算機中，（ ）的存取速度最快。
A）高速緩存 B）外存儲器 C）寄存器 D）內存儲器
12．資源管理器的目錄前圖標中增加“+”號，這個符號的意思是（ ）。
A）該目錄下的子目錄已經展開 B）該目錄下還有子目錄未展開
C）該目錄下沒有子目錄 D）該目錄為空目錄
13．在WORD文檔編輯中實現圖文混合排版時，關於文本框的下列敘述正確的是（ ）。
A）文本框中的圖形沒有辦法和文檔中輸入文字疊加在壹起，只能在文檔的不同位置
B）文本框中的圖形不可以襯於文檔中輸入的文字的下方
C）通過文本框，可以實現圖形和文檔中輸入的文字的疊加，也可以實現文字環繞
D）將圖形放入文本框後，文檔中輸入的文字不能環繞圖形
14．壹個向量第壹個元素的存儲地址是100，每個元素的長度是2，則地5個元素的地址是（ ）。
A）110 B）108 C）100 D）109
15．已知A = 35H，A /\ 05H \/ A /\ 30H 的結果是：（ ）。
A）30H B）05H C）35H D）53H
16．設有壹個含有13個元素的Hash表（0 ~ 12），Hash函數是：H（key）= key % 13，，其中%是求余數運算。用線性探查法解決沖突，則對於序列（2、8、31、20、19、18、53、27），18應放在第（ ）號格中。
A）5 B）9 C）4 D）0
17．按照二叉數的定義，具有3個結點的二叉樹有（ ）種。
A）3 B）4 C）5 D）6
18．在壹個有向圖中，所有頂點的入度之和等於所有頂點的出度之和的（ ）倍。
A）1/2 B）1 C）2 D）4
19．要使1 ．．．8號格字的訪問順序為：8、2、6、5、7、3、1、4，則下圖中的空格中應填入（ ）。
1 2 3 4 5 6 7 8
4 6 1 -1 7 3 2
A）6 B）0 C）5 D）3
20．設棧S和隊列Q的初始狀態為空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通過棧S，壹個元素出棧後即進入隊列Q，若出隊的順序為e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，則棧S的容量至少應該為（ ）。
A）2 B）3 C）4 D）5
二．問題求解：（6 + 8 = 14分）
1． 在書架上放有編號為1 ，2 ，．．．，n的n本書。現將n本書全部取下然後再放回去，當放回去時要求每本書都不能放在原來的位置上。例如：n = 3時：
原來位置為：1 2 3
放回去時只能為：3 1 2 或 2 3 1 這兩種
問題：求當n = 5時滿足以上條件的放法***有多少種？（不用列出每種放法）
2． 設有壹棵k叉樹，其中只有度為0和k兩種結點，設n 0 ，n k ，分別表示度為0和度為k的結點個數，試求出n 0 和n k之間的關系（n 0 = 數學表達式，數學表達式僅含n k 、k和數字）。
三．閱讀程序，寫出正確的程序運行結果：（8 + 9 + 9 = 26分）
1． program Gxp1;
var i , n , jr , jw , jb : integer ;
ch1 : char ;
ch : array[1..20] of char ;
begin
readln(n);
for i:=1 to n do read(ch[i]);
jr:=1; jw:=n; jb:=n;
while (jr<=jw) do
begin
if (ch[jw]=’R’)
then begin
ch1:=ch[jr]; ch[jr]:=ch[jw]; ch[jw]:=ch1; jr:=jr+1;
end
else if ch[jw]=’W’
then jw:=jw-1;
else begin
ch1:=ch[jw]; ch[jw]:=ch[jb]; ch[jb]:=ch1; jw:=jw-1; jb:=jb-1;
end
end;
for i:=1 to n do write(ch[1]);
writeln;
end.
輸入：10
RBRBWWRBBR
輸出：
2． program Gxp2;
var i , j , s ,sp1 : integer ;
p : boolean ;
a : array[1..10] of integer ;
begin
sp1:=1; a[1]:=2; j:=2;
while sp1<10 do
begin
j:=j+1; p:=true;
for i:=2 to j-1 do
if (j mod i=0) then p:=false;
if p then begin
sp1:=sp1+1; a[sp1]:=j;
end;
end;
j:=2; p:=true;
while p do
begin
s:=1;
for i:=1 to j do s:=s*a[i];
s:=s+1;
for i:=2 to s-1 do
if s mod i=0 then p:=false;
j:=j+1;
end;
writeln(s); writeln;
end.
輸出：
3． Program Gxp2
Var d1 , d2 , X , Min : real ;
begin
Min:=10000; X:=3;
while X<15 do
begin
d1:=sqrt(9+(X-3)*(X-3)); d2:=sqrt(36+(15-X)*(15-X));
if(d1+d2)<Min then Min:=d1+d2;
X:=x+0.001;
end;
writeln(Min:10:2);
end.
輸出：
四．完善程序：（15 + 15 = 30分）
1． 問題描述：工廠在每天的生產中，需要壹定數量的零件，同時也可以知道每天生產壹個零件的生產單價。在N天的生產中，當天生產的零件可以滿足當天的需要，若當天用不完，可以放到下壹天去使用，但要收取每個零件的保管費，不同的天收取的費用也不相同。
問題求解：求得壹個N天的生產計劃（即N天中每天應生產零件個數），使總的費用最少。
輸入：N（天數 N<=29）
每天的需求量（N個整數）
每天生產零件的單價（N個整數）
每天保管零件的單價（N個整數）
輸出：每天的生產零件個數（N個整數）
例如：當N=3時，其需要量與費用如下：
第壹天 第二天 第三天
需 要 量 25 15 30
生產單價 20 30 32
保管單價 5 10 0
生產計劃的安排可以有許多方案，如下面的三種：
第壹天 第二天 第三天 總的費用
25 15 30 25*20+15*30+30*32=1910
40 0 30 40*20+15*5+30*32=1835
70 0 0 70*20+45*5+30*10=1925
程序說明：
b[n]：存放每天的需求量
c[n]：每天生產零件的單價
d[n]：每天保管零件的單價
e[n]：生產計劃
程序：
program exp5;
var
i,j,n,yu,j0,j1,s : integer ;
b,c,d,e : array[0..30] of integer ;
begin
readln(n);
for i:=1 to n do readln(b[i],c[i],d[i]);
for i:=1 to n do e[i]:=0;
①__________:=10000; c[n+2]=0; b[n+1]:=0 j0:=1;
while (j0<=n) do
begin
yu:=c[j0]; j1:=j0; s:=b[j0];
while ②__________ do
begin
③__________ j1:=j1+1; s:=s+b[j1];
end;
④__________ j0:=j1+1;
end;
for i:=1 to n do ⑤__________
readln;
end.
二．問題描述：有n種基本物質（n≤10），分別記為P1，P2，……，Pn，用n種基本物質構造物質，這些物品使用在k個不同地區（k≤20），每個地區對物品提出自己的要求，這些要求用壹個n位的數表示：a1a2……a n，其中：
ai = 1表示所需物質中必須有第i種基本物質
= -1表示所需物質中必須不能有第i種基本物質
= 0無所謂
問題求解：當k個不同要求給出之後，給出壹種方案，指出哪些物質被使用，哪些物質不被使用。
程序說明：數組 b[1],b[2]……b[n] 表示某種物質
a[1..k,1..n] 記錄k個地區對物品的要求，其中：
a[i,j]=1 表示第i個地區對第j種物品是需要的
a[i,j]=0 表示第i個地區對第j種物品是無所謂的
a[i,j]= -1 表示第i個地區對第j種物品是不需要的
程序：
program gxp2;
var
i,j,k,n : integer ;
p : boolean ;
b : array[0..20] of 0..1 ;
a : array[1..20,1..10] of integer ;
begin
readln(n,k);
for i:=1 to k do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
for i:=0 to n do b[i]:=0;
p:=true;
while ①__________ do
begin
j:=n;
while b[j]=1 do j:=j-1;
②__________
for i:=j+1 to n do b[i]:=0;
③__________
for i:=1 to k do
for j:=1 to n do
if (a[i,j]=1) and (b[j]=0) or ④__________
then p:=true;
end;
if ⑤__________
then writeln(‘找不到！’)
else for i:=1 to n do
if (b[i]=1) then writeln(‘物質’,i,’需要’)
else writeln(‘物質’,i,’不需要’);
end.