資源簡介

第十屆全國青少年信息學奧林匹克聯賽初賽試題
（ 提高組 Pascal 語言 二小時完成 ）
● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、 單項選擇題 （共10題，每題1.5分，共計15分。每題有且僅有一個正確答案.）。
設全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，B = {b, d, e}，C = {e, f, g}，那么集合為（ ）。
A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g}
由3個a，5個b和2個c構成的所有字符串中，包含子串“abc”的共有（ ）個。
A. 40320 B. 39600 C. 840 D. 780 E. 60
某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態為空，從這一時刻開始的出入記錄為：“進，出，進，進，出，進，進，進，出，出，進，出”。假設車輛入站的順序為1，2，3，……，則車輛出站的順序為（ ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7
滿二叉樹的葉結點個數為N，則它的結點總數為（ ）。
A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1
二叉樹T，已知其前序遍歷序列為1 2 4 3 5 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其后序遍歷序列為（ ）。
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1
十進制數100.625等值于二進制數（ ）。
A. 1001100.101 B. 1100100.101 C. 1100100.011 D. 1001100.11 E. 1001100.01
下面哪個部件對于個人桌面電腦的正常運行不是必需的（ ）。
CPU B. 圖形卡（顯卡） C. 光驅 D. 主板 E. 內存
下列哪個網絡上常用的名字縮寫是錯誤的（ ）。
WWW（World Wide Web）
URL（Uniform Resource Locator）
HTTP（Hypertext Transfer Protocol）
FTP（Fast Transfer Protocol）
TCP（Transfer Control Protocol）。
用靜電吸附墨粉后轉移到紙張上，是哪種輸出設備的工作方式（ ）。
A. 針式打印機 B. 噴墨打印機 C. 激光打印機 D. 筆式繪圖儀 E. 噴墨繪圖儀
一臺計算機如果要利用電話線上網，就必須配置能夠對數字信號和模擬信號進行相互轉換的設備，這種設備是（ ）。
A. 調制解調器 B. 路由器 C. 網卡 D. 網關 E. 網橋
二、 不定項選擇題 （共10題，每題1.5分，共計15分。多選或少選均不得分）。
美籍匈牙利數學家馮·諾依曼對計算機科學發展所做出的貢獻包括（ ）。
提出理想計算機的數學模型，成為計算機科學的理論基礎。
提出存儲程序工作原理，對現代電子計算機的發展產生深遠影響。
設計出第一臺具有存儲程序功能的計算機EDVAC。
采用集成電路作為計算機的主要功能部件。
指出計算機性能將以每兩年翻一番的速度向前發展。
下列哪個（些）是64位處理器（ ）。
A. Intel Itanium B. Intel Pentium III C. AMD Athlon64
D. AMD Opteron E. IBM Power 5
(2004)10 + (32)16的結果是（ ）。
A. (2036)16 B. (2054)10 C. (4006)8 D. (100000000110)2 E. (2036)10
下列哪個（些）不是數據庫軟件的名稱（ ）。
A. MySQL B. SQL Server C. Oracle D. Outlook E. Foxpro
下列哪個（些）不是計算機的存儲設備（ ）。
A. 文件管理器 B. 內存 C. 顯卡 D. 硬盤 E. U盤
下列哪個（些）軟件屬于操作系統軟件（ ）。
A. Microsoft Word B. Windows XP C. Foxmail D. 金山影霸 E. Red Hat Linux
下列說法中正確的有（ ）。
CPU的基本功能就是執行指令。
CPU的主頻是指CPU在1秒內完成的指令周期數，主頻越快的CPU速度一定越快。
內部構造不同的CPU運行相同的機器語言程序，一定會產生不同的結果。
在一臺計算機內部，一個內存地址編碼對應唯一的一個內存單元。
數據總線的寬度決定了一次傳遞數據量的大小，是影響計算機性能的因素之一。
彩色顯示器所顯示的五彩斑斕的色彩，是由哪三色混合而成的（ ）。
A. 紅 B. 白 C. 藍 D. 綠 E. 橙
下列哪個（些）程序設計語言支持面向對象程序設計方法（ ）。
A. C++ B. Object Pascal C. C D. Smalltalk E. Java
某大學計算機專業的必修課及其先修課程如下表所示：
課程代號 C0 C1 C2 C3 C4 C5 C6 C7
課程名稱 高等數學 程序設計語言 離散數學 數據結構 編譯技術 操作系統 普通物理 計算機原理
先修課程 C0, C1 C1, C2 C3 C3, C7 C0 C6
請你判斷下列課程安排方案哪個（些）是合理的（ ）。
A. C0, C1, C2, C3, C4, C5, C6, C7 B. C0, C1, C2, C3, C4, C6, C7, C5
C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4
E. C0, C1, C2, C3, C6, C7, C5, C4
三．問題求解（共2題，每題5分，共計10分）
75名兒童到游樂場去玩。他們可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費用是5元，游樂場總共收入700，可知有 名兒童沒有玩過其中任何一種。
已知a, b, c, d, e, f, g七個人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們的座位安排在圓桌旁，使得每個人都能與他身邊的人交談？如果可以，請以“a b”開頭寫出你的安排方案： 。
四．閱讀程序（共4題，每題8分，共計32分）
1．program progam1;
var
u: array [0..3] of integer;
a, b, c, x, y, z: integer;
begin
read(u[0], u[1], u[2], u[3]);
a := u[0] + u[1] + u[2] + u[3] - 5;
b := u[0] * (u[1] - u[2] div u[3] + 8);
c := u[0] * u[1] div u[2] * u[3];
x := (a + b + 2) * 3 - u[(c + 3) mod 4];
y := (c * 100 - 13) div a div (u[b mod 3] * 5);
if((x+y) mod 2 = 0) then z := (a + b + c + x + y) div 2;
z := (a + b + c – x - y) * 2;
writeln(x + y - z);
end.
輸入：2 5 7 4
輸出： 。
2．program program2;
var
i, number, ndata, sum: integer;
data: array[1..100] of integer;
procedure solve(s, sign, n: integer);
var i: integer;
begin
for i := s to ndata do begin
inc(sum, sign * (number div (n * data[i])));
solve(i + 1, -sign, n * data[i]);
end;
end;
begin
read(number ,ndata);
sum := 0;
for i := 1 to ndata do read(data[i]);
solve(1, 1, 1);
writeln(sum);
end.
輸入：1000 3 5 13 11
輸出： 。
3．program program3;
var c: array[1..3] of string[200];
s: array[1..10] of integer;
m, n, i: integer;
procedure numara;
var cod: boolean;
i, j, nr: integer;
begin
for j := 1 to n do begin
nr := 0; cod := true;
for i := 1 to m do
if c[i, j] = '1' then begin
if not cod then begin
cod := true; inc(s[nr]); nr := 0;
end
end
else begin
if cod then begin
nr := 1; cod := false;
end
else inc(nr);
end;
if not cod then inc(s[nr]);
end;
end;
begin
readln(m, n);
for i := 1 to m do readln(c[i]);
numara;
for i := 1 to m do
if s[i] <> 0 then write(i, ' ', s[i], ' ');
end.
輸入：
3 10
1110000111
1100001111
1000000011
輸出： 。
4．program program4;
const
u: array[0..2] of integer = (1, -3, 2);
v: array[0..1] of integer = (-2, 3);
var
i, n, sum: integer;
function g(n: integer): integer;
var i, sum: integer;
begin
sum := 0;
for i := 1 to n do inc(sum, u[i mod 3] * i);
g := sum;
end;
begin
sum := 0;
read(n);
for i := 1 to n do inc(sum, v[i mod 2] * g(i));
writeln(sum);
end.
輸入：103
輸出： 。
五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)
1．Joseph
題目描述:
原始的Joseph問題的描述如下：有n個人圍坐在一個圓桌周圍，把這n個人依次編號為1，…，n。從編號是1的人開始報數，數到第m個人出列，然后從出列的下一個人重新開始報數，數到第m個人又出列，…，如此反復直到所有的人全部出列為止。比如當n=6，m=5的時候，出列的順序依次是5，4，6，2，3，1。
現在的問題是：假設有k個好人和k個壞人。好人的編號的1到k，壞人的編號是k+1到2k。我們希望求出m的最小值，使得最先出列的k個人都是壞人。
輸入:
僅有的一個數字是k（0 < k <14）。
輸出:
使得最先出列的k個人都是壞人的m的最小值。
輸入樣例:
4
輸出樣例:
30
程序：
program program1;
var
i, k, m, start: longint;
find: boolean;
function check(remain: integer): boolean;
var result: integer;
begin
result:=( ① ) mod remain;
if( ② )then begin
start := result; check := true;
end
else check := false;
end;
begin
find := false;
read(k);
m := k;
while ( ③ ) do begin
find := true; start := 0;
for i := 0 to k-1 do
if( not check( ④ )) then begin
find := false; break;
end;
inc(m);
end;
writeln( ⑤ );
end.
2．邏輯游戲
題目描述:
一個同學給了我一個邏輯游戲。他給了我圖1，在這個圖上，每一段邊界都已經進行了編號。我的任務是在圖中畫一條連續的曲線，使得這條曲線穿過每一個邊界一次且僅穿過一次，而且曲線的起點和終點都在這整個區域的外面。這條曲線是容許自交的。
對于圖1，我的同學告訴我畫出這樣的一條曲線（圖2）是不可能的，但是對于有的圖形（比如圖3），畫出這樣一條曲線是可行的。對于給定的一個圖，我想知道是否可以畫出滿足要求的曲線。
圖1 圖2
圖3 圖4
輸入:
輸入的圖形用一個n×n的矩陣表示的。矩陣的每一個單元里有一個0到255之間（包括0和255）的整數。處于同一個區域的單元里的數相同，相鄰區域的數不同（但是不相鄰的區域里的數可能相同）。
輸入的第一行是n（0輸出:
當可以畫出滿足題意的曲線的時候，輸出“YES”；否則，輸出“NO”。
輸入樣例:
3
1 1 2
1 2 2
1 1 2
輸出樣例:
YES
程序：
program program2;
const
d: array[0..7] of integer = (1, 0, -1, 0, 0, 1, ① );
var
orig, n, i, j, ns: integer;
a: array[0..101, 0..101] of integer;
bun: boolean;
procedure plimba(x, y: integer);
var i, x1, y1: integer;
begin
a[x, y] := -a[x, y];
if (abs(a[x - 1, y]) <> orig) and (( ② <> a[x - 1, y])
or (abs(a[x, y - 1]) <> orig)) then inc(ns);
if (abs(a[x + 1, y]) <> orig) and ((a[x + 1, y - 1] <> a[x + 1,y])
or (abs(a[x, y - 1]) <> orig)) then inc(ns);
if (abs(a[x, y - 1]) <> orig) and (( ③ <> a[x, y - 1])
or (abs(a[x - 1, y]) <> orig)) then inc(ns);
if (abs(a[x, y + 1]) <> orig) and ((a[x - 1, y + 1] <> a[x,y + 1])
or (abs(a[x - 1, y]) <> orig)) then inc(ns);
for i := 0 to 3 do begin
x1 := x + d[2 * i];y1:=y+ ④ ;
if (x1 >= 1) and (x1 <= n) and (y1 >= 1) and (y1 <= n) and
( ⑤ ) then plimba(x1, y1);
end;
end;
begin
bun := true;
read(n);
for i := 0 to n+1 do
for j := 0 to n+1 do a[i, j] := 0;
a[0, 0] := -1; a[n + 1, 0] := -1;
a[0, n + 1] := -1; a[n + 1, n + 1] := -1;
for i := 1 to n do
for j := 1 to n do read(a[i, j]);
for i := 1 to n do
for j := 1 to n do
if a[i, j] > -1 then begin
ns := 0; ⑥ ;
plimba(i, j);
if ns mod 2 = 1 then bun := false;
end;
if bun then writeln('YES');
if not bun then writeln('NO');
end.
賽區 市 學校 姓名
========================== 密 封 線 =======================
第十屆全國青少年信息學奧林匹克聯賽初賽試題
提高組答卷紙
閱 卷 記 錄
總閱卷人 總 得 分
第 一 大 題 得 分 第三大題得分
題號 1 2 3 4 5 6 7 8 9 10 第四大題得分
得分 1) 2) 3) 4)
第 二 大 題 得 分 第五大題得分
題號 11 12 13 14 15 16 17 18 19 20 (1) (2)
得分
============================ 以下由考生填寫 ============================
答卷部分
單項選擇題 （共10題，每題1.5分，共計15分。每題有且僅有一個正確答案.）。
題號 1 2 ３ 4 5 6 7 8 9 10
選擇
二．不定項選擇題 （共10題，每題1.5分，共計15分。多選或少選均不得分）。
題號 11 12 13 14 15 16 17 18 19 20
選擇
三．問題求解（共2題，每題5分，共計10分）
1. 答：　　　　　　　　　
2. 答: 　　　　　　　　　
四. 閱讀程序（共4題，每題8分，共計32分）
程序的運行結果是:
程序的運行結果是:
賽區 市 學校 姓名
========================== 密 封 線 =======================
四. 閱讀程序（共4題，每題8分，共計32分）
程序的運行結果是:
（4）程序的運行結果是:
五. 完善程序 (前5空，每空2分，后6空，每空3分，共28分)
Pascal 語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
（1） ________________________________
（2） ________________________________
（3） ________________________________
（4） ________________________________
（5） ________________________________
2.
（1） ________________________________
（2） ________________________________
（3） ________________________________
（4）________________________________
（5）________________________________
（6） ________________________________
第十屆全國青少年信息學奧林匹克聯賽初賽試題
提高組參考答案
單項選擇題 （共10題，每題1.5分，共計15分。每題有且僅有一個正確答案.）。
題號 1 2 ３ 4 5 6 7 8 9 10
選擇 A D E C B B C D C A
二．不定項選擇題 （共10題，每題1.5分，共計15分。多選或少選均不得分）。
題號 11 12 13 14 15 16 17 18 19 20
選擇 BC ACDE BCD D AC BE ADE ACD ABDE BCE
三．問題求解（共2題，每題5分，共計10分）
答： 10
答： a b d f g e c
四. 閱讀程序（共4題，每題8分，共計32分）
（1）程序的運行結果是: 263
(2) 程序的運行結果是: 328
（3）程序的運行結果是: 1 4 2 1 3 3
（4）程序的運行結果是: -400
五. 完善程序 (前5空，每空2分，后6空，每空3分，共28分)
Pascal語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
（1） start+m-1 　
（2） result>=k (或者k<=result) 　　　　 　
（3） 　 not find (或者 find=false) 　　
（4） 2*k-i 　　
（5） m-1 　　
2.
(1) 0,-1
（2） a[x-1,y-1]
（3） a[x-1,y-1]
（4） d[2*i+1]
（5） a[x1,y1]=orig (或者orig=a[x1,y1])
（6） orig:=a[i,j]單選題：
1. NOI機試使用的操作系統是：
A. Windows B. Linux C. MacOS D. Vxworks
答案：B
2. Linux中為文件改名使用的命令是：
A. mv B. ren C. chroot D. su
答案：A
3. 在 Linux中返回上一級目錄使用的命令是：
A. cd B. cd . C. cd .. D. cd ./
答案：C
4. 在 Linux中刪除當前目錄下的 test目錄的命令是：
A. mv test B. rm –p test C. rm –r test D. rm –f test
答案：C
5. 當前目錄下有一個編譯好的可執行文件 a.out，執行它使用的命令是：
A. a.out B. . a.out C. ./a.out D. ./a
答案：C
6. 使用高級語言編寫的程序稱之為：
A. 源程序 B. 編輯程序
C. 編譯程序 D. 鏈接程序
答案：A
7. 屬于面向對象程序設計語言的是：
A. C B. C++
C. Pascal D. Basic
答案：B
8. 下列哪個程序在 Redhat Linux 9.0系統中可以用來調試程序：
A. gdb B. gbd
C. debug D. grub
答案：A
9. 在 Linux系統中，下面的說法中正確的是：
A. 文件夾中的文件可以與該文件夾同名
B. 文件夾中的文件不能與該文件夾同名
C. 在不同文件夾中的兩個文件不可以使用相同的文件名
D. 以上說法都不對
答案：A
10. Linux系統中殺死名為 test的后臺進程的命令是：
A. kill test B. kill -9 test C. killall test
答案：C
11. Linux系統中可以查看隱藏文件的命令是：
A. ls -d B. ls -a
C. ls -R D. ls -l
答案：B
12. Linux系統中編譯 C程序的編譯器是：
A. gcc B. g++
C. vc D. fpc
答案：A
13. Linux系統中編譯 Pascal程序的編譯器是：
A. gcc B. g++
C. vc D. fpc
答案：D
14. Linux系統中編譯 C++程序的編譯器是：
A. gcc B. g++
C. vc D. fpc
答案：B
15. Linux系統中，將當前目錄下的文件名打印到 tmp文件中的命令是：
A. ls >tmp B. ls tmp
C. vi . D. ls -a tmp
答案：A
16. Linux系統中，測量當前目錄下程序 test運行時間的命令是：
A. ./test B. time ./test
C. gdb test . D. time test
答案：B
17. vim編輯器中，強制退出不保存修改應當輸入：
A. :qq B. :q
C. :q! . D. :wq
答案：C
18. vim編輯器中，強制退出并保存修改應當輸入：
A. :qq B. :q
C. :q! . D. :wq
答案：D
19. vim編輯器中，定位到文件中第 12行應當輸入：
A. /12 B. :12
C. 12 . D. -12
答案：B
20. vim編輯器中，在文件中查找字符串“12”應當輸入：
A. /12 B. :12
C. 12 D. -12
答案：A
21. 使用 gcc編譯 C程序時，生成調試信息的命令行選項是：
A. -g B. -O2
C. -c D. -Wall
答案：A
22. 使用 gcc編譯 C程序時，生成所有警告信息的命令行選項是：
A. -g B. -O2
C. -c D. -Wall
答案：D
23. 使用 gcc編譯 C程序時，只編譯生成目標文件的命令行選項是：
A. -g B. -O2
C. -c D. -Wall
答案：C
24. 使用 gcc編譯 C程序時，指定輸出文件名的命令行選項是：
A. -g B. -o
C. -c D. -Wall
答案：B
25. 如果 C程序中使用了 math.h中的函數，在編譯時需要加入哪個選項：
A. –om B. –lm C. –om D. –gm
答案：B
26. Linux系統中具有最高權限的用戶是：
A. Admin B. Administrator C. root D. supervisor
答案：C
27. 如何在 Linux的各個虛擬控制臺中切換：
A. Ctrl+Fn B. Alt+Fn C. Shift+Fn D. Alt+n
答案：B
28. 在 Redhat Linux 9中，從字符控制臺切換回桌面環境使用的快捷鍵是：
A. Ctrl+F1 B. Ctrl+F7 C. Alt+F1 D. Alt+F7
答案：D
29. 在 Redhat Linux 9中默認使用的 Shell是：
A. ksh B. bash C. csh D. busybox
答案：B
30. 在 Linux中查看當前系統中的進程使用的命令是：
A. free B. ifconfig C. ps D. ls
答案：C
31. 在 Linux中如何查看進程的 CPU利用率：
A. free B. ifconfig C. ps D. cpuinfo
答案：C
32. 如果自己的程序進入死循環，應當如何終止：
A. Ctrl-C B. Ctrl-D C. Alt-C D. Alt-D
答案：A
33. 可執行文件 a.out從標準輸入讀取數據。現有一組輸入數據保存在 1.in中，
如何使用這個測試數據文件測試自己的程序：
A. a.out <1.in B. ./a.out <1.in C. a.out >1.in D. ./a.out >1.in
答案：B
34. 可執行文件 prog_1向標準輸出輸出運行結果。如何將輸出結果保存到 1.out
文件中：
A. prog_1 <1.out B. ./ prog_1 <1.out C. prog_1 >1.out D. ./ prog_1 >1.out
答案：D
35. 使用 Reset鍵強行重新啟動計算機可能會對系統造成什么后果：
A. 文件系統損壞 B. 內存燒毀 C. CPU燒毀 D. 顯示器爆炸
答案：A
36. 在 Linux系統中，下列哪個命令可以查看文件的大小：
A. ls –a B. ls –R C. ls –l D. ls –d
答案：C
37. 當前目錄中有如下文件
-rw-r--r-- 1 user None 8.7K Jul 2 16:35 foobar
-rw-r--r-- 1 user None 93 Jul 2 16:35 foobar.c
-rwx------ 1 user None 144 Jul 2 16:35 foobar.sh
其中可以執行的文件是：
A. foo B. foobar C. foobar.c D. foobar.sh
答案：D
38. 評測系統中對程序源文件大小的限制是：
A.小于 1KB B.小于 50KB C.小于 1MB D.無限制
答案：B
39. 如無另行說明，評測系統中對程序使用內存的限制是：
A小于 512KB B小于 1MB C小于 10MB D.以硬件資源為限
答案：D
40. Linux下的換行字符為：
A. \n B. \r C. \r\n D. \n\r
答案：A
41. 如何終止一個失去響應的進程（$pid代表進程號）：
A. kill $pid B. stop $pid C. hang $pid D. rm $pid
答案：A
42. Linux中是否區分文件和目錄名稱的大小寫：
A. 是 B. 否
答案：A
43. 選手在 NOI機試過程中是否可以使用網絡：
A. 可以訪問互聯網 B. 可以訪問局域網 C. 禁止使用網絡
答案：C
44. 下列哪條命令可以為自己的程序創建一個備份：
A. mv my.c my.c.bak B. cp my.c myc.bak
C. cat my.c my.c.bak D. echo my.c my.c.bak
答案：B
45. 在 Anjuta中調試程序，繼續執行的快捷鍵是：
A. F4 B. F5 C. F6 D. F7
答案：A
46. 在 Lazarus中開始運行程序的快捷鍵是：
A. F4 B. F5 C. F8 D. F9
答案：D
47. 在 Anjuta中調試程序，單步運行(Step over)的快捷鍵是：
A. F4 B. F5 C. F6 D. F7
答案：C
48. 在 Lazarus中調試程序，單步運行(Step over)的快捷鍵是：
A. F4 B. F5 C. F8 D. F9
答案：C
49. 調試程序的方法有
A 單步調試 B使用 print類語句打印中間結果 C 讀源代碼 D以上都是
答案：D
50. 如果需要在 Lazarus 中使用單步調試，則：
A. 無須配置
B. 在 File選單中配置
C. 在 Environment->Debugger Options中配置
D. 在 Tools->Diff中配置
答案：C
51. 在考試過程中，如果出現系統死機或者崩潰現象，選手應當采取的措施是：
A.靜坐等待 B.自行重啟系統，不必向監考人員匯報
C.舉手示意監考人員處理 D.離開考場
答案：C
52. 提交的答案程序中如果包含 NOI考試明確禁止使用的代碼，后果是
A 沒后果
B 本題成績以 0分計算
C 取消參賽資格
D 禁賽 1年
答案：B
53. NOI比賽使用的 Linux發行版是：
A. Redhat 9 B. Fedora 5
C. Debian Sarge D. Gentoo 2006.1
答案：A
54. 對評測結果有疑義，需要申請復評，則：
A 直接向評測人員反映
B 向指導老師反映
C 提出書面申請，并由科學委員會認可簽字后提交至評測人員
D 在網站上申請
答案：C
55. 復評成績較原始成績有變化，則：
A 以原始成績為準
B 以復評成績為準
C 以分高的為準
D 以分低的為準
答案： B
56. Pascal中 integer和 long integer類型的長度和編譯選項是否有關系
A 有關系 B 有時候有關系 C 沒關系 D 不確定
答案：A
57. NOI考試對 C++語言模板的使用有限制嗎？
A 有 B 沒有 C 有時候有 D無所謂
答案：A
58. NOI考試對 PASCAL語言的使用有限制嗎？
A 有 B 沒有 C 有時候有 D無所謂
答案：B
59. 名為 FILE的文件和名為 File的文件在 Linux系統中被認為是：
A 同一個文件 B 不同的文件 C 由系統版本決定
答案：B
60. 目錄 DIRECT和目錄 Direct在 Linux系統中被認為是：
A 同一個目錄 B 不同的目錄 C 由系統版本決定
答案：B
61. 在 NOI正式考試中如何登錄自己的比賽用機：
A 使用 friend帳戶
B 使用考前評測人員下發的帳戶
C 自建帳戶
答案：B
62. 如果考試分多日進行，那么考試使用的帳戶：
A 使用同樣的帳戶
B 使用 friend帳戶
C 使用每場考試前評測人員下發的帳戶
D 自建帳戶
答案：C
63. 選手答案文件保存的目錄是：
A 任意目錄
B /home
C /tmp
D 選手目錄下和考題名稱符合的目錄
答案：D
64. 選手答案的文件名要求是：
A 無要求
B和試卷的題目摘要中所示文件名一致
C file.in
D file.ans
答案：B
65. 選手答案的文件名大小寫錯誤，成績會怎樣：
A 減半
B 沒有影響
C 0分
D 根據考試情況決定
答案：C
66. 選手提交的源代碼文件擴展名是否有特殊要求：
A 沒有 B 只能是大寫 C 只能是小寫 D 無所謂
答案：C
67. Pascal源文件的擴展名是：
A 無所謂 B pas C lpr D PAS
答案：B
68. 發現鼠標有問題，選手可以：
A 自行更換 B 請工作人員更換 C咨詢老師 D 將就使
答案：B
69. 對試題理解有問題，選手可以：
A 互相討論 B 舉手求助 C 上網查 D 打電話求助
答案：B
70. 考試結束后選手需要：
A 逗留考場 B 迅速離開 C 咨詢老師 D 互相討論
答案：B
71. 復評結束后是否還能提交復評申請：
A 不能 B 能 C 依據考題而定 D 依據考試類型
答案： A
72. 測試點時間限制的含義是指
A 系統時間 B 用戶時間 C 總時間 D 北京時間
答案： B
73. 什么情況下選手可以申請延長考試時間：
A 機器出現故障 B 答題時間不夠 C 網絡出現故障 D 和監考人員鬧糾紛
答案：A
74. 草稿紙用完了，如何處理：
A 沒辦法 B 上網求助 C 打電話求助 D 舉手向監考人員求助
答案 D
75. 水喝完了，如何處理
A 怪自己倒霉 B 喝別人的 C 舉手向監考人員再要一瓶 D 出去買
答案 C
76. 考試太簡單，能提前離開嗎
A 能 B 不能 C 依考試情況而定 D 依個人情況而定
答案：A
77. 離開考場后，發現還有個問題沒改，能回去再改嗎
A 能 B 不能 C 依考試情況而定 D 依個人情況而定
答案 B
78. 考試中機器突然沒響應了，如何處理
A 重啟機器 B 等待 C問旁邊的人 D 舉手向監考人員求助
答案： D
79. 考試中發現登錄名和密碼的單子丟了，如何處理
A 問指導老師 B 沒辦法 C 向工作人員再要一張 D 用別人的
答案： C
80. 復評的時候忘記登錄名和密碼了，如何處理
A 問指導老師 B 沒辦法 C 問工作人員再要一張 D 用別人的
答案： C
81. 在監考人員宣布 NOI機試開始之前，是否允許選手登錄系統和翻閱試卷？
A. 是 B. 否
答案：B
82. 在 NOI機試中，是否允許選手私自重新啟動計算機？
A. 是 B. 否
答案：B
83. 在 NOI系列考試中， 如果由于文件名不正確導致被判 0分，提出復評請求，
會被接受嗎？
A. 會 B. 不會
答案：B
84. 在 NOI系列考試中， 如果由于文件目錄名不正確導致被判 0分，提出復評
請求，會被接受嗎？
A. 會 B. 不會
答案：B
85. 在 NOI系列考試中， 如果由于文件保存路徑不正確導致被判 0分，提出復
評請求，會被接受嗎？
A. 會 B. 不會
答案：B
86. Lazarus是可以支持多窗口編輯的 IDE嗎？
A. 是 B. 否
答案：A
87. Anjuta是可以支持多窗口編輯的 IDE嗎？
A. 是 B. 否
答案：A
88. 選手可以不使用 IDE環境編輯程序源代碼嗎？
A. 可以 B. 不可以
答案：A
89. 選手回答填空題，提交的答案中可以包含引號嗎？
A. 可以 B. 不可以
答案：B
90. 選手程序在某測試點上的運行時間僅比時限多 0.005秒，算不算超時？
A. 算 B. 不算
答案：A
計算機常識單選題：
91. 一個完整的計算機系統應包括_______。
A.系統硬件和系統軟件 B.硬件系統和軟件系統
C.主機和外部設備 D.主機、鍵盤、顯示器和輔助存儲器
答案：B
92. 目前微型計算機中采用的邏輯組件是_______。
A.小規模集成電路 B.中規模集成電路
C.大規模和超大規模集成電路 D.獨立組件
答案：C
93. 軟件與程序的區別是_______。
A.程序價格便宜、軟件價格昂貴
B.程序是用戶自己編寫的，而軟件是由廠家提供的
C.程序是用高級語言編寫的，而軟件是由機器語言編寫的
D.軟件是程序以及開發、使用和維護所需要的所有文檔的總稱,而程序是軟件
的一部分
答案：D
94. IT表示_______。
A. 通信技術 B. 信息技術 C. 網絡技術 D. 信息學
答案：B
95. 計算機中央處理器簡稱為_______
A. IBM B.UBS C.CPU D.Computer
答案：C
96. 計算機內存儲器的作用是_______
A.用來存放暫時不用的程序和數據
B.用來存放當前 CPU正在使用的程序和數據
C.用來存放要刪除的信息
D.僅用來存儲選手的數據和程序
答案：B
97. 用來全面管理計算機硬件和軟件資源的軟件叫_______
A．操作系統 B．應用軟件 C．管理軟件 D. 系統平臺
答案：A
98. LAN是指_______
A．互聯網 B．局域網 C．廣域網 D. 城域網
答案：B
99. 在微機中，bit的中文含義是_____。
A. 二進制位 B. 字
C. 字節 D. 雙字
答案：A
100.為了避免混淆，十六進制數在書寫時常在后面加字母_____。
A. H B. O
C. D D. B
答案：A
101.計算機所能辨認的最小信息單位是_______。
A. 位 B. 字節 C. 字 D. 字符串"
答案：A
102.ASCII的含義是________。
A.條件碼 B.二－十進制編碼
C.二進制碼 D.美國信息交換標準代碼
答案：D
103.在計算機術語中經常用 RAM表示________。
A、只讀存儲器 B、可編程只讀存儲器
C、動態隨機存儲器 D、隨機存取存儲器
答案：D
104.RAM存儲器在斷電后，其中的數據會_______。
A.丟失 B.自動保存
C.不變化 D.需人工保存
答案：A
105.ROM存儲器在斷電后，其中的數據會_______。
A.丟失 B.自動保存
C.不變化 D.需人工保存
答案：C
106.現代計算機所應用的存儲程序原理是_________提出的。
A.圖靈
B.布爾
C.馮·諾依曼
D.愛因斯坦
答案：C
107.計算機內所有的信息都是以_______數碼形式表示的。
A.八進制
B.十進制
C.二進制
D.十六進制
答案：C
108.計算機能直接識別和執行的語言是________。
A. 機器語言
B. 匯編語言
C. C語言
D. Pascal語言
答案：A
109.Linux是一個_______操作系統，意思是源碼可以免費獲得。
A. 開源的
B. 有使用許可的
C. 不開放源代碼的
答案：A
110.NOI的中文意思是：
A. 中國信息學奧賽
B. 中國國家奧委會
C. 國際信息學奧賽
D. 中國信息學聯賽
答案：A
多選題：
111.NOI機試中，選手允許使用的編程語言包括 ____
A. C B. C++ C. Pascal D. Java
答案：ABC
112.NOI比賽的題目類型有
A. 非交互式程序題 B. 交互式程序題 C. 答案提交題
答案：ABC
113.選手比賽中提交的有效文件類型有
A 答案文件 B 臨時文件 C 源程序 D 庫文件
答案 AC
114.參加 NOI考試目的是
A 提高水平 B 增進交流 C 為國爭光 D 為得獎
答案 ABC
115.選手提交的程序不得進行的操作包括：
A. 試圖訪問網絡
B. 使用 fork或其它線程/進程生成函數
C. 打開或創建題目規定的輸入/輸出文件之外的其它文件
D. 運行其它程序
答案：ABCD
116.下列哪些申訴將不被受理：
A. 以修改過的程序或答案為依據的
B. 沒有復測結果支持的
C. 超過申訴時間的
D. 對評測結果中的超時有異議，且復測結果的運行時間與題目時間限制之
差小于題目時間限制 5％的。
答案：ABCD
117.遇到下列哪些情況可以向工作人員申請加時補償：
A. 計算機硬件故障 B. 上廁所
C. 操作系統死機 D. 工作人員答疑
答案：AC
118.選手進入考場可以攜帶的物品是：
A. 紙 B. 筆 C. 手表 D. 書籍
答案：BC
119.選手進入考場不可以攜帶的物品是：
A. 紙 B. 筆 C. U盤 D. 手機
答案：ACD
120.競賽組織者將在競賽場地為選手提供的物品是：
A. 草稿紙 B. 飲用水 C. 食品 D. 鉛筆
答案：ABC
填空題：
121.字長為 32bit的計算機,表示它能作為一個整體進行傳送的數據長度可為____
個字節。
答案：4
122.一個字節由相鄰的_______個二進制位組成。
答案：8
123.二進制數“10”化為十進制數是_______
答案：2
124.與十六進制數（AB）等值的二進數是_______
答案：10101011
125.內存空間地址段為 3001H至 7000H，則可以表示_______KB的存儲空間。
答案：4
126.Linux中查看當前路徑使用的命令是_______
答案：pwd
127.在 Linux下建立目錄使用的命令是_______
答案：mkdir
128.NOI比賽中提供的 Pascal IDE環境是_______
答案：Lazarus
129.NOI比賽中提供的 C++ IDE環境是_______
答案：Anjuta
130.NOI比賽每場上機考試的比賽時間是_______小時
答案：5第十二屆全國青少年信息學奧林匹克聯賽初賽試題
（ 提高組 Pascal 語言 二小時完成 ）
由整理收集 ( http: / / www.21cnjy.com / )

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



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


