資源簡介

第十三屆全國青少年信息學奧林匹克聯賽初賽試題
（ 提高組 Pascal 語言 二小時完成 ）

●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●



一、 單項選擇題 （共 10 題，每題 1.5 分，共計 15 分。每題有且僅有一個正確答案.）。


1. 在以下各項中。（ ）不是 CPU 的組成部分。
A. 控制器 B. 運算器 C. 寄存器 D. 主板 E. 算術邏輯單元(ALU)


2. 在關系數據庫中, 存放在數據庫中的數據的邏輯結構以( )為主。
A. 二叉樹 B. 多叉樹 C. 哈希表 D. B+樹 E. 二維表


3.在下列各項中，只有（ ）不是計算機存儲容量的常用單位。
A. Byte B. KB C. MB D. UB E. TB


4．ASCII碼的含義是（ ）。
A. 二—十進制轉換碼 B. 美國信息交換標準代碼 C. 數字的二進制數碼
D. 計算機可處理字符的唯一編碼 E. 常用字符的二進制編碼


5．在 Pascal 語言中，表達式 (23 or 2 xor 5)的值是（ ）

A. 18 B. 1 C.23 D.32 E.24


6．在 Pascal 語言中，判斷整數a 等于 0 或b等于 0或c等于0 的正確的條件表達式是（ ）
A. not ((a<>0) or (b<>0) or (c<>0))
B. not ((a<>0) and (b<>0) and (c<>0))
C. not ((a=0) and (b=0)) or (c=0)
D.(a=0) and (b=0) and (c=0)
E. not ((a=0) or (b=0) or (c=0))
7. 地面上有標號為A、B、C的3根細柱, 在A柱上放有10個直徑相同中間有孔的圓盤, 從上到下次依次編號為1, 2, 3, ……，將A柱上的部分盤子經過B柱移入C柱, 也可以在B柱上暫存。如果B柱上的操作記錄為：“進，進，出，進，進，出，出，進，進，出，進，出，出”。那么, 在C柱上, 從下到上的盤子的編號為（ ）。
A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6
D. 2 4 3 6 7 5 E. 2 1 4 3 7 5

8. 與十進制數17.5625相對應的8進制數是（ ）。
A. 21.5625 B. 21.44 C. 21.73
D. 21.731 E. 前4個答案都不對

9. 歐拉圖G是指可以構成一個閉回路的圖，且圖G的每一條邊恰好在這個閉回路上出現一次（即一筆畫成）。在以下各個描述中, 不一定是歐拉圖的是：（ ）。
A. 圖G中沒有度為奇數的頂點
B. 包括歐拉環游的圖(歐拉環游是指通過圖中每邊恰好一次的閉路徑)
C. 包括歐拉閉跡的圖(歐拉跡是指通過途中每邊恰好一次的路徑)
D. 存在一條回路, 通過每個頂點恰好一次
E. 本身為閉跡的圖

10. 一個無法靠自身的控制終止的循環稱為“死循環”，例如在C語言程序中，語句“while(1)printf("*")；”就是一個死循環，運行它將無休止地打印*號。下面關于死循環的說法中, 只有（ ）是正確的。
A. 不存在一種算法, 對任何一個程序及相應的輸入數據, 都可以判斷是否會出現死循環, 因而, 任何編譯系統都不做死循環檢查
B. 有些編譯系統可以檢測出死循環
C. 死循環屬于語法錯誤， 既然編譯系統能檢查各種語法錯誤， 當然也能檢查出死循環
D. 死循環與多進程中出現的“死鎖”差不多，而死鎖是可以檢測的，因而，死循環也是可以檢測的
E. 對于死循環，只能等到發生時做現場處理, 沒有什么更積極的手段

二、 不定項選擇題 （共 10 題，每題 1.5 分，共計 15 分。每題正確答案的個數大于或等于 1。多選或少選均不得分）。


11. 設A=B=true，C=D=false，以下邏輯運算表達式值為真的有（ ）。
A. (﹁A∧B)∨(C∧D∨A) B. ﹁ ( ( (A∧B)∨C)∧D)
C. A∧(B∨C∨D)∨D D. (A∧(D∨C)) ∧B


12. 命題“P→Q”可讀做P蘊含Q， 其中P、Q是兩個獨立的命題. 只有當命題P成立而命題Q不成立時， 命題"P→Q"的值為false， 其它情況均為true. 與命題"P→Q"等價的邏輯關系式是（ ）。
A. ﹁ P∨Q B. P∧Q C. ﹁ (P∨Q) D. ﹁(﹁Q∧P )
13. (2070)16+(34)8的結果是（ ）。
A. (8332)10 B. (208C)16

C. (100000000110)2 D. (20214)8


