第十届全国青少年信息学奥林匹克联赛初赛试题
（ 提高组 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) cai@jcc.pc.tool.rf.edu.jp ( 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;