1. 在以下各項中。（ ）不是 CPU 的組成部分。
A. 控制器 B. 運算器 C. 寄存器 D. ALU E. RAM


2. BIOS（基本輸入輸出系統）是一組固化在計算機內（ ）上一個 ROM 芯片上的程序。
A. 控制器 B. CPU C. 主板 D. 內存條 E. 硬盤


3.在下面各世界頂級的獎項中，為計算機科學與技術領域作出杰出貢獻的科學家設立的獎項是（ ）。
A. 沃爾夫獎 B. 諾貝爾獎 C. 菲爾茲獎
D. 圖靈獎 E. 南丁格爾獎


4．在編程時（使用任一種高級語言，不一定是 Pascal），如果需要從磁盤文件中輸入一個很大的二維 數組（例如 1000*1000 的 double 型數組），按行讀（即外層循環是關于行的）與按列讀（即外層循 環是關于列的）相比，在輸入效率上（ ）。
A. 沒有區別 B. 有一些區別，但機器處理速度很快，可忽略不計
C. 按行讀的方式要高一些 D. 按列讀的方式要高一些 E. 取決于數組的存儲方式。


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

A. 441 B. 42 C.23 D.24 E.25


6．在 Pascal 語言中，判斷 a 不等于 0 且 b 不等于 0 的正確的條件表達式是（ ）