14. 已知7個節點的二叉樹的先根遍歷是1 2 4 5 6 3 7(數字為結點的編號，以下同)， 后根遍歷是4 6 5 2 7 3 1， 則該二叉樹的可能的中根遍歷是（ ）由收集 ( http: / / www. / " \t "_blank )
A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7
C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3

15. 冗余數據是指可以由以他數據導出的數據，例如，數據庫中已存放了學生的數學、語文、和英語的三科成績，如果還存放三科成績的總分，則總分就可以看做冗余數據。冗余數據往往會造成數據的不一致，例如上面4個數據如果都是輸入的，由于操作錯誤使總分不等于三科成績之和，就會產生矛盾。下面關于冗余數據的說法中， 正確的是（ ）。
A. 應該在數據庫中消除一切冗余數據
B. 與用高級語言編寫的數據處理系統相比， 用關系數據庫編寫的系統更容易消除冗余數據
C. 為了提高查詢效率， 在數據庫中可以適當保留一些冗余數據， 但更新時要做相容性檢驗
D. 做相容性檢驗會降低效率， 可以不理睬數據庫中的冗余數據

16.在下列各軟件中，屬于 NOIP 競賽（復賽）推薦使用的語言環境有（ ）。

A. gcc B. g++
C. Turbo C D. free pascal

17. 以下斷電之后將仍能保存數據的有（ ）。
A. 硬盤 B. ROM C. 顯存 D. RAM


18. 在下列關于計算機語言的說法中，正確的有（ ）。
A. 高級語言比匯編語言更高級， 是因為它的程序的運行效率更高
B. 隨著Pascal、C等高級語言的出現， 機器語言和匯編語言已經退出了歷史舞臺
C. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上
D. C是一種面向過程的高級計算機語言

19. 在下列關于算法復雜性的說法中， 正確的有（ ）。
A. 算法的時間復雜度，是指它在某臺計算機上具體實現時的運行時間
B. 算法的時間復雜度，是指對于該算法的一種或幾種主要的運算， 運算的次數與問題的規模之間的函數關系
C. 一個問題如果是NPC類的， 就意味著在解決該問題時， 不存在一個具有多項式時間復雜度的算法. 但這一點還沒有得到理論上證實，也沒有被否定
D. 一個問題如果是NP類的，與C有相同的結論 由收集 ( http: / / www. / " \t "_blank )


20. 近20年來， 許多計算機專家都大力推崇遞歸算法，認為它是解決較復雜問題的強有力的工具. 在下列關于遞歸的說法中， 正確的是（ ）。
A. 在1977年前后形成標準的計算機高級語言"FORTRAN77"禁止在程序使用遞歸， 原因之一是該方法可能會占用更多的內存空間.
B. 和非遞歸算法相比， 解決同一個問題， 遞歸算法一般運行得更快一些
C. 對于較復雜的問題， 用遞歸方式編程往往比非遞歸方式更容易一些
D. 對于已定義好的標準數學函數sin(x)， 應用程序中的語句“y=sin(sin(x));”就是一種遞歸調用

三．問題求解（共 2 題，每題 5 分，共計 10 分）


1．給定n個有標號的球，標號依次為1，2，…，n。將這n個球放入r個相同的盒子里，不允許有空盒，其不同放置方法的總數記為S(n,r)。例如，S(4,2)=7，這7種不同的放置方法依次為{(1) , (234)} , {(2) , (134)} , {(3) , (124)} , {(4) , (123)} , {(12) , (34)} , {(13) , (24)} , {(14) , (23)}。當n=7，r=4時，S(7,4)= 。


2．N個人在操場里圍成一圈，將這N個人按順時針方向從1到N編號，然后從第一個人起，每隔一個人讓下一個人離開操場，顯然，第一輪過后，具有偶數編號的人都離開了操場。依次做下去，直到操場只剩下一個人，記這個人的編號為J(N)，例如，J(5)=3，J(10)=5，等等。
則J(400)= 。
（提示：對N=2m+r進行分析，其中0≤r<2m）。



四．閱讀程序寫結果（共 4 題，每題 8 分，共計 32 分）


1. program s401;
var p,q:array[0..5] of integer;
i,x,y:integer;
begin
y:=20;
for i:=0 to 4 do read(p[i]);
readln;
q[0]:=(p[0]+p[1])+(p[2]+p[3]+p[4]) div 7;
q[1]:=p[0]+p[1] div ((p[2]+p[3]) div p[4]);
q[2]:=p[0]*p[1] div p[2];
q[3]:=q[0]*q[1];
q[4]:=q[1]+q[2]+q[3];
x:=(q[0]+q[4]+2)-p[(q[3]+3) mod 4];
if (x>10) then
y:=y+(q[1]*100-q[3]) div (p[p[4] mod 3]*5)
else
y:=y+20+(q[2]*100-q[3]) div (p[p[4] mod 3]*5);
writeln(x,',',y);
end.
/*注：本例中，給定的輸入數據可以避免分母為 0 或下標越界。由收集 ( http: / / www. / " \t "_blank ) */
輸入：6 6 5 5 3
輸出：


