程序说明：
数组 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.
6
赛区 市 学校 姓名
========================== 密
封 线 =======================
第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
提高组答卷纸
阅 卷 记 录 总阅卷人 总 得 分 第 一 大 题 得 分 第二大题得分 2 3 4 5 6 7 8 9 10 第三大题得分 题号 1 (1) (2) 得分 12 13 14 15 16 17 18 19 20 第四大题得分 题号 11 (1) (2) 得分
============================== 以下由考生填写 ===============================
答卷部分
一、 选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分） 题号 选择 题号 选择
二、问题解答 （12分）
1．答：有 种不同形态的二叉树可以得到这一遍历结果; （1分） 可画出的这些二叉树为: （5分）
2．用递推公式给出某人从底层开始走完全部楼梯的走法为（用F（N）记录不同方案数）: （6分）
7
1 11
2 12
３ 13
4 14
5 15
6 16
7 17
8 18
9 19
10 20
赛区 市 学校 姓名
============================= 密 封 线 ============================
三、阅读程序，并写出程序的正确运行结果：（每题10分，共20分）
（1） 程序的运行结果是:
（2） 程序的运行结果是:
四、根据题意, 将程序补充完整（共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
第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
8
提高组参考答案
一、选择一个正确答案代码（A/B/C/D），填入每题的括号内 (每题1.5分，多选无分，共30分） 题号 1 2 ３ 4 5 6 7 8 9 10 选择 C B D C D B Ｄ Ｂ Ａ C 题号 11 选择 D
12 B
13 A
14 C
15 B
16 A
17 D
18 D
19 B
20 Ｂ
二、问题解答（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
9