A. not a=0 or not b=0 B. not((a=0)and(b=0)) C. not(a=0 and b=0) D. (a<>0)or(b<>0) E. (a<>0)and (b<>0)

7．某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態為空，從 這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出,出”。假設車輛入站的 順序為 1，2，3，……，則車輛出站的順序為（ ）。

A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6

D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5


8．高度為 n 的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為 n-1 的滿二叉樹。在這里，樹高等于葉結點的最大深度，根結點的深度為 0，如果某個均衡的二叉樹共有 2381 個結點， 則該樹的樹高為（ ）。
A. 10 B. 11 C. 12 D. 13 E. 210 – 1


9. 與十進制數 1770.625 對應的八進制數是（ ）。 ( http: / / www.21cnjy.com / " \t "_blank )

A. 3352.5 B. 3350.5 C. 3352.1161
D. 3350.1151 E. 前 4 個答案都不對


10．將 5 個數的序列排序，不論原先的順序如何，最少都可以通過（ ）次比較，完成從小到大的排序。

A. 6 B. 7 C. 8 D. 9 E. 10


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


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


12. (2010)16 + (32)8的結果是（ ）。

A. (8234)10 B. (202A)16

C. (100000000110)2 D. (2042)16


13. 設棧S的初始狀態為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可能出現的有（ ）。

A. a, b, c, e, d B. b, c, a, e, d

C. a, e, c, b, d D. d, c, e, b, a


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

A. 3 2 1 4 6 5 B. 3 2 1 5 4 6

C. 2 3 1 5 4 6 D. 2 3 1 4 6 5


15. 在下列各數據庫系統軟件中，以關系型數據庫為主體結構的是（ ）。

A. ACCESS B. SQL Server

C. Oracle D. Foxpro


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

A. gcc/g++ B. Turbo Pascal

C. Turbo C D. free pascal

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


18. 在下列關于計算機語言的說法中，正確的有（ ）。
A. Pascal和C都是編譯執行的高級語言
B. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上
C. C++是歷史上的第一個支持面向對象的計算機語言
D. 高級語言比匯編語言更高級，是因為它的程序的運行效率更高


19. 在下列關于計算機算法的說法中，正確的有（ ）。
A. 一個正確的算法至少要有一個輸入
B. 算法的改進，在很大程度上推動了計算機科學與技術的進步 ( http: / / www.21cnjy.com / " \t "_blank )
C. 判斷一個算法的好壞，主要依據它在某臺計算機上具體實現時的運行時間
D. 目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法


20. 在下列關于青少年信息學競賽的說法中，你贊成的是（ ）（本題不回答為0分，答題一律滿分）。
A. 舉行信息學競賽的目的，是為了帶動廣大青少年學科學、愛科學，為造就一大批優秀的計算機科學 與技術人才奠定良好的基礎
B. 如果競賽優勝者不能直接保送上大學，我今后就不再參與這項活動了
C. 準備競賽無非要靠題海戰術，為了取得好成績，就得拼時間、拼體力
D. 為了取得好成績，不光要看智力因素，還要看非智力因素。優秀選手應該有堅韌不拔的意志，有 嚴謹求實的作風，既要努力奮進，又要勝不驕敗不餒


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


1．將 2006 個人分成若干不相交的子集，每個子集至少有 3 個人，并且：
（1）在每個子集中，沒有人認識該子集的所有人。
（2）同一子集的任何 3 個人中，至少有 2 個人互不認識。
（3）對同一子集中任何 2 個不相識的人，在該子集中恰好只有 1 個人認識這兩個人。 則滿足上述條件的子集最多能有 個？


2．將邊長為 n 的正三角形每邊 n 等分，過每個分點分別做另外兩邊的平行線，得到若干個正三角形， 我們稱為小三角形。正三角形的一條通路是一條連續的折線，起點是最上面的一個小三角形，終點是最 下面一行位于中間的小三角形。在通路中，只允許由一個小三角形走到另一個與其有公共邊的且位于同 一行或下一行的小三角形，并且每個小三角形不能經過兩次或兩次以上（圖中是 n=5 時一條通路的例 子）。設 n=10，則該正三角形的不同的通路的總數為_ __。




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


1. Program ex401;

var

u,v:array[0..3] of integer;

i,x,y:integer;

begin

x:=10; y:=10;

for i:=0 to 3 do read(u[i]);
v[0]:=(u[0]+u[1]+u[2]+u[3]) div 7; v[1]:=u[0] div ((u[1]-u[2]) div u[3]); v[2]:=u[0]*u[1] div u[2]*u[3]; v[3]:=v[0]*v[1];
x:=(v[0]+v[1]+2)-u[(v[3]+3) mod 4];

if (x>10) then

y:=y+(v[2]*100-v[3]) div (u[u[0] mod 3]*5) ( http: / / www.21cnjy.com / " \t "_blank )

else

y:=y+20+(v[2]*100-v[3]) div (u[v[0] mod 3]*5);

writeln (x,',',y);
end. {*注：本例中，給定的輸入數據可以避免分母為 0 或下標越界。 )
輸入：9 3 9 4
輸出：



2.Program ex402;

const

m:array[0..4] of integer=(2,3,5,7,13);

var i,j:integer; t: longint; begin
for i:=0 to 4 do begin
t:=1;

for j:=1 to m[i]-1 do t:=t*2;

t:=(t*2-1)*t; write (t,' '); end;
writeln;

end.
輸出:_____



3. Program ex403;

Const NN=7; Type
Arr1=array[0..30] of char;

var s:arr1;
k,p:integer;

function fun1(s:arr1; a:char;n:integer):integer;

var j:integer; begin
j:=n;

while (a0) do dec(j);

fun1:=j;

end;

Function fun2(s:arr1; a:char; n:integer):integer;

var j:integer; begin
j:=1;