2. program s402;
var a,b:integer;
x,y:^integer;
procedure fun(a,b:integer);
var k:integer;
begin
k:=a; a:=b; b:=k;
end;
begin
a:=3; b:=6;
x:=@a; y:=@b;
fun(x^,y^);
write('No.1:',a,',',b,' ');
fun(a,b);
writeln('No.2:',a,',',b);
end.
輸出:



3. program S403;
var a1:array[1..50] of integer;
var i,j,t,t2,n,n2:integer;
begin
n:=50;
for i:=1 to n do a1[i]:=0;
n2:=round(sqrt(n));
for i:=2 to n2 do
if(a1[i]=0) then
begin
t2:=n div i;
for j:=2 to t2 do a1[i*j]:=1;
end;
t:=0;
for i:=2 to n do
if (a1[i]=0) then
begin
write(i:4); inc(t);
if(t mod 10=0) then writeln;
end;
writeln;
end.
輸出：




4. program S404;
const n=12;
ch2:array[0..12] of char
=('q','A','S','O','R','T','E','X','A','M','P','L','E');
var k:integer;
ch:array[0..12] of char;
procedure shift(k,n:integer);
var v:char;
j:integer;
begin
v:=ch[k]; j:=k+k;
while (j<=n) do
begin
if (jif (ord(v)begin ch[j div 2]:=ch[j]; j:=j*2; end
else
exit;
ch[j div 2]:=v;
end;
end;
procedure hpsrt;
var k:integer;
tmp:char;
begin
for k:=n div 2 downto 1 do shift(k,n);
write('No.1: ');
for k:=1 to n do write(ch[k]);
writeln;
for k:=n downto 1 do
begin
tmp:=ch[1]; ch[1]:=ch[k]; ch[k]:=tmp;
shift(1,k-1);
end;
end;
begin
for k:=0 to n do ch[k]:=ch2[k];
hpsrt;
write('No.2: ');
for k:=1 to n do write(ch[k]);
writeln;
end.
輸出：


五．完善程序 (前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分)


1．(格雷碼 Gray Code) 由收集 ( http: / / www. / " \t "_blank )
Gray Code是一種二進制編碼，編碼順序與相應的十進制數的大小不一致。其特點是，對于兩個相鄰的十進制數，對應的兩個格雷碼只有一個二進制位不同。另外，最大數與最小數間也僅有一個二進制位不同，以4位二進制數為例，編碼如下：
十進制數 格雷碼 十進制數 格雷碼
0 0000 8 1100
1 0001 9 1101
2 0011 10 1111
3 0010 11 1110
4 0110 12 1010
5 0111 13 1011
6 0101 14 1001
7 0100 15 1000
如果把每個二進制的位看做一個開關，則將一個數變為相鄰的另一個數，只須改動一個開關。因此，格雷碼廣泛用于信號處理、數-模轉換等領域。
下面程序的任務是：由鍵盤輸入二進制的位數n(n<16)，再輸入一個十進制數m(0≤m<2n)，然后輸出對應于m的格雷碼(共n位，用數組gr[ ]存放)
program s501;
var bound，m，n，i，j，b，p:integer;
gr:array[0..14]of integer;
begin
bound:=1;
writeln('input n，m');
readln(n，m);
for i:=1 to n do bound:=[ ① ];
if (m<0)or(m>=bound) then
begin
writeln('Data error!');
[ ② ];
end;
b:=1;
for i:=1 to n do
begin
p:=0; b:=b*2;
for[ ③ ] to m do
if ([ ④ ] ) then
p:=1-p;
gr:=p;
end;
for i:=n[ ⑤ ] do
write(gr);
writeln;
end.


2．（連續郵資問題）某國發行了n種不同面值的郵票，并規定每封信上最多允許貼m張郵票。在這些約束下，為了能貼出{1，2，3，…，maxvalue}連續整數集合的所有郵資，并使maxvalue的值最大，應該如何設計各郵票的面值 例如，當n=5和m=4時，面值設計為（1，3，11，15，32），可使maxvalue達到最大值70（或者說,用這些面值的1至4張郵票可以表示不超過70的所有郵資，但無法表示郵資71）。而用其他面值的1至4張郵票如果可以表示不超過k的所有郵資，必有k≤70）由收集 ( http: / / www. / " \t "_blank )
下面是用遞歸回溯求解連續郵資問題的程序。數組x[1：n]表示n種不同的郵票面值，并約定各元素按下標是嚴格遞增的。數組bestx[1：n]存放使maxvalue達到最大值的郵票面值（最優解），數組y[maxl]用于記錄當前已選定的郵票面值x[1：i]能貼出的各種郵資所需的最少郵票張數。請將程序補充完整。
program S502;
const NN=20;
maxint=30000;
maxl=500;
var bestx,x:array [0..NN] of integer;
y:array [0..maxl] of integer;
j,n,m,maxvalue:integer;
procedure result;
var j:integer;
begin
writeln('max=',maxvalue);
for j:=1 to n do write(bestx[j]:4);
writeln;
end;
procedure backtrace(i,r:integer);
var j,k:integer;
z: array[0..maxl] of integer;
begin
for j:=0 to[ ① ]do
if (y[j]for k:=1 to m-y[j] do
if (y[j]+k<=y[ ② ]) then
y[ ③ ]:=y[j]+k;
while (y[r]if (i>n) then
begin
if (r-1>maxvalue) then
begin
maxvalue:=[ ④ ] ;
for j:=1 to n do bestx[j]:=x[j];
end;
exit;
end;
for k:=0 to maxl do z[k]:=y[k];
for j:=[ ⑤ ] to r do
begin
x[i]:=j;
[ ⑥ ];
for k:=0 to maxl do y[k]:=z[k];
end;
end;
begin
maxvalue:=0;
writeln('input n,m:');
readln(n,m);
for j:=1 to maxl do y[j]:=maxint;
y[0]:=0; x[0]:=0; x[1]:=1;
backtrace(2,1);
result;
end.
NOIP2007年提高組（Pascal語言）參考答案與評分標準
一、單項選擇題：（每題1.5分）
1. D 2. E 3. D 4. B 5. A
6. B 7. D 8. B 9. D 10. A
二、 不定項選擇題 （共10題，每題1.5分，共計15分。每題正確答案的個數大于或等于1。多選或少選均不得分）。
11. ABC 12. AD 13. ABD 14. ABD 15. BC
16. ABD 17. AB 18. CD 19. BC 20. AC
三、問題求解：（共2題，每題5分，共計10分）
1．350
2．289
四、閱讀程序寫結果（共4題，每題8分，共計32分）
1 129,43
2 No.1:3,6 No.2:3,6
3 2 3 5 7 11 13 17 19 23 29
31 37 41 43 47
4 No.1: XTORSEAAMPLE
No.2: AAEELMOPRSTX
五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)
（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學委員會審查）
1 ① bound*2
② exit
③ j:=0
④ (j mod b-(b div 2))=0
⑤ downto 1
2 ① x[i-2]*(m-1)
② j+x[i-1]*k
③ j+x[i-1]*k （同2）
④ r-1
⑤ x[i-1]+1
⑥ backtrace(i+1,r)
完整程序：
program S501;
var bound,m,n,i,j,b,p:integer;
gr:array[0..14] of integer;
begin
bound:=1;
writeln('input n,m');
readln(n,m);
for i:=1 to n do bound:=bound*2 ;
if (m<0) or(m>=bound) then
begin
writeln('Data error!');
exit ;
end;
b:=1;
for i:=1 to n do
begin
p:=0; b:=b*2;
for j:=0 to m do
if (j mod b-(b div 2))=0 then
p:=1-p;
gr[i]:=p;
end;
for i:=n downto 1 do
write(gr[i]);
writeln;
end.
program S502;
const NN=20;
maxint=30000;
maxl=500;
var bestx,x:array [0..NN] of integer;
y:array [0..maxl] of integer;
j,n,m,maxvalue:integer;
procedure result;
var j:integer;
begin
writeln('max=',maxvalue);
for j:=1 to n do write(bestx[j]:4);
writeln;
end;
procedure backtrace(i,r:integer);
var j,k:integer;
z: array[0..maxl] of integer;
begin
for j:=0 to x[i-2]*(m-1) do
if (y[j]for k:=1 to m-y[j] do
if (y[j]+k<=y[j+x[i-1]*k]) then
y[j+x[i-1]*k]:=y[j]+k;
while (y[r]if (i>n) then
begin
if (r-1>maxvalue) then
begin
maxvalue:=r-1 ;
for j:=1 to n do bestx[j]:=x[j];
end;
exit;
end;
for k:=0 to maxl do z[k]:=y[k];
for j:=x[i-1]+1 to r do
begin
x[i]:=j;
backtrace(i+1,r);
for k:=0 to maxl do y[k]:=z[k];
end;
end;
begin
maxvalue:=0;
writeln('input n,m:');
readln(n,m);
for j:=1 to maxl do y[j]:=maxint;
y[0]:=0; x[0]:=0; x[1]:=1;
backtrace(2,1);
result;
end.

展開更多......

收起↑