第十九届全国青少年信息学奥林匹克联赛初赛
提高组 Pascal 语言试题
竞赛时间：2013 年 10 月 13 日 14:30~16:30
选手注意：
? 试题纸共有 12 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上
的一律无效。 ? 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确 选项）
1. 一个 32 位整型变量占用（
）个字节。
C. 32
）。
C. 6.25
D. 11.125 D. 128
A. 4 B. 8
2. 二进制数 11.01 在十进制下是（
A. 3.25
3. 下面的故事与（
B. 4.125
）算法有着异曲同工之妙。
从前有座山，
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：?个 老和尚给小和尚讲故事....’?A. 枚举
山 里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有
C. 贪心
D. 分治
B. 递归
4. 1948 年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。 A. 冯·诺伊曼（John von Neumann） B. 图灵（Alan Turing） C. 欧拉（Leonhard Euler） D. 克劳德·香农（Claude Shannon） 5. 已知一棵二叉树有 2013 个节点，则其中至多有（
）个节点有 2 个子节点。
D. 1024
A. 1006 B. 1007 C. 1023
6. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通
图。右图是一个有 5 个顶点、8 条边的连通图。若要使它不再是连通 图，至少要删去其中的（ ）条边。
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 1 页，共 12 页
A. 2
B. 3 C. 4 D. 5
7. 斐波那契数列的定义如下：F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 (n ≥ 3)。如果用下面的函数计
算斐波那契数列的第 n 项，则其时间复杂度为（ ）。
funtion F(n : longint) : longint; begin
if n <= 2 then
F := 1 else
F := F(n - 1) + F(n - 2);
end; A. O(1)
B. O(n)
C. O(n2)
D. O(Fn)
8. 二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子 树上所有节点的值。那么，二叉查找树的（ ）是一个有序序列。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 宽度优先遍历
9. 将（2, 6, 10, 17）分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数 h(x) =
（ ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。 A. x mod 11 C. 2x mod 11
B. xmod 11
D. ?√ ? mod 11，其中?√ ?表示√ 下取整
10. IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被 使用（ ）位地址的 IPv6 协议所取代。
2
A. 40 B. 48 C. 64 D. 128
11. 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。
那么，12 个顶点的二分图至多有（ ）条边。
A. 18 B. 24 C. 36 D. 66
12. （ ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进
制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。
A. ASCII B. Unicode C. GBK 2312 D. BIG5 ）。
13. 把 64 位非零浮点数强制转换成 32 位浮点数后，不可能（ A. 大于原数 B. 小于原数 C. 等于原数
D. 与原数符号相反
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 2 页，共 12 页
14. 对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不
使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。 A. O(mn + n3)
B. O(n2)
D. O((m + n) log n)
2
C. O((m + n) log n)
15. T(n)表示某个算法输入规模为 n 时的运算次数。如果 T(1)为常数，且有递归式 T(n) =
2*T(n / 2) + 2n，那么 T(n) = （ ）。 A. Θ(n)
B. Θ(n log n)
C. Θ(n2) D. Θ(n2 log n)
二、不定项选择题（共 5 题，每题 1.5 分，共计 7.5 分；每题有一个或多个正确 选项，多选或少选均不得分）
1. 下列程序中，正确计算 1, 2, …, 100 这 100 个自然数之和 sum（初始值为 0）的是（
）。A. for i := 1 to 100 do sum := sum + i; B. i := 1; while i > 100 do begin sum := sum + i; inc(i); end; repeat C. i := 1; D. i := 1; repeat sum := sum + i; sum := sum + i; inc(i); inc(i); until i > 100; until i <= 100;
2. （ ）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。 A. 快速排序 B. 插入排序 C. 冒泡排序 D. 归并排序
3. 以 A0 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标
无关），最后一个遍历到的顶点可能是（ ）。
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 3 页，共 12 页
A. A1
B. A2 C. A3 D. A4
4. （ ）属于 NP 类问题。 A. 存在一个 P 类问题 B. 任何一个 P 类问题 C. 任何一个不属于 P 类的问题
D. 任何一个在（输入规模的）指数时间内能够解决的问题
5. CCF NOIP 复赛考试结束后，因（ ）提出的申诉将不会被受理。 A. 源程序文件名大小写错误
B. 源程序保存在指定文件夹以外的位置 C. 输出文件的文件名错误
D. 只提交了可执行文件，未提交源程序
三、问题求解（共 2 题，每题 5 分，共计 10 分；每题全部答对得 5 分，没有部 分分）
1. 某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1, s2, …, sn，均为 0
或 1。该系统每次随机生成 n 个数 a1, a2, …, an，均为 0 或 1，请用户回答(s1a1 + s2a2 + … + snan)除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使 问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。
然而，事与愿违。例如，当 n = 4 时，有人窃听了以下 5 次问答： 系统生成的 n 个数 问答编号 掌握密码的用户的回答 a1 a2 a3 a4 1 2 3 4 1 0 0 1 1 0 1 1 0 ，s2 = 0 1 1 1 0 0 1 0 0 0 ，s3 = 1 0 0 0 0 ，s4 = 。
1 5 就破解出了密码 s1 =
2. 现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概
率地随机跳到 1, 2, …, k 号荷叶之一上，直至跳到 1 号荷叶为止。当 n = 2 时，平均一共 跳 2 次；当 n = 3 时，平均一共跳 2.5 次。则当 n = 5 时，平均一共跳 次。
1
2
3
4
5
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 4 页，共 12 页
四、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）
1. var
n, i : integer; str : string; isPlalindrome : boolean;
begin
readln(str); n := Length(str);
isPlalindrome := true;
for i := 1 to (n div 2) do begin
if (str[i] <> str[n-i+1]) then
isPlalindrome := false;
end;
if (isPlalindrome) then
writeln('Yes') else
writeln('No');
end.
输入：abceecba
输出：
2. var
a, b, u, v, i, num : integer;
begin
readln(a, b, u, v);
num := 0;
for i := a to b do begin
if (i mod u = 0) or (i mod v = 0) then
inc(num);
CCF NOIP2013 初赛提高组 Pascal 语言试题
第 5 页，共 12 页
NOIP2013初赛提高组Pascal试题及答案