while (a>s[j])and(j
fun2:=j;

end;

begin

for k:=1 to NN do s[k]:=chr(ord('A')+2*k+1);
k:=fun1(s,'M',NN)+fun2(s,'M',NN);
writeln(k);

end.
輸出：



4. program ex404;

var x,x2:longint; ( http: / / www.21cnjy.com / " \t "_blank )
procedure digit(n,m:longint);

var n2:integer;

begin

if(m>0) then begin
n2:=n mod 10;

write(n2:2);

if(m>1) then digit(n div 10,m div 10);

n2:=n mod 10; write(n2:2); end;
end;

begin

writeln('Input a number:');

readln(x);

x2:=1;

while(x2
x2:=x2 div 10; digit(x,x2); writeln;
end.
輸入：9734526
輸出：


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


1．（選排列）下面程序的功能是利用遞歸方法生成從 1 到 n(n<10)的 n 個數中取 k(1<=k<=n)個數的 全部可能的排列（不一定按升序輸出）。例如，當 n=3，k=2 時，應該輸出（每行輸出 5 個排列）：

12 13 21 23 32

31
程序：
Program ex501; Var i,n,k:integer;
a:array[1..10] of integer;

count:longint;

Procedure perm2(j:integer);

var i,p,t:integer;

begin

if ① then

begin

for i:=k to n do begin inc(count);
t:=a[k]; a[k]:=a[i]; a[i]:=t;

for ② do write(a[p]:1);

write(' ');

t:=a[k];a[k]:=a[i];a[i]:=t;

if (count mod 5=0) then writeln;

end; exit; end;
for i:=j to n do begin
t:=a[j];a[j]:=a[i];a[i]:=t; ( http: / / www.21cnjy.com / " \t "_blank )

③ ;

t:=a[j]; ④ ;

end end; begin
writeln('Entry n,k (k<=n):'); read(n,k);

count:=0;

for i:=1 to n do a[i]:=i;
⑤ ;

end.


2．（TSP 問題的交叉算子）TSP 問題(Traveling Salesman Problem)描述如下：給定 n 個城 市，構成一個完全圖，任何兩城市之間都有一個代價（例如路程、旅費等），現要構造遍歷所有城市的環 路，每個城市恰好經過一次，求使總代價達到最小的一條環路。

　
遺傳算法是求解該問題的一個很有效的近似算法。在該算法中，一個個體為一條環路，其編碼方法 之一是 1 到 n 這 n 個數字的一個排列，每個數字為一個城市的編號。例如當 n=5 時，“3 4 2 1 5” 表示該方案實施的路線為 3->4->2->1->5->3。遺傳算法的核心是通過兩個個體的交叉操作，產生兩 個新的個體。下面的程序給出了最簡單的一種交叉算法。具體過程如下：
(1)選定中間一段作為互換段，該段的起止下標為 t1，t2，隨機生成 t1，t2 后，互換兩段。
(2)互換后，在每個新的排列中可能有重復數字，因而不能作為新個體的編碼，一般再做兩步處理：
(2.1) 將兩個互換段中，共同的數字標記為 0，表示已處理完。
(2.2) 將兩個互換段中其余數字標記為 1，按順序將互換段外重復的數字進行替換。 例如：n=12，兩個個體分別是：

a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11

a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9
t1=5，t2=8。上述每一行中，兩個星號間的部分為互換段。假定數組的下標從 1 開始，互換后有：

a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11

a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9
然后，將數字 6,7 對應的項標記為 0，星號內數字 2,9,10,11 對應的項標記為 1，并且按順序對 應關系為:10<->2，11<->9。于是，將 a1[9]=10 替換為 a1[9]=2，將 a2[2]=2 替換為 a2[2]=10， 類似再做第 2 組替換。這樣處理后，就得到了兩個新個體：

a1: 1 3 5 4 6 7 10 11 2 12 8 9

a2: 3 10 1 12 2 6 7 9 8 5 4 11
（3）輸出兩個新個體的編碼。 程序：

program ex502;

type arr1=array[1..20] of integer;

var a1,a2,kz1,kz2:arr1; n,k,t1,t2:integer;
function rand1(k:integer):integer;

var t:integer;

begin t:=0;
while (t<2) or(t>k) do t:=random(k+1)-2; rand1:=t;
end;

procedure read1(var a:arr1;m:integer);
{讀入數組元素 a[1]至 a[m]，a[0]=0，略。}

procedure wrt1(var a:arr1;m:integer);
{輸出數組元素 a[1]至 a[m]，略。}
procedure cross(var a1,a2:arr1;t1, t2,n:integer); ( http: / / www.21cnjy.com / " \t "_blank )

var i,j,t,kj:integer; begin
for i:=t1 to t2 do begin
t:=a1[i]; ① ;

end;

for i:=1 to n do

if (it2) then begin
kz1[i]:=-1;kz2[i]:=-1;

end else
begin ② ; end;

for i:=t1 to t2 do for j:=t1 to t2 do
if(a1[i]=a2[j]) then
begin ③ ; break; end;

for i:=t1 to t2 do if(kz1[i]=1) then begin
for j:=t1 to t2 do if(kz2[j]=1) then
begin kj:=j; break; end;

for j:=1 to n do if ④ then

begin a1[j]:=a2[kj];break; end;

for j:=1 to n do if ⑤ then

begin a2[j]:=a1[i]; break; end;

kz1[i]:=0;kz2[kj]:=0;

end; end; begin
writeln('input (n>5):');

readln(n);

writeln('input array 1:'); read1(a1,n);
writeln('input array 2:'); read1(a2,n);

t1:=rand1(n-1);

repeat

t2:=rand1(n-1); until(t1<>t2); if(t1>t2) then
begin k:=t1; t1:=t2; t2:=k; end;

⑥ ;

wrt1(a1,n); wrt1(a2,n);

end.
提高組（PASCAL 語言）參考答案與評分標準
由整理收集 ( http: / / www.21cnjy.com / )

一、單項選擇題：（每題 1.5 分）

1. E 2. C 3. D 4. E 5. C 6. E 7. C 8. B 9. A 10. B

二、不定項選擇題：（每題 1.5 分） ( http: / / www.21cnjy.com / " \t "_blank )

11. ABC 12. AB 13. C 14. BC 15. ABCD
16. AD 17. CD 18.AB 19. BD 20.（滿分，空白 0 分）


三、問題求解：（每題 5 分）
1. 401 2. 9! （或 362880）

四、閱讀程序寫結果
1. -13，57 （對 1 個數給 4 分，無逗號扣 1 分）

2. 6 28 496 8128 33550336 ( http: / / www.21cnjy.com / " \t "_blank )
（前 2 個對 1 個數給 1 分，后 3 個對 1 個數給 2 分）

3. 11
4. 6 2 5 4 3 7 9 9 7 3 4 5 2 6（數字之間無空格扣 2 分）

五、完善程序(前 5 空，每空 2 分，后 6 空，每空 3 分)
1．① j=k （或k=j）
② p:=1 to k
③ perm2(j+1)
④ a[j]:=a[i];a[i]:=t
⑤ perm2(1)
2．① a1[i]:=a2[i];a2[i]:=t
② kz1[i]:=1;kz2[i]:=1;
③ kz1[i]:=0;kz2[j]:=0;
④ (a1[j]=a1[i])and(kz1[j]=-1)
⑤ (a2[j]=a2[kj])and(kz2[j]=-1) ( http: / / www.21cnjy.com / " \t "_blank )
⑥ cross(a1,a2,t1,t2,n)第九屆分區聯賽提高組初賽試題
（提高組 PASCAL 語言 二小時完成）
●● 全部答案均要寫在答案卷子上，寫在試卷紙上一律無效 ●●
一.單項選擇題 （共10題，每題1.5分，共計15分。每題有且僅有一個正確答案.）。
1. 圖靈 (Alan Turing) 是 （ ）。
A） 美國人 B） 英國人 C） 德國人 D） 匈牙利人 E） 法國人
2. 第一個給計算機寫程序的人是（ ）。
A） Alan Mathison Turing B） Ada Lovelace C） John von Neumann
D） John Mc-Carthy E） Edsger Wybe Dijkstra
3. 十進制數2003等值于二進制數（ ）。
A） 0100000111 B） 10000011 C） 110000111 D） 11111010011 E） 1111010011
4. 假設A=true,B=false,C=ture,D=ture,邏輯運算表達式A∧B∨C∧D的值是（ ）。
A） ture B） false C） 0 D） 1 E） NULL
5. 一個高度為h 的二叉樹最小元素數目是（ ）。
A） 2h+1 B） h C） 2h-1 D） 2h E） 2h-1
6. 已知隊列（13，2，11，34，41，77，5，7，18，26，15），第一個進入隊列的元素是13，則第五個出隊列的元素是（ ）。
A） 5 B） 41 C） 77 D） 13 E） 18
7. 下面一段程序是用（ ）語言書寫的。
int func1(int n){
int i,sum=0;
for(i=1;i<=n;i++)
sum+=i*i;
return sum;
}
A) FORTRAN B) PASCAL C) C D) PROLOG E) BASIC
8. 設全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，則集合（A ∩B）∪～C 為（ ）。
A） 空集 B） {1} C） {3，5} D）{1，5} E） {1，3，5}
9. 表達式(1+34)*5-56/7 的后綴表達式為（ ）。
A） 1+34*5-56/7 B） -*+1 34 5/56 7 C） 1 34 +5*56 7/-
D） 1 34 5* +56 7/- E） 1 34+5 56 7-*/
10. 下列計算機設備，即是輸入設備，又是輸出設備的是（ ）。
A） 鍵盤 B） 觸摸屏 C） 掃描儀 D）投影儀 E） 數字化儀
二.不定項選擇題（共10題，每題1.5分，共計15分。多選少選均不得分）。
11. 下列分辨率的顯示器顯示出的圖像，最清晰的是（ ）。
A） 800*600 B） 1024*768 C） 640*480 D） 1280*1024 E） 800*1000
12. 下列說法中，哪個（些）是錯誤的（ ）。
A）程序是指令的序列，它有三種結構：順序、分支和循環。
B）數據總線決定了中央處理器CPU所能訪問的最大內存空間的大小。
C）中央處理器CPU內部有寄存器組，用來儲存數據。
D）不同廠家生產的CPU所能處理的指令集是相同的。
E）數據傳輸過程中可能會出錯，奇偶校驗法可以檢測出數據中那一為在傳輸中出了差錯。
13. CPU訪問內存的速度比訪問下列哪個（些）存儲設備要慢（ ）。
A）寄存器 B）硬盤 C）軟盤 D）高速緩存 E）光盤
14. 下列電子郵件地址，哪個（些）是正確的（ ）。
A）wang@ ( http: / / www.21cnjy.com / ) B) [email protected] ( http: / / www.21cnjy.com / ) C) 162.105.111.22
D) ccf. E)http://www.
15. 數字圖像文件可以用下列哪個（些）軟件來編輯（ ）。
A）畫筆（Paintbrush） B）記事薄（Notepad） C) Photoshop D) WinRAR E)Midisoft
16. 下列哪個（些）軟件不是操作系統軟件的名字（ ）。
A）WindowsXP B) DOS C) Linux D) OS/2 E) Arch/Info
17. 下列哪個（些）不是個人計算機的硬件組成部分（ ）。
A）主板 B）虛擬內存 C）電源 D）硬盤 E）總線
18. 運算試(2008)10-(3723)8 的結果是（ ）。
A）(-1715)10 B) (5)10 C) (5)16 D) (101)2 E) (3263)8
19. 已知元素（8，25，14，87，51，90，6，19，20），問這些元素以怎樣的順序進入棧，才能使出棧的順序滿足：8在51前面；90在87的后面；20在14的后面；25在6的前面；19在90的后面。（ ）。
A）20，6，8，51，90，25，14，19，87
B）51，6，19，20，14，8，87，90，25
C）19，20，90，7，6，25，51，14，87
D）6，25，51，8，20，19，90，87，14
E）25，6，8，51，87，90，19，14，20
20. 假設我們用d=(a1,a2,...,a5),表示無向圖G的5個頂點的度數，下面給出的哪（些）組d 值合理（ ）。
A）{5，4，4，3，1} B）{4，2，2，1，1} C）{3，3，3，2，2}
D）{5，4，3，2，1} E）{2，2，2，2，2}
三、問題求解（共2題，每題5分，共計10分）
1. 無向圖G有16條邊，有3個4度頂點、4個3度頂點，其余頂點的度均小于3，則G至少_______個頂點。
2. 某年級學生共選修6門課程，期末考試前，必須提前將這6門課程考完，每人每天只在下午至多考一門課程，設6門課程為C1，C2，C3，C4，C5，C6，S(Ci)為學習Ci 的學生集合。已知S(Ci)∩S(C6)≠ф，i=1，2，...，5，S(Ci)∩S(Ci+1)≠ф，i=1，2，3，4，S(C5)∩S(C1)≠ф，問至少安排_____天才能考完這6門課程。
四.閱讀程序（共4題，每題8分，共計32分）
1. program Program1;
var a,b,c,d,sum : longint;

begin
read(a,b,c,d);
a := a mod 23; b := b mod 28; c := c mod 33;
sum := a * 5544 + b * 14421 + c * 1228 - d;
sum := sum + 21252; sum := sum mod 21252;
if (sum = 0 ) then sum := 21252;
writeln(sum);
end.
輸入：283 102 23 320 輸出____________
2. program Program2;
const
u : array[1..4] of integer = (0,5,3,1);
v : array[1..4] of integer = (0,7,6,5);
var a,b,c,d,e,f,x,y,z: integer;
begin
read(a,b,c,d,e,f);
z := f+ e + d + (c+3) div 4; y := 5 * d + u[c mod 4];
if (b > y) then
begin
z := z + (b - y + 8) div 9;
x := ((b - y + 8) div 9 * 9 -(b - y)) * 4 + 11 * e + v[c mod 4];
end
else
x := (y - b) * 4 + 11 * e + v[c mod 4];
if (a > x) then
z := z + (a - x + 35) div 36;
writeln(z)
end.
輸入： 4 7 9 20 56 47 輸出____________________
3. program Program3;
var m,n: integer; mark: Boolean;
function test(m,N:integer):integer;
var i,p: integer; flag: boolean;
begin
m := m - 1; i := 0; flag := False;
for p:= 2*N downto (N+1) do
begin
i:= (i+m) mod p;
if (i
begin
test := 0; flag := Ture; Break;
end
end;
if not(flag) then test:=1;
end;
begin
read(n); m:=1; Mark := False;
repeat
if (test(m,n)=1) then
begin writeln(m); break; end;
m:= m+1;
until Mrak;
end.
輸入：7 輸出_________
4. program Program4;
var m,n,i,j: integer;
p,w,a,b: array[0..19] of integer;
begin
read(n); m:= 0;
for i:= 0 to n-1 do
begin read(p[i]); b[i]:=1; end;
for i:=0 to n-1 do
begin
if (i>0) then
a[m]:=p[i]-p[i-1]
else
a[m]:=p[i];
m:=m+1;
while ((m>1) and (a[m-1]=0)) do
begin m:=m-1; b[m]:=1; end;
if (m>0) then
w[i]:=b[m-1];
else
w[i]:=b[0];
a[m-1]:=a[m-1]-1;
for j:=0 to m-1 do b[j]:=b[j]+1;
while ((m>1) and (a[m-1]=0)) do
begin
m:=m-1; b[m]:=1;
end;
end;
for i:= 0 to n-1 do
begin
write(w[i]); write(' ');
end;
writeln(' ');
end.
輸入：9
4 6 6 6 6 8 9 9 9 9
輸出：____________________
五. 完善程序（共2題，第1題每空3分；第2題每空2分。共計28分）。
1. 翻硬幣
題目描述：
一摞硬幣共有m枚，每一枚都是正面朝上。取下最上面的一枚硬幣，將它翻面后放回原處。然后取下最上面的2枚硬幣，將他們一起翻面后放回原處。在取3枚，取4枚……直至m枚。然后在從這摞硬幣最上面的一枚開始，重復剛才的做法。這樣一直做下去，直到這摞硬幣中每一枚又是正面朝上為止。例如，m為1時，翻兩次即可。
輸 入：僅有的一個數字是這摞硬幣的枚數m ，0< m <1000。
輸 出：為了使這摞硬幣中的每一枚都是朝正面朝上所必須翻的次數。
輸入樣例：30
輸出樣例：899
程 序：
program Program1;
var m:integer;
function solve(m: integer):integer;
var i,t,d: integer;
flag: Boolean;
begin
if (m = 1) then
solve := (1)
else begin
d := 2*m+1; t := 2; i := 1; flag := False;
repeat
if (t = 1) then
begin
solve := (2) ; flag := True;
end
else if ( (3) ) then
begin
solve := i*m-1; flag := True;
end
else
t := (4) ;
i:=i+1;
until flag;
end
end;
begin
read(m); if (( (5) ) and (m<1000)) then
writeln( (6) );
end.
2. OIM地形
題目描述：
二維離散世界有一種地形叫OIM(OI Mountain)。這種山的坡度只能上升('/')或下降('\'),而且兩邊的山腳都與地平線等高,山上所有地方都不低于地平線.例如：
/\ /\
/ \/\ 是一座OIM；而 / \ 不是。
\/
這個世界的地理學家們為了方便紀錄，給OIM所有可能的形狀用正整數編好號，而且每個正整數恰好對應一種山形。他們規定，若兩座山的寬度不同，則較寬的編號較大；若寬度相同，則比較從左邊開始第1個坡度不同的地方，坡度上升的編號較大。以下三座OIM的編號有小到大遞增：
/\ /\ /\ /\
/ \/\ / \/\/\ / \/ \。顯然/\的編號為1。但是地理學家在整理紀錄是發覺，查找編號與山形的對應關系不是很方便。他們希望能快速地從編號得到山的形狀。你自告奮勇答應他們寫一個程序，輸入編號，能馬上輸出山形。
輸 入：一個編號（編號大小不超過600,000,000），
輸 出：輸入編號所對應的山形，1座山所占行數恰為它的高度，即山頂上不能有多余空行。
輸入樣例：15
輸出樣例： /\ /\
/ \/ \
程 序：
program Program2;
const
L:integer =19; SZ: integer =50;
UP: char = '/'; DN: char = '\';
Var
i,nth,x,y,h,e,f:integer;
m: array[0..1,0..38,0..19] of integer;
pic: array[0..49,0..49] of char;

procedure init;
var k,s,a,b,c: integer;
begin
for a:=0 to 1 do
for b:=0 to 2*L do
for c:=0 to L do
m[a,b,c]:=0; m[0,0,0]:=1;
for k:=0 to 2*L-1 do
begin
for s:=1 to L do
begin
m[0,k+1,s] := m[0,k,s+1] + m[1,k,s+1];
m[1,k+1,s]:= (1) ;
end;
m[0,k+1,0] :=m[0,k,1]+m[1,k,1];
end;
end;

procedure draw(k,s,nth:integer);
begin
if (k=0) then exit;
if ((nth-m[1,k,s])>=0) then
begin
nth:=nth-m[1,k,s];
if (y>h) then (2) ;
pic[y,x]:=UP; y:=y+1; x:=x+1; draw( (3) );
end
else begin
y:=y - 1; pic[y,x]:=DN; x:=x+1; draw(k-1,s-1,nth);
end;
end;

begin
init;
read(nth);
for e:=0 to SZ-1 do
for f:=0 to SZ-1 do
pic[e,f]:= ' ';
x:=0;
y:=0
h:=0;
i:=0;

while ((nth-m[0,2*i,0])>=0) do
begin
nth:= nth-m[0,2*i,0];
(4) ;
end;
draw( (5) );
for i:=h downto x-1 do
begin
for e:=0 to x-1 do
write(pic[i,e]);
writeln(' ');
end;
end.
九屆分區提高組官方參考解答
一、單選10題 每題1.5分
B B D A B
B C E C B
二、不定項選擇10題 每題1.5分
D BDE AD AB AC
E B BCD D BE
三、問題求解 每題5分
1.答：11
2.答：4
四、閱讀程序 每題8分
1. 8910
2. 126
3. 1872
4. 1 1 2 4 5 1 1 3 9 （空格分隔）
五、完善程序
題一
（1）2
（2）i*m
（3）t=2*m
（4）(t*2) mod d
（5）m>0
（6）solve(m)
題二 OIM
（1）m[0,k,s-1]+m[1,k,s-1]
（2）h:=y
（3）k-1,s+1,nth
（4）i:=i+1
（5）2*i,0,nth
來自官方的參考解答，部分題目有可能存在其他正確解答。
各位選手可以自己估分，以上答案為紅色部分難度較大，正確率極低，一般選手正常發揮得分在55～65之間，最高得分估計不超過85分。
預計湖南、安徽、福建等地得分在50分以上的選手有把握進入復賽。初賽試題
第
全
學奧林匹克聯賽初賽試題
(提高組 Pascal語
小時完成)
●全部試題答案均要求寫在答卷紙上,寫在試卷紙上律無效
單項選擇題(共10題,每題1.5分,共計15分。每題有且僅有一個正確答案)
項
)不是CPU的組成部分
控制
板
算術邏
系數據庫
放在數據庫中的數據
叉樹
希
樹
維表
在下列各項中,只有(
算機存儲容
用單位
的含
一進制轉換碼
美國信息交換標準代
C.數字的二進制編
計算機可處理字符
用字符的二進制編碼
表達式
)的值是
判斷整數a等于0或b等于0或c等
確的條件表
地面上有標號為
3根約
柱上放
徑相
有孔的圓盤,從上
次編號為
的部分盤子經過B柱移入C柱
以在B柱上暫存。如果B柱
操作記錄為:“進,進
到上的盤子的編號為
初賽試題
進制數17.5625對應的8進制數是()
前4個答案都不對
歐拉圖G是指可以構成
圖,且圖
條邊恰好在這個閉回路上出現一次(即一筆
成)。在以下各個描述
是歐拉圖的是()
A.圖G中沒有度為奇數的頂點
次的閉路徑)
包含歐拉閉跡的圖(歐拉跡是指通過圖中每邊恰好一次的路徑
存在一條回路,通過每個頂點恰好一次
本身為閉跡的圖
無法靠自身的控制終止的循環稱為“死循環”,例如,在
(*”),”就
死循環
將無休止地打
關于死循環的說法中,只有(
是正確的
A.不存在一種算法,對任何一個程序及相應的輸入數據,都可以判斷是否會出現死循環,因而
任何編譯系統都不做死循環檢驗
死循環
法錯誤,既然編譯系統能檢査各
檢查出死循環
D.死循環與多進
現的“死鎖”差不多,而死鎖是可以檢測的,因而,死循環也
檢測
死循
等到發生時做現場處理,沒有
積極的手段
不定項選擇題(共10題,每題1.5分,共計15分。每題正確答案的個數大于或等
多選
或少選均不得分)
11.設A=B
輯運算表達式值為真的有()
C.A∧( BVCVD)
(A∧(DC)∧B
題
讀做P蘊涵Q,其
兩個獨立的命題
命題P成立而命題Q不成立
命題“
的值為
情況均為
命題“P→Q”等價的邏輯關系式
C.(1
000110
初賽試題
結點的二叉樹的先根遍歷
(數字為結點的編
后根遍
是
根遍
61
15.冗余數據
其他數據
數據,例如,數據庫中已存放了學生的數學、語文和英
的總分,則總分就可以看作冗余數
余數據
成數據的不一致
4個數據如果
操作錯誤使總分不等
關于冗余數據的說法
確的是
A.應該在數據
B.與用高級語言編寫的數據處理系統相
關系數據庫編寫的系統更容易消除冗余數據
提高査詢效率,在數據庫中可以適當保留一些冗余數據,但更新時要做相容性檢驗
D.做相容性檢驗會降低效率,可以不理睬數據庫
余數據
16.在下列各軟件中,屬
賽(復賽)推薦使用的語言環境有
斷電之后仍能保存數據
關于計算機語言的說氵
確的有(
級語言比匯編語言更高級,是因為它的程序的運行效率更
現,機
歷史舞
級語言程序比匯編語言程序更容易從一種計算機移植到另
機上
程的高級計算機語
算法復雜性的說氵
確的有(
是指它在某臺計算機上具體實現時的運行田
是指
算法的一種或兒種主要的運算,運算的次數與問題的規
數關
就意味著在解決該問題時
有多項式時間復雜度的算
但這一點還沒
實,也沒有被否定
題女
相同的結論
近20年來,許多
專家都大力推崇遞歸算法,認為它是解決較復雜問題的強有力的
列關于遞歸算法的說法第八屆全國青少年信息學奧林匹克聯賽（NOIP2002）初賽試題
（提高組 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)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.
第八屆全國青少年信息學奧林匹克聯賽（NOIP2002）初賽試題

（提高組參考答案）

一、 選擇一個正確答案代碼（A/B/C/D），填入每題的括號內（每題材1.5分，多選無分，共30分）。
題號 1 2 3 4 5 6 7 8 9 10
選擇 C A D A C B B D A D
題號 11 12 13 14 15 16 17 18 19 20
選擇 C B C B C B C B C B
二、 問題解答（6+8=14分）
1) 答：當n=5時，滿足以上條件的方法共有44種。
2) 答：n0和nk之間的關系為：n0=(k-1) nk+1。
三、 閱讀程序，并寫出程序的正確運行結果：（8+9+9分，共26分）
（１）程序的運行結果是：RRRRWWBBBB
（２）程序的運行結果是：30031
（３）程序的運行結果是：15.00（PASCAL） 15 (BASIC)
四、 根據題意，將程序補充完整（共30分）
PASCAL語言　　　　　　　　　　　BASIC語言
題一（每個點3分　共15分）
1 C[ n+1] 50 C(N+1)
2 (yu+d[j1]=C(J1+1)
3 yu:=yu+d[j1]; 90 YU=YU+D(J1)
4 e[j0]:=s; 110 E(J0)=S
5 write(e[I`]:4); 140 PRINT E(I);
題二（每個點3分　共15分）
1 p and(b[0]=0) 90 (P=0) OR(B(0)<>0
2 b[j]:=1; 140 B(J)=1
3 p:=false; 160 P=0
4 (a[i,j]=-1)and(b[j]=1) 190 ((A(I,J)=-1)AND(B(J)=1))
5 P 220 P=1


批準：中國科協、教育部 主辦：中國計算機學會
承辦：山西省計算機學會 2002-10-27發布第十一屆全國青少年信息學奧林匹克聯賽初賽試題
（ 提高組pascal 語言二小時完成）
●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效●●
一、單項選擇題（共10題，每題1.5分，共計15分。每題有且僅有一個正確答案.）。
1. 字符串“ababacbab”和字符串“abcba”的最長公共子串是（ ）。
A. abcba B. cba C. abc D. ab E. bcba
2. 設全集I = {a, b, c, d, e, f, g, h}，集合B A = {a, b, c, d, e, f}， C A = {c, d, e}，
~B A= {a, d}，那么集合C B A 為（ ）。
A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f}
3. 以下二進制數的值與十進制數23.456 的值最接近的是（ ）。
A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111
4. 完全二叉樹的結點個數為4 * N + 3，則它的葉結點個數為（ ）。
A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2
5. 平面上有五個點A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以這五點作為完全圖G 的頂點，
每兩點之間的直線距離是圖G 中對應邊的權值。圖G 的最小生成樹中的所有邊的權值
綜合為（ ）。
A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 5
6. 下列設備中沒有計算功能的是（ ）。
A. 筆記本電腦B. 掌上電腦C. 智能手機
D. 電子計算器E. 液晶顯示器
7. Intel的首顆64 位處理器是（ ）。
A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium
8. 常見的郵件傳輸服務器使用（ ）協議發送郵件。
A. HTTP B. SMTP C. TCP D. FTP E. POP3
9. 不能在Linux 上使用的網頁瀏覽器是（ ）。
A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla
10. 一位藝術史學家有20000 幅1024 * 768 的真彩色圖像，如果將這些圖像以位圖形式保存
在CD 光盤上（一張CD 光盤的容量按600M計算），大約需要（ ）張CD光盤。
A. 1 B. 10 C. 100 D. 1000 E. 10000
二、不定項選擇題（共10題，每題1.5分，共計15分。多選或少選均不得分）。
11. 設A = true，B = false，C = false，D = true，以下邏輯運算表達式值為真的有（ ）。
A. (A B ∧ )∨(C D ∧ ) B. ((A B ∧ ) C ∨ ) D ∧ C. A∧((B C ∨ ) D ∨ )
D. (A∧(B C ∨ )) D ∨ E. (A B ∨ )∧(C D ∨ )
12. (3725)8 + (B)16的運算結果是（ ）。
A. (3736)8 B. (2016)10 C. (11111100000)2 D. (3006)10 E. (7E0)16
13. 二叉樹T的寬度優先遍歷序列為A B C D E F G H I，已知A是C的父結點，D 是G 的
父結點，F 是I 的父結點，樹中所有結點的最大深度為3（根結點深度設為0），可知E
的父結點可能是（ ）。
A. A B. B C. C D. D E. F
14. 設棧S的初始狀態為空，元素a, b, c, d, e, f, g依次入棧，以下出棧序列不可能出現的有
（ ）。
A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g
D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a
15. 下列外設接口中可以通過無線連接的方式連接設備的是（ ）。
A. USB 2.0 高速版B. 紅外C. 藍牙D. 串口E. IEEE 802.11g 無線網卡
16. 處理器A 每秒處理的指令數是處理器B 的2 倍。某一特定程序P 分別編譯為處理器A
和處理器B 的指令，編譯結果處理器A 的指令數是處理器B 的4 倍。已知程序P 的算
法時間復雜度為O(n2)，如果處理器A執行程序P時能在一小時內完成的輸入規模為n，
則處理器B執行程序P時能在一小時內完成的輸入規模為（ ）。
A. 4 * n B. 2 * n C. n D. n / 2 E. n / 4
17. 以下哪個（些）不是計算機的輸出設備（ ）。
A. 鼠標B. 顯示器C. 鍵盤D. 掃描儀E. 繪圖儀
18. 以下斷電之后將不能保存數據的有（ ）。
A. 硬盤B. 寄存器C. 顯存D. 內存E. 高速緩存
19. 下列活動中屬于信息學奧賽系列活動的是（ ）。
A. NOIP B. NOI C. IOI D. 冬令營E. 國家隊選拔賽
20. 下列關于高級語言的說法正確的有（ ）。
A. Ada 是歷史上的第一個高級語言
B. Pascal和C都是編譯執行的高級語言
C. C++是歷史上的第一個支持面向對象的語言
D. 編譯器將高級語言程序轉變為目標代碼
E. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上
三．問題求解（請在空格處填上答案，每空5分，共計10分）
1. 將數組{32, 74, 25, 53, 28, 43, 86, 47}中的元素按從小到大的順序排列，每次可以交換任
意兩個元素，最少需要交換次。
2. 取火柴游戲的規則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1 根或
2 根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，
先取者沒有必勝策略記為0。當N 分別為100，200，300，400，500 時，先取者有無必
勝策略的標記順序為（回答應為一個由0 和/或1 組成的字符串）。
四．閱讀程序（共4題，每題8分，共計32 分）
1． var
a, b, c, p, q : integer;
r : array[0..2] of integer;
begin
read(a, b, c);
p := a div b div c;
q := b - c + a + p;
r[0] := a * p div q * q;
r[1] := r[0] * (r[0] - 300);
if (3 * q - p mod 3 <= r[0]) and (r[2] = r[2]) then
r[1] := r[r[0] div p mod 2]
else r[1] := q mod p;
writeln(r[0] - r[1]);
end.
輸入：100 7 3
輸出：
2． var
a : array [1..50] of integer;
n, i, sum : integer;
procedure work(p, r: integer);
var
i, j, temp : integer;
begin
if p < r then begin
i := p - 1;
for j := p to r - 1 do
if a[j] >= a[r] then begin
inc(i);
temp := a[i]; a[i] := a[j]; a[j] := temp;
end;
temp := a[i + 1]; a[i + 1] := a[r]; a[r] := temp;
work(p, i);
work(i + 2, r);
end;
end;
begin
read(n);
for i := 1 to n do read(a[i]);
work(1, n);
for i := 1 to n - 1 do sum := sum + abs(a[i + 1] - a[i]);
writeln(sum);
end.
輸入：10 23 435 12 345 3123 43 456 12 32 -100
輸出：
3． var
str : string;
len, i, j : integer;
nchr : array [0..25] of integer;
mmin : char;
begin
mmin := 'z';
readln(str);
len := length(str);
i := len;
while i >= 2 do begin
if str[i - 1] < str[i] then break;
dec(i);
end;
if i = 1 then begin
writeln('No result!');
exit;
end;
for j := 1 to i - 2 do write(str[j]);
fillchar(nchr, sizeof(nchr), 0);
for j := i to len do begin
if (str[j] > str[i - 1]) and (str[j] < mmin) then
mmin := str[j];
inc(nchr[ord(str[j]) - ord('a')]);
end;
dec(nchr[ord(mmin) - ord('a')]);
inc(nchr[ord(str[i - 1]) - ord('a')]);
write(mmin);
for i := 0 to 25 do
for j := 1 to nchr[i] do
write(chr(i + ord('a')));
writeln;
end.
輸入：zzyzcccbbbaaa
輸出：
4. var
n : longint;
function g(k : longint) : longint;
begin
if k <= 1 then g := k
else g := (2002 * g(k - 1) + 2003 * g(k - 2)) mod 2005;
end;
begin
read(n);
writeln(g(n));
end.
輸入：2005
輸出：
五．完善程序(前5空，每空2分，后6空，每空3分，共28分)
1．木材加工
題目描述:
木材廠有一些原木，現在想把這些木頭切割成一些長度相同的小段木頭（木頭有可能有
剩余），需要得到的小段的數目是給定的。當然，我們希望得到的小段越長越好，你的任務
是計算能夠得到的小段木頭的最大長度。
木頭長度的單位是cm。原木的長度都是正整數，我們要求切割得到的小段木頭的長度
也是正整數。
輸入:
第一行是兩個正整數N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的數目，
K是需要得到的小段的數目。
接下來的N行，每行有一個1到10000之間的正整數，表示一根原木的長度。
輸出:
輸出能夠切割得到的小段的最大長度。如果連1cm長的小段都切不出來，輸出”0”。
輸入樣例:
3 7
232
124
456
輸出樣例:
114
程序：
var
n, k : integer;
len : array [1..10000] of integer;
i, left, right, mid : integer;
function isok(t : integer) : boolean;
var
num, i : integer;
begin
num := 0;
for i := 1 to n do begin
if num >= k then break;
num := ① ;
end;
if ② then isok := true
else isok := false;
end;
begin
readln(n, k);
right := 0;
for i := 1 to n do begin
readln(len[i]);
if right < len[i] then right := len[i];
end;
inc(right);
③ ;
while ④ < right do begin
mid := (left + right) div 2;
if ⑤ then right := mid
else left := mid;
end;
writeln(left);
end.
2．N叉樹
題目描述:
我們都了解二叉樹的先根遍歷，中根遍歷和后根遍歷。當知道先根遍歷的結果和中根遍
歷結果的時候，我們可以唯一的確定二叉樹；同樣的，如果知道了后根遍歷的結果和中根遍
歷結果，二叉樹也是唯一確定的。但是如果只知道先根遍歷和后根遍歷的結果，二叉樹就不
是唯一的了。但是我們可以計算滿足條件的不同二叉樹一共有多少個。這不是一個很困難的
問題，稍微復雜一點，我們把這個問題推廣到N叉樹。
我們用小寫英文字母來表示N 叉樹的結點，不同的結點用不同的字母表示。比如，對
于4叉樹，如果先根遍歷的結果是abdefgc，后根遍歷的結果是defgbca，那么我們可以
得到6個不同的4叉樹（如下圖）。
輸入:
輸入數據包括3行。
第一行是一個正整數N(2 ≤ N ≤ 20)，表示我們要考慮N叉樹。
第二行和第三行分別是兩個字符串序列，分別表示先根遍歷和后根遍歷的結果。
輸出:
輸出不同的N叉樹的數目。題目中給的數據保證得到的結果小于2
31
。
輸入樣例:
4
abdefgc
defgbca
輸出樣例:
6
程序：
var
str1, str2 : string;
N, len : integer;
com : array[0..100, 0..100] of longint;
function getcom(x, y : integer) : longint;
begin
if (y = 0) or (x = y) then ①
else if com[x][y] <> 0 then getcom := com[x][y]
else begin
com[x][y] := getcom(x - 1, y)+ ② ;
getcom := com[x][y];
end;
end;
function count(a, b, c : integer) : longint;
var
sum : longint;
k, s, t, p : integer;
begin
sum := 1; k := 0; s := a + 1; t := c;
if a = b then count := 1
else begin
while s <= b do begin
p := t;
while str1[s] <> str2[t] do inc(t);
sum := sum * count(s, s + t - p, p);
s := ③ ;
④ ; inc(k);
end;
count := ⑤ * getcom(N, k);
end;
end;
begin
readln(N); readln(str1); readln(str2);
len := length(str1);
writeln(count( ⑥ ));
end.
第十一屆全國青少年信息學奧林匹克聯賽初賽
提高組(P)參考答案
單項選擇題 （共10題，每題1.5分，共計15分。每題有且僅有一個正確答案.）。
題號 1 2 ３ 4 5 6 7 8 9 10
選擇 B A D E D E E B A C
二．不定項選擇題 （共10題，每題1.5分，共計15分。多選或少選均不得分）。
題號 11 12 13 14 15 16 17 18 19 20
選擇 CDE BCE BC CE BCE B ACD BCDE ABCDE BDE
三．問題求解（共2題，每題5分，共計10分）
答： 5
答： 11011
四. 閱讀程序（共4題，每題8分，共計32分）
（1）程序的運行結果是: -7452
(2) 程序的運行結果是: 3223
（3）程序的運行結果是: zzzaaabbbcccy
（4）程序的運行結果是: 31
五. 完善程序 (前5空，每空2分，后6空，每空3分，共28分)
pascal語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
（1） num + len[i] div t 　
（2） num >= k 　　　　 　
（3） left := 0 　　
（4） left + 1 　　
（5） not isok(mid) （或者 isok(mid) = false） 　　
2.
（1） getcom := 1
（2） getcom(x - 1, y - 1)
（3） s + t - p + 1
（4） inc(t) （或者t := t + 1）
（5） sum
（6） 1, len, 1NOIP2007年提高組（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)第七屆分區聯賽提高組初賽
(提高組PASCAL語言　二小時完成)
一、選擇一個正確答案代碼(A/B/C/D)，填入每題的括號內(每題1.5分，多選無分，共30分)
1、中央處理器CPU能訪問的最大存儲器容量取決于( )
　A)地址總線 　B)數據總線 　C)控制總線　 D)內存容量
2、計算機軟件保護法是用來保護軟件( )的。
　A)編寫權 　B)復制權 　C)使用權 　D)著作權
3、64KB的存儲器用十六進制表示，它的最大的地址碼是( )
　A)10000 　B)FFFF 　C)1FFFF 　D)EFFFF
4、在樹型目錄結構中，不允許兩個文件名相同主要指的是( )
　A)同一個磁盤的不同目錄下 　B)不同磁盤的同一個目錄下
　C)不同磁盤的不同目錄下 　 C)同一個磁盤的同一個目錄下
5、下列設備哪一項不是計算機輸入設備( )
　A)鼠標 　B)掃描儀 　C)數字化儀 　D)繪圖儀
6、在計算機硬件系統中，cache是( )存儲器
　A)只讀 　B)可編程只讀 　C)可擦除可編程只讀 　D)高速緩沖
7、若我們說一個微機的CPU是用的PII300，此處的300確切指的是( )
　A)CPU的主時鐘頻率 　　　　B)CPU產品的系列號
　C)每秒執行300百萬條指令 　D)此種CPU允許最大內存容量
8、Email郵件本質上是一個( )
　A)文件 　B)電報 　C)電話 　D)傳真
9、2KB的內存能存儲( )個漢字的機內碼
　A)1024 　B)516 　C)2048 　D)218
10、以下對Windows的敘述中，正確的是( )
　A)從軟盤上刪除的文件和文件夾，不送到回收站
　B)在同一個文件夾中，可以創建兩個同類、同名的文件
　C)刪除了某個應用程序的快捷方式，將刪除該應用程序對應的文件
　D)不能打開兩個寫字板應用程序
11、運算式(2047)10—(3FF)16+(2000)8的結果是( )
　A)(2048)10 　B)(2049)10 　C)(3746)8 　D)(1AF7)16
12、TCP/IP協議共有( )層協議
　A)3 　 B)4 　C)5 　D)6
13.若已知一個棧的入棧順序是1，2，3，…，n，其輸出序列為P1，P2，P3，…，Pn，若P1是n，則Pi是( )
　A)i 　B)n-1 　C)n-i+1 　D)不確定
14.計算機病毒是( )
　A)通過計算機傳播的危害人體健康的一種病毒
　B)人為制造的能夠侵入計算機系統并給計算機帶來故障的程序或指令集合
　C)一種由于計算機元器件老化而產生的對生態環境有害的物質
　D)利用計算機的海量高速運算能力而研制出來的用于疾病預防的新型病毒
15.下面關于算法的錯誤說法是( )
　A)算法必須有輸出 　B)算法必須在計算機上用某種語言實現
　C)算法不一定有輸入 D)算法必須在有限步執行后能結束
16.[x]補碼=10011000，其原碼為( )
　A)011001111 　B)11101000 　C)11100110 　D)01100101
17.以下哪一個不是棧的基本運算( )
　A)刪除棧頂元素 　B)刪除棧底的元素 　
　C)判斷棧是否為空 D)將棧置為空棧
18.在順序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的關鍵碼比較的次數為( )
　A)2 　B)3 　C)4 　D)5
19.一棵二叉樹的高度為h，所有結點的度為0，或為2，則此樹最少有( )個結點
　A)2h-1 　B)2h-1 　C)2h+1 　D)h+1
20.無向圖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)},對該圖進行深度優先遍歷,得到的頂點序列正確的是( )
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
二、問題求解(5+7=12分)
1.已知一棵二叉樹的結點名為大寫英文字母，其中序與后序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序為：
2.平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形？
三、閱讀程序，寫出程序正確的運行結果(4+7+8+9=28分)
1.PROGRAM GAO7_1：
　FUNCTION ACK(M，N：INTEGER)：INTEGER；
　　BEGIN
　　　IF M=0 THEN ACK：=N+1
　　　　　　 ELSE IF N=0 THEN ACK:=ACK(M-1，1)
　　　　　　　　　　　　 ELSE ACK:=ACK(M-1，ACK(M，N-1))
　　END；
　　 BEGIN WRITELN(ACK(3，4))； READLN； END.
輸出
2.PROGRAM GAO7_2；
　VAR P，Q，S，T：INTEGER；
　BEGIN
　　READLN(P)；
　　FOR Q：=P+1 TO 2*P DO
　　BEGIN
　　　T:=0；S:=(P*Q)MOD(Q-P)；
　　　IF S=0 THEN BEGIN T:=P+Q+(P*Q)DIV(Q-P)；WRITE(T：4)；END；
　　 END；
　　END.
輸入12　　　輸出
3.PROGRAM GAO7_3；
　VAR I，J，H，M，N，K：INTEGER；
　　　B ：ARRAY[1..10]OF INTEGER；
　BEGIN
　　READLN(N)；
　　　FOR I:=1 TO 10 DO
　　　　BEGIN
　　　　M：=N；J：=11；
　　　　WHILE M>0 DO
　　　　　BEGIN J:=J-1；B[J]：=M MOD 10；M:=M DIV 10 END；
　　　　FOR H:=J TO 10 DO N:=N+B[H]；
　　　　END；
　　 WRITELN(N)；
　END.
輸入1234　　　輸出：
4.PROGRAM GAO7_4；
　VAR X，Y1，Y2，Y3：INTEGER；
　BEGIN
　　READLN(X)；Y1：=0；Y2：=1；Y3：=1；
　　WHILE Y2<=X DO
　　　BEGIN
　　　　Y1：=Y1+1；Y3：=Y3+2；Y2：=Y2+Y3
　　　 END；
　　　WRITELN(Y1)；
　　END.
輸入：23420　　輸出：
四、完善程序(每空3分，共30分)
　　1.存儲空間的回收算法。設在內存中已經存放了若干個作業A，B，C，D。其余的空間為可用的(如圖一中(a))。
　　此時，可用空間可用一個二維數組dk[1..100，1..2 ]表示，(如下表一中(a))，其中：dk[i，1]對應第i個可用空間首址，dk[i，2]對應第i個可用空間長度如上圖中，dk：
1005030010050100 0 0100 50 300100 500 10010000 0
表一(a) 表一(b)
　　現某個作業釋放一個區域，其首址為d，長度為L，此時將釋放區域加入到可用空間表中。要求在加入時，若可用空間相鄰時，則必須進行合并。因此出現下面的4種情況(如上圖一(b)所示)。
　(1)下靠，即回收區域和下面可用空間相鄰，例如，d=80，L=20，此時成為表二中的(a)。
　(2)上靠，例如，d=600，L=50，此時表成為表二中的(b)。
　(3)上、下靠，例如，d=150，L=150，此時表成為表二中的(c)。
　(4)上、下不靠，例如，d=430，L=20，此時表成為表二中的(d)。
80 70
300 100
50 100
10050300100500150
100
300
500
100 1005030010043020500100
表二(a)(下靠) 表二(b)(上靠) 表二(c)(上，下靠) 表二(d)(上，下不靠)
程序說明：對數組dk預置2個標志，即頭和尾標志，成為表二中(b)，這樣可使算法簡單，sp為dk表末地址。
程序清單：
PROGRAM GAO7_5；
　VAR I，J，SP，D，L：INTEGER；
　　　DK ：ARRAY[0..100，1..2]OF INTEGER；
　BEGIN
　　READLN(SP)；
　FOR I:=1 TO SP DO
　　READLN(DK[I，1]，DK[I，2])；
　　DK[0，1]:=0；DK[0，2]:=0；　①　；
　　DK[SP，1]:=10000；DK[SP，2]:=0；READLN(D，L)；I:=1；
　WHILE DK[I，1]　IF(DK[I，1]+DK[I，2]=D)THEN
　　　　　　　　　　　　　　　IF(D+L=DK[I+1，1])THEN
　　　　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　　　　DK[I，2]:=　③　　；
　　　　　　　　　　　　　　　　　FOR J:=I+1 TO SP-1 DO
　　　　　　　　　　　　　　　　　　DK[J]:=DK[J+1]；
　　　　　　　　　　　　　　　　　SP：=SP-1；
　　　　　　　　　　　　　　　　 END
　　　　　　　　　　　　　　　 ELSE DK[I，2]:=DK[I，2]+L
ELSE IF(D+L=DK[I+1，1])THEN
　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　DK[I+1，1]::=　④　；DK[I+1，2]:=DK[I+1，2]+L
　　　　　　　　　　　　　END
　　 ELSE BEGIN
　　　　　　FOR J:=SP DOWNTO I+1 DO　　DK[J+1]:=DK[J]；
　　　　　　　⑤　:=D；　　　DK[I+1，2]:=L；SP:=SP+1；
　　　　　END；
　FOR I:=1 TO SP-1 DO　 WRITELN(DK[I，1]:4，DK[I，2]:4)；READLN；
END.
2.求關鍵路徑
　設有一個工程網絡如下圖表示(無環路的有向圖)：
　其中，頂點表示活動，①表示工程開始，⑤表示工程結束(可變，用N表示)，邊上的數字表示活動延續的時間。
如上圖中，活動①開始5天后活動②才能開始工作，而活動③則要等①、②完成之后才能開始，即最早也要7天后才能工作。
　在工程網絡中，延續時間最長的路徑稱為關鍵路徑。上圖中的關鍵路徑為：①—②—③—④—⑤共18天完成。
　關鍵路徑的算法如下：
1.數據結構：
　R[1..N，1..N]OF INTEGER；　　　表示活動的延續時間，若無連線，則用-1表示；
　EET[1..N]　　　　　　　　　　　表示活動最早可以開始的時間
　ET[1..N]　　　　　　　　　　 　表示活動最遲應該開始的時間
關鍵路徑通過點J，具有如下的性質：EET[J]=ET[J]
2.約定：
　結點的排列已經過拓撲排序，即序號前面的結點會影響序號后面結點的活動。
程序清單：
PROGRAM GAO7_6；
　VAR I，J，N，MAX，MIN，W，X，Y：INTEGER；
　　　R：ARRAY[1..20，1..20]　OF INTEGER；
　　　EET，ET：ARRAY[1..20]　OF INTEGER；
　BEGIN
　　READLN(N)
　　FOR I:=1 TO N DO
　　　FOR J:=1 TO N DO
　　　　R[I，J]:=-1；
　　READLN(X，Y，W)；{輸入從活動X到活動Y的延續時間，以0為結束}
　WHILE X<>0 DO
　　　BEGIN
　　　　R[X，Y]:=W；　①　
　　　END；
　　EET[1]：=0；{認為工程從0天開始}
　　FOR I：=2 TO N DO
　　　BEGIN
　　　　MAX:=0；
　　　　FOR J:=1 TO N DO
　　　　　IF R[J，I]<>-1 THEN
　　　　　　　IF　②　THEN MAX:=R[J，I]+EET[J]；
　　　　EET[I]:=MAX；
　　　END；
　　　　③　
　　　FOR I：=N-1 DOWNTO 1 DO
　　　　BEGIN
　　　　　MIN：=10000；
　　　　　FOR J：=1 TO N DO
　　　　　　IF R[I，J]<>-1 THEN
　　　　　　　　IF　④　THEN MIN：=ET[J] - R[I，J]；
　　　　　　　ET[I]：=MIN；
　　　　　　END；
　　　　WRITELN(EET[N])；
　　　　FOR I：=1 TO N -1 DO
　　　　　IF　⑤　THEN WRITE(I，'→')；
　　WRITE(N)；READLN
END.
（提高組參考答案）

一、選擇一個正確答案代碼（A/B/C/D），填入每題的括號內（每題1.5分，多選無分，共30分）

題號 1 2 3 4 5 6 7 8 9 10
選擇 A D B D C D A A A A
題號 11 12 13 14 15 16 17 18 19 20
選擇 A C C B B B B C B D

二、問題解答（5+7分，兩題共12分）
1、答：該二叉樹先序遍歷的順序為：ABCEGDFHIJ

2、答：這些點為頂點，能組成2250個不同四邊形

三、閱讀程序，并寫出程序的正確運行結果：（4+7+8+9分，共28分）
（1）程序的運行結果是：125（PASCAL） S=1055（BASIC）
（2）程序的運行結果是：181 110 87 76 66 62 61 60
（3）程序的運行結果是：1348
（4）程序的運行結果是：153

四、根據題意，將程序補充完整（每個點3分，共30分）

PASCAL 語言 BASIC語言

題一
（1）SP：=SP+1 65 SP：=SP+1
（2）I：I-1 100 K=K-1
（3）DK[I，2]+L+DK[I+1，2] 130 A（K，2）+L+A（K+1，2）
（4）D 410 D
(5) D K[I+1，1] 450 A（K+1，1）

題二
（1）READLN（X，Y，W） 100 GOTO 70
(2) R[J, I+EET[J]>MAX 150 R(J,I)+ EET[J]>MAX
(3)ET[N]:=EET[N] 180 ET(N)=EET(N)
(4) ET[J]-R[I,J](5) EET[I]=ET[I] 280 EET(I)=ET(I)

主管：中國科協、教育部 主辦：中國計算機學會 承辦：江蘇省科協青少年科技中心第六屆全國青少年信息學（計算機）奧林匹克分區聯賽試題
（ 提高組 PASCAL 語言 二小時完成 ）
● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、選擇一個正確答案代碼（A/B/C/D），填入每題的括號內 (每題1.5分，多選無分，共30分）
1．下列無符號數中，最小的數是（ ）。
A．（11011001）2 B．（75）10 C．（37）8 D．（2A）16
2．在外部設備中，繪圖儀屬于（ ）。
A．輸入設備 B．輸出設備 C．輔（外）存儲器 D．主（內）存儲器
3．計算機主機是由CPU 與（ ）構成的。
A．控制器 B。輸入、輸出設備 C．運算器 D．內存儲器
4．計算機病毒的特點是（ ）。
A．傳播性、潛伏性、易讀性與隱蔽性 B．破壞性、傳播性、潛伏性與安全性
C．傳播性、潛伏性、破壞性與隱蔽性 D．傳播性、潛伏性、破壞性與易讀性
5．WINDOWS 9X 是一種（ ）操作系統。
A．單任務字符方式 B．單任務圖形方式
C．多任務字符方式 D．多任務圖形方式
6．Internet 的規范譯名應為（ ）。
A．英特爾網 B．因特網 C． 萬維網 D．以太網
7．計算機網絡是一個（ ）系統。
A．管理信息系統 B．管理數據系統
C．編譯系統 D．在協議控制下的多機互連系統
8．計算機系統總線上傳送的信號有（ ）。
A．地址信號與控制信號 B．數據信號、控制信號與地址信號
C．控制信號與數據信號 D．數據信號與地址信號
9．計算機的運算速度取決于給定的時間內，它的處理器所能處理的數據量。處理器一次能處理
的數據量叫字長。已知64位的奔騰處理器一次能處理64個信息位，相當于（ ）字節。
A．8個 B．1 個 C．16個 D．2個
10．某種計算機的內存容量是640K，這里的640K容量是指（ ）個字節。
A．640 B．640*1000 C．640 * 1024 D．640*1024*1024
11．下面哪些計算機網絡不是按覆蓋地域劃分的（ ）。
A．局域網 B．都市網 C．廣域網 D．星型網
12．在有N個葉子節點的哈夫曼樹中，其節點總數為（ ）
A．不確定 B．2N-1 C．2N+1 D．2N
13．已知數組A中，每個元素A[I，J]在存貯時要占3個字節，設I從1變化到8，J從1變化到10，分配內存時是從地址SA開始連續按行存貯分配的。
試問：A[5，8]的起始地址為（ ）。
A．SA+141 B．SA+180 C．SA+222 D．SA+225
14．不同類型的存儲器組成了多層次結構的存儲器體系，按存取速度從快到慢的排列是（ ）。
A．快存 / 輔存 / 主存 B．外存 / 主存 / 輔存
C．快存 / 主存 / 輔存 D．主存 / 輔存 / 外存
15．某數列有1000個各不相同的單元，由低至高按序排列；現要對該數列進行二分法檢索（binary search），在最壞的情況下，需檢視（ ）個單元。
A．1000 B．10 C．100 D．500
16．請仔細閱讀下列程序段:
PASCAL 語言 BASIC 語言
上列程序段的正確輸出是（ ）。
A．-1　　　 　B．-2　　 　C．-3 D．-4
17．線性表若采用鏈表存貯結構，要求內存中可用存貯單元地址（ ）。
A．必須連續 B．部分地址必須連續
C．一定不連續 D．連續不連續均可
18．下列敘述中，正確的是（ ）。
線性表的線性存貯結構優于鏈表存貯結構
隊列的操作方式是先進后出
棧的操作方式是先進先出
D．二維數組是指它的每個數據元素為一個線性表的線性表
19．電線上停著兩種鳥（A，B），可以看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可分為兩類：一類是兩端的小鳥相同；另一類則是兩端的小鳥不相同。已知：電線兩個頂點上正好停著相同的小鳥，試問兩端為不同小鳥的線段數目一定是（ ）。
A．奇數 B．偶數 C．可奇可偶 D．數目固定
一個文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角則以（80，25）表示，屏幕上每一個字符佔用兩字節（byte），整個屏幕則以線性方式存儲在電腦的存儲器內，由屏幕左上角開始，位移為0，然后逐列逐列存儲。
求位于屏幕（X，Y）的第一個字節的位移是（ ）。
A．(Y * 80 + X) * 2 - 1
B．((Y - 1) * 80 + X - 1) * 2
C．(Y * 80 + X - 1) * 2
D．((Y - 1) * 80 + X) * 2 - 1
二、問題求解（6＋6＝12分）
1．已知，按中序遍歷二叉樹的結果為：abc
問：有多少種不同形態的二叉樹可以得到這一遍歷結果，并畫出這些二叉樹。
2．設有一個共有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當n=3時，共有4種走法，即1+1+1,1+2,2+1,3。
三、閱讀程序，并寫出正確的運行結果（每題10分，共20分）
program noi_003;
const n=7; m=6;
var i,j,x0,y0,x1,y1,x2,y2:integer;
d:real; p:boolean; g:array[0..n,0..m] of 0..1;
function disp(x1,y1,x2,y2:integer):real;
begin disp:=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); end;
begin
for i:=0 to n do for j:=0 to m do g[i,j]:=0;
readln(x1,y1,x2,y2); g[x1,y1]:=1; g[x2,y2]:=1; p:=true;
while p do
begin
p:=false; d:=disp(x1,y1,x2,y2); x0:=x1; y0:=y1;
for i:=4 to n do for j:=0 to m do
if (d>disp(i,j,x2,y2)) and (g[i,j]=0) then
begin d:=disp(i,j,x2,y2); x0:=i; y0:=j; end;
if (x0<>x1) or (y0<>y1) then
begin x1:=x0; y1:=y0; p:=true;g[x1,y1]:=1; end;
d:=disp(x1,y1,x2,y2); x0:=x2; y0:=y2;
for i:=0 to 3 do for j:=0 to m do
if (dbegin d:=disp(x1,y1,i,j);x0:=i;y0:=j end;
if (x0<>x2) or (y0<>y2) then
begin x2:=x0; y2:=y0; p:=true; g[x2,y2]:=1; end;
end; WRITELN（X1，Y1，X2，Y2）
end.
輸入： 7 6 0 0
輸出：
2.
program noi_002;
var i,j,l,n,k,s,t:integer; b:array[1..10] of 0..9;
begin
readln(l,n); s:=l; k:=1; t:=l;
if n>l then begin
while sbegin k:=k+1;t:=t*l;s:=s+t end;
s:=s-t;n:=n-s-1;
for i:=1 to 10 do b[i]:=0;
j:=11;
while n>0 do
begin j:=j-1;b[j]:=n mod l;n:=n div l end;
for i:=10-k+1 to 10 do write(chr(ord('A')+b[i]));
readln;
end
else writeln(chr(ord('A')+n-1))
end.
輸入 ： 4 167 輸出：
四、完善程序（共38分）
問題描述
　　將2n個0和2n 個1，排成一圈。從任一個位置開始，每次按逆時針的方向以長度為n+1的單位進行數二進制數。
要求給出一種排法，用上面的方法產生出來的2ｎ＋１個二進制數都不相同。
例如，當n=2時, 即2２個0 和2２個1 排成如下一圈：
比如，從A位置開始，逆時針方向取三個數000，然后再從B位置上開始取三個數001，接著從C開始取三個數010，…，可以得到000，001，010，101，011，111，110，100共8個二進制數且都不相同。
程序說明
以n=4為例，即有16個0，16個1，
數組a用以記錄32個0，1的排法，
數組b統計二進制數是否已出現過。
程序清單
Program noi00;
var
a : array[1..36] of 0..1;
b :array[0..31] of integer;
i, j, k, s, p : integer;
Begin
for i:=1 to 36 do a[i]:=0;
for i:=28 to 32 do a[i]:=1;
p:=1; a[6]:=1;
while (p=1) do
begin
j:=27;
while a[j]=1 do j:=j-1;
①
for i:=j+1 to 27 do ②
for i:=0 to 31 do b[i]:=0;
for i:=1 to 32 do
begin
③
for k:=i to i+4 do s:=s*2+a[k];
④
end;
s:=0;
for i:=0 to 31 do s:=s+b[i];
if ⑤ then p:=0
end;
for i:=1 to 32 do FOR J：=I TO I+4 DO write(a[J]);
writeln
End.
2．問題描述
求出一棵樹的深度和寬度。例如有如下的一棵樹：
①
/ ∣ \
② ③ ④
/ /
⑤ ⑥
\
⑦
其樹的深度為從根結點開始到葉結點結束的最大深度, 樹的寬度為同一層上結點數的最大值。在上圖中樹的深度為4，寬度為3。
用鄰接表來表示樹，上圖中的樹的鄰接表見表1.
程序說明：
數組 tree表示樹,用鄰接表來表示(假設樹的度為4)
數組 q表示隊列，其中SP1——取出指針，SP2——存入指針，q[i,0]表示層數
數組 d，統計同一層上的結點數(假設≤20層)
表1
１ ２ ３ ４ ０ ０
２ ０ ０ ０ ０ ０
３ ５ ０ ０ ０ ０
４ ６ ０ ０ ０ ０
５ ０ ０ ０ ０ ０
６ ７ ０ ０ ０ ０
７ ０ ０ ０ ０ ０
程序清單
program noi00_6;
var i, j, sp1, sp2, l, max : integer; tree:array[1..20,1..6] of integer;
q: array[1..100,0..6] of integer; d: array[0..20] of integer;
begin
for i:=1 to 14 do for j:=1 to 6 do tree[i,j]:=0;
for j:=1 to 14 do tree[j,1]:=j;
tree[1,2]:=2; tree[1,3]:=3; tree[1,4]:=4; tree[2,2]:=5; tree[2,3]:=6;
tree[3,2]:=7; tree[3,3]:=8; tree[4,2]:=9; tree[4,3]:=10; tree[4,4]:=11;
tree[7,2]:=12; tree[7,3]:=13; tree[13,2]:=14;
sp1:=1; sp2:=1;
for i:=1 to 6 do q[1,i]:=tree[1,i];
q[1,0]:=1;
while ① do
begin
l:= ② ; j:=2;
while ③ do
begin
sp2:=sp2+1; q[sp2,0]:=l; q[sp2,1]:=q[sp1,j];
for i:=2 to 6 do
q[sp2,i]:=tree[q[sp1,j],i];
j:=j+1
end;
sp1:=sp1+1
end;
writeln ④ ;
for i:=0 to 20 do d[i]:=0;
for i:=1 to sp2 do
d[q[i,0]]:= ⑤ ;
max:=d[1];
for i:=2 to 20 do
if d[i]>max then max:=d[i];
writeln(max);
readln;
end.
賽區 市 學校 姓名
========================== 密 封 線 =======================
第六屆全國青少年信息學（計算機）奧林匹克分區聯賽初賽試題
提高組答卷紙
閱 卷 記 錄
總閱卷人 總 得 分
第 一 大 題 得 分 第二大題得分
題號 1 2 3 4 5 6 7 8 9 10 第三大題得分
得分 (1) (2)
題號 11 12 13 14 15 16 17 18 19 20 第四大題得分
得分 (1) (2)
============================== 以下由考生填寫 ===============================
答卷部分
選擇一個正確答案代碼（A/B/C/D），填入每題的括號內（每題1.5分，多選無分，共30分）
題號 1 2 ３ 4 5 6 7 8 9 10
選擇
題號 11 12 13 14 15 16 17 18 19 20
選擇
二、問題解答 （12分）
1．答：有 種不同形態的二叉樹可以得到這一遍歷結果;　　　　　 　　　（1分）
可畫出的這些二叉樹為:　　　　　　　　　　　　　　　　　　　　　　　 （5分）
2．用遞推公式給出某人從底層開始走完全部樓梯的走法為（用F（N）記錄不同方案數）:
（6分）
賽區 市 學校 姓名
============================= 密 封 線 ============================
三、閱讀程序，并寫出程序的正確運行結果：（每題10分，共20分）
程序的運行結果是:
程序的運行結果是:
四、根據題意, 將程序補充完整（共38分）
PASCAL語言 BASIC語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
題一（3+3+4+4+4=18分）
① 　　　　　　　　　　　　　　　　 70
② 　　　　　　　　　　　　　　　　　　　　 110 　　　　　　　　　　　　　　　　　　 　　
③ 　　　　　　　　　　　　　　　　　　　　 140 　　　　　　　　　　　　　　　　　
④ 　　　　　　　　　　　　　　　　　　　　 180 　　　　　　　　　　　　　　　　　
⑤ 　　　　　　　　　　　　　　　　　　　　 220 　　　　　　　　　　　　　　　　　
題二（ 4+4+4+4+4=20分）
① 　　　　　　　　　　　　　　　　 90
② 　　　　　　　　　　　　　　　　　　　　 100 　　　　　　　　　　　　　　　　
③ 　　　　　　　　　　　　　　　　　　　　 120 　　　　　　　　　　　　　　　　　
④ 　　　　　　　　　　　　　　　　　　　　 210 　　　　　　　　　　　　　　　　　
⑤ 　　　　　　　　　　　　　　　　　　 240 　　　　　　　　　　　　　　　　　
第六屆全國青少年信息學（計算機）奧林匹克分區聯賽初賽試題
提高組參考答案
選擇一個正確答案代碼（A/B/C/D），填入每題的括號內 (每題1.5分，多選無分，共30分）
題號 1 2 ３ 4 5 6 7 8 9 10
選擇 C B D C D B Ｄ 　Ｂ 　Ａ C
題號 11 12 13 14 15 16 17 18 19 20
選擇 D B A C B A D D B Ｂ
二、問題解答（12分 ）
1．答：有 5 種不同形態的二叉樹可以得到這一遍歷結果; 可畫出的這些二叉樹為:
① a ② b ③ a ④ c ⑤ c
\ / \ \ / /
b a c c a b
\ / \ /
c b b a
2．用遞推公式給出的某人從底層開始走完全部樓梯的走法為（用F（N）記錄不同方案數）：
　F（1）＝1　 　F（2）＝2　 F（3）＝4　
　　　　F（N）＝F（N－3）＋F（N－2）＋F（N－1）　　（N≥4）
　　　　　
三、閱讀程序，并寫出程序的正確運行結果：（每題10分，共20分）
（１）程序的運行結果是: 4 3 0 2
（２）程序的運行結果是: BBAC
四、根據題意，將程序補充完整（共38分）
PASCAL語言 BASIC語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
題一（3+3+4+4+4=18分）
① A[j]:=1; 70 A ( j ) = 0
② A[i]:=0; 　　 　　 110　 A ( I ) = 0
③ S :=0; 　 　　　140 S = 0
④ B[s]:=1; 　 　　　180　 B ( s ) = 1
⑤ S = 32 　　　220　 S < 32
題二（ 4+4+4+4+4=20分）
① S p1<=sp2 90 sp1 > sp2
② Q [sp1,0]+1 　　 100 Q（SP1，0）+1；
③ Q [sp1,j]<>0 　 120　 q (sp1, j) = 0
④ （ q[sp2,0] ) ; 　 　　　210　 q (sp2, 0)
　　　　　　　　　　　　　　　　 　　　 　　　　　　　　　　　　　　　　　　
⑤ D[ q[i,0]]+1 ; 　　　240　 d (q (i, 0)) + 1
var
a:array[1..3,1..4] of integer;
b:array[1..4,1..3] of integer;
x,y:integer;
begin
for x:=1 to 3 do
for y:=1 to 4 do
a[x,y]:=x-y;
for x:=4 downto 1 do
for y:=1 to 3 do
b[x,y]:=a[y,x];
writeln(b[3,2]);
end.
DIM A(3,4), B(4,3)
FOR X=1 TO 3
FOR Y=1 TO 4
A(X,Y)=X-Y
NEXT Y , X
FOR X=4 TO 1 STEP -1
FOR Y=1 TO 3
B(X,Y)=A(Y,X)
NEXT Y, X
PRINT B(3,2)
END
　A
　0
　Ｂ　０　　　　　　１　Ｈ
Ｃ　０　　　　　　　　１Ｇ
　Ｄ　１　　　　　　１　Ｆ
　0
　　　　　　Ｅ第十四屆全國青少年信息學奧林匹克聯賽初賽試題
（ 提高組 Pascal語言 二小時完成 ）
●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、單項選擇題（共10題，每題1.5分，共計15分。每題有且僅有一個正確答案）。
1．在以下各項中，（ ）不是操作系統軟件。
A．Solaris B．Linux C．Sybase D．Windows Vista E．Symbian
2．微型計算機中，控制器的基本功能是（ ）。
A．控制機器的各個部件協調工作 B．實現算數運算與邏輯運算 C．存儲各種控制信息
D．獲取外部信息 E．存放程序和數據
3．設字符串S=“Olympic”，S的非空字串的數目是（ ）。
A．29 B．28 C．16 D．17 E．7
4．完全二叉樹有2*N-1的結點，則它的葉子結點數目是（ ）。
A．N-1 B．2*N C．N D．2N-1 E．N/2
5．將數組{8，23，4，16，77，-5，53，100}中元素從大到小按順序排序，每次可以交換任意兩個元素，最少要交換（ ）次。
A．4 B．5 C．6 D．7 E．8
6．設棧S的初始狀態為空，元素a，b，c，d，e，f依次入棧，出棧順序為b，d，c，f，e，a那么棧容量至少應該是（ ）。
A．6 B．5 C．4 D．3 E．2
7．與十進制數28.5625相等的四進制數是（ ）
A．123.21 B．131.22 C．130.22 D．130.21 E．130.20
8．遞歸過程和函數調用時，處理參數和返回地址，通常使用一種稱為（ ）的數據結構。
A．隊列 B．多維數組 C．線性表 D．鏈表 E．棧
9．TCP/IP 是一組構成互聯網基礎的網絡協議，字面上包括兩組協議：傳輸控制協議（TCP）和網際互聯協議（IP）。TCP/IP協議把Internet網絡系統描述成具有4個層次功能的網絡模型，其中提供源節點和目的節點之間的信息傳輸服務，包括尋址和路由器選擇等功能的是（）。
A．鏈路層 B．網絡層 C．傳輸層 D．應用層 E．會話層
10．對有序數組{5,13,19,21,37,56,64,75,88,92,100}進行二分查找，等概率情況下，查找成功的平均查找長度（平均比較次數）是（）。
A．35/11 B．34/11 C．33/11 D．32/11 E．34/10
二、不定項選擇題（共10題，每題1.5分，共計15分。每題正確答案的個數大于或等于1。多選或少選均不得分）。
11．下列關于圖靈的說法正確的有（ ）。
A．圖靈獎是美國計算機協會與1966年設立的，專門鼓勵那些對計算機做出重要貢獻的個人
B．圖靈獎有“計算機界諾貝爾獎”之稱。
C．迄今為止，還沒有華裔計算機科學家獲此殊榮。
D．圖靈獎的名稱取自計算機科學先驅、英國科學家阿蘭·圖靈。
12．計算機在工作過程中，若突然停電，（ ）中不會丟失信息不會丟失。
A．硬盤 B．CPU C．ROM D．RAM
13．若A=True，B=False，C=True，D=False，以下邏輯運算表達式真的有（ ）。
A．（A∧B）V（C∧DV A） B．（（ A∧B）VC）∧ B
C．（BVCVD）VD∧A D．A∧（DV C）∧B
14．Web2.0是近年來互聯網熱門概念之一，其核心是互動與分享。下列網站中，（ ）是典型的Web2.0的應用。
A．Sina B．Flickr C．Yahoo D．Google
15．(2008)10+ (5B)16 的結果是（）。
A．（833）16 B．（2099）10 C．（4063）8 D．（100001100011）2
16．二叉樹T，已知其先序遍歷是1 2 4 3 5 7 6（數字為節點編號，以下同），后序遍歷是4 2 7 5 6 3 1，則該二叉樹的中根遍歷是（ ）
A．4 2 1 7 5 3 6 B．2 4 1 7 5 3 6 C．4 2 1 7 5 6 4 D．2 4 1 5 7 3 6
17．面向對象的程序設計（Object-Oriented Programming）是一種程序設計的方法論，它將對象作為程序設計的基本單元，將數據和程序封裝在對象中，以提高軟件的重用性、靈活性、和擴展性。下面關于面向對象的程序設計說法中正確的是（ ）。
A．面向對象的程序設計方法通常采用自頂向下的設計方法進行設計。
B．面向對象的程序設計方法具有繼承性（inheritance）、封裝性（encapsulation）、多態性（polymorphism）等幾大特點。
C．支持面向對象特性稱為面向對象的編程語言，目前較為流行的有C++，JAVA，C#等。
D．面向對象的程序設計的雛形來自于Simula語言，后來在SmallTalk語言的完善和標準化的過程中得到更多的擴展和對以前的思想的重新注解。至今，SmallTalk語言仍然被視為面向對象的基礎。
18．設T是一棵有n個定點的樹，以下說法正確的是（ ）。
A．T是聯通的，無環的 B．T是聯通的，有n-1條邊
C．T是無環的，有n-1條邊 D．以上都不對
19．NOIP競賽推薦使用的語言環境有（ ）。
A．Dev-C++ B．Visual C++ C．Free Pascal D．Lazarus
20．在下列防火墻（Firewall）的說法中，正確的有（ ）。
A．防火墻是一項協助確保信息安全的設備，其會依照特定的規則，允許或是限制數據通過
B．防火墻可能是一臺專屬硬件或是安裝在一般硬件上的一套軟件
C．網絡層防火墻可以視為一種IP數據包過濾器，只允許符合特定規定的數據包通過，其余的一概禁止穿越防火墻
D．應用層防火墻是在TCP/IP的“應用層”上工作，可以攔截進出某應用程序的所有數據包
三、問題求解（共2題，每題5分，共計10分）
1．有6個城市，任何兩個城市之間有一條道路連接，6個城市之間兩兩之間的距離如下表表示，則城市1到城市6的最短距離為____________。
城市1 城市2 城市3 城市4 城市5 城市6
城市1 0 2 3 1 12 15
城市2 2 0 2 5 3 12
城市3 3 2 0 3 6 5
城市4 1 5 3 0 7 9
城市5 12 3 6 7 0 2
城市6 15 12 5 9 2 0
2．書架上有21本書，編號從1 到 21 從中選4 本，其中每兩本的編號都不相鄰的選法一共有___________________種。
四、閱讀程序寫結果（共4題，每題8分，共計32分）。
1．var
i,a,b,c,d:integer;
f:array[0..3] of integer;
begin
for i:=0 to 3 do
read(f[i]);
a:=f[0]+f[1]+f[2]+f[3];
a:=a div f[0];
b:=f[0]+f[2]+f[3];
c:=(b*f[1]+a) div f[2];
d:=f[(b div c) mod 4];
if (f[(a+b+c+d) mod 4]>f[2]) then
begin
a:=a+b;
writeln(a)
end
else
begin
c:=c+d;
writeln(c);
end;
end.
輸入： 9 19 29 39
輸出：_______________________________
2．procedure foo(a,b,c:integer);
begin
if a>b then foo(c,a,b)
else
writeln(a,',',b,',',c)
end;
var a,b,c:integer;
begin
readln(a,b,c);
foo(a,b,c);
end.
輸入：2 1 3
輸出：_________________
3．procedure f(a,b,c:integer);
begin
write(a,b,c,'/');
if (a=3)and(b=2)and(c=1) then exit;
if (belse
if aif aend;
var a,b,c:integer;
begin
readln(a,b,c);
f(a,b,c);
end.
輸入：1 3 2
輸出：____________________
4．var
s:string;
i,j,len,k:integer;
begin
readln(s);
len:=length(s);
for i:=1 to len do
if (ord(s[i])>=ord('A')) and (ord(s[i])<=ord('Z')) then
s:=chr(ord(s[i])-ord('A')+ord('a'));
for i:=1 to len do
if (ord(s[i])else
s:=chr(ord(s[i])-23);
write(s);
write('/');
for j:=1 to 3 do
begin
i:=1;
while i<=len-j do
begin
s[i]:=s[i+j];
i:=i+j;
end;
end;
writeln(s);
end.
輸入：ABCDEFGuvwxyz
輸出：________________________________
五．完善程序（前6空，每空3分，后5空，每空2分，共28分）。
1．（找第k大的數）給定一個長度為1000000的無序正整數序列，以及另一個數n(1<=n<=1000000)，接下來以類似快速排序的方法找到序列中第n大的數（關于第n大的數：例如序列{1，2，3，4，5，6}中第3大的數是4）
Var a:array[1..1000000] of integer;
n,m,ans:integer;
procedure swap(var a,b:integer);
var t:integer;
begin
if (a<>b) then begin
t:=a; a:=b; b:=t;
end;
end;
Function FindKth(left,right,n:integer):integer;
Var tmp,value,i,j:integer;
begin
if left=right then exit(left);
tmp:=random(right-left)+left;
swap(a[tmp],a[left]);
value:=____①_____
i:=left; j:=right;
while ibegin
while (iif ia:=a[j];inc(i);
end else break;
while (iif ia[j]:=a[i]; dec(j);
end else break;
end;
____④_____
if iif i>n then begin dec(j); exit(______⑥________);end;
exit(i);
end;
var i:integer;
begin
randomize;
ans:=-1;
m:=5;
for i:=1 to m do
read(a[i]);
read(n);
ans:=FindKth(1,m,n);
writeln(a[ans]);
end.
2．（矩陣中的數字）有一個n*n（1≤n≤5000)的矩陣a，對于1≤ivar
n,k,answerx,answery:integer;
a:array[1..5000,1..5000] of integer;
Procedure FindKPosition;
Var I,j:integer;
Begin
i:=n; j:=n;
while j>0 do begin
if a[n,j]dec(j);
end;
______①_________
while a[i,j]<>k do
begin
while (___②_____) and (i>1) do dec(i);
while (___③_____) and (j<=n) do inc(j);
end;
_______④________
_______⑤________
end;
var i,j:integer;
begin
read(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
read(k);
FindKPosition;
writeln(answerx,' ',answery);
end. NOIP2008年提高組（Pascal語言）參考答案與評分標準
一、單項選擇題：（每題1.5分）
1. C 2. A 3. B 4. C 5. B
6. D 7. D 8. E 9. B 10. C
二、 不定項選擇題 （共10題，每題1.5分，共計15分。每題正確答案的個數大于或等于1。多選或少選均不得分）。
11. ABD 12. AC 13. BC 14. B 15. ABC
16. ABD 17. BCD 18. ABC 19. ACD 20. ABCD
三、問題求解：（共2題，每題5分，共計10分）
1．7
2．3060
四、閱讀程序寫結果（共4題，每題8分，共計32分）
1. 23 （信心題）
2. 1,3,2 (簡單遞歸)
3. 132/213/231/312/321/ （全排列）
4. defghijxyzabc/hfizxjaybcccc （字符串替換）
五．完善程序 (前6空，每空3分，后5空，每空2分，共28分)
（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學委員會審查）
1. ① a[left]
② a[j] < value (或a[j] <= value)
③ a[i] > value （或a[i] >= value）
④ a[i] := value;
⑤ i,right,n
⑥ FindKth(left, i, n)
2. ① inc(j); (或者j := j+1;)
② a[i,j] > k
③ a[i,j] < k
④ answerx := i;
⑤ answery := j;

展開更多......

收起↑