NOIP2015提高组Pascal试题

第二十一届全国青少年信息学奥林匹克联赛初赛

提高组Pascal语言试题

竞赛时间：2015年10月11日14:30~16:30

选手注意：

试题纸共有9页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）

1. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以（ ）形式进行的。

A. 二进制码

2. 下列说法正确的是（ ）。

A. CPU的主要任务是执行数据运算和程序控制

B. 存储器具有记忆能力，其中信息任何时候都不会丢失

C. 两个显示器屏幕尺寸相同，则它们的分辨率必定相同

D. 个人用户只能使用Wifi的方式连接到Internet

3. 与二进制小数0.1相等的十六进制数是（ ）。

A. 0.8

4. 下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（ ）。

A. 120 82 50

5. 线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。

A. 必须连续

C. 一定不连续

6. 今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为（ ）。

A. f B. c C. a D. b B. 部分地址必须连续 D. 连续不连续均可 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F2 B. 0.4 C. 0.2 D. 0.1 B. 八进制码 C. 十进制码 D. 智能拼音码

7. 前序遍历序列与后序遍历序列相同的二叉树为（ ）。

A. 非叶子结点只有左子树的二叉树

C. 根结点无右子树的二叉树

8. 如果根的高度为1，具有61个结点的完全二叉树的高度为（ ）。

A. 5

9. 6个顶点的连通图的最小生成树，其边数为（ ）。

A. 6

10. 设某算法的计算时间表示为递推关系式T(n) = T(n - 1) + n（n为正整数）及T(0) = 1，则

该算法的时间复杂度为（ ）。

A. O(log n)

11. 具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运

算的时间复杂度均为（ ）。

A. Θ(n2)

12. 在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ ）思想的算法。

A. 贪心

13. 双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的

一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ）。

A. p^.llink := q; q^.rlink := p;

p^.llink^.rlink := q; q^.llink := p^.llink;

B. q^.llink := p^.llink; p^.llink^.rlink := q;

q^.rlink := p; p^.llink := q^.rlink;

C. q^.rlink := p; p^.rlink := q;

p^.llink^.rlink := q; q^.rlink := p;

D. p^.llink^.rlink := q; q^.rlink := p;

q^.llink := p^.llink; p^.llink := q;

14. 对图G中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图G的一个正常

着色。正常着色图G所必需的最少颜色数，称为G的色数。那么下图的色数是（ ）。 B. 分治 C. 递推 D. 回溯 B. Θ(e2) C. Θ(ne) D. Θ(n + e) B. O(n log n) C. O(n) D. O(n2) B. 5 C. 7 D. 4 B. 6 C. 7 D. 8 B. 只有根结点的二叉树 D. 非叶子结点只有右子树的二叉树

A. 3

B. 4 C. 5 D. 6

15. 在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选

手自带的是（ ）。

A. 鼠标

B. 笔 C. 身份证 D. 准考证

二、不定项选择题（共5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多选或少选均不得分）

1. 以下属于操作系统的有（ ）。

A. Windows XP

2. 下列属于视频文件格式的有（ ）。

A. AVI

3. 下列选项不是正确的IP地址的有（ ）。

A. 202.300.12.4

4. 下列有关树的叙述中，叙述正确的有（ ）。

A. 在含有n个结点的树中，边数只能是(n-1)条

B. 在哈夫曼树中，叶结点的个数比非叶结点个数多1

C. 完全二叉树一定是满二叉树

D. 在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先

5. 以下图中一定可以进行黑白染色的有（ ）。（黑白染色：为各个结点分别指定黑白

两种颜色之一，使相邻结点颜色不同。）

A. 二分图

B. 完全图 C. 树 D. 连通图

B. 192.168.0.3 C. 100:128:35:91 D. 111-103-35-21 B. MPEG C. WMV D. JPEG B. UNIX C. Linux D. Mac OS

三、问题求解（共2题，每题5分，共计10分；每题全部答对得5分，没有部分分）

1. 在1和2015之间（包括1和2015在内）不能被4、5、6三个数任意一个数整除的数

有_________个。

2. 结点数为5的不同形态的二叉树一共有_________种。（结点数为2的二叉树一共有2

种：一种是根结点和左儿子，另一种是根结点和右儿子。）

四、阅读程序写结果（共4题，每题8分，共计32分）

1. type

point = record

x: longint;

y: longint;

end;

EX = record

a: longint;

b: longint;

c: point;

end;

var

e: EX;

begin

e.a := 1;

e.b := 2;

e.c.x := e.a + e.b;

e.c.y := e.a * e.b;

writeln(e.c.x, ',', e.c.y);

end.

输出：_________

2. type

p_char = ^char;

var

c1, c2: char;

p1, p2: p_char;

procedure fun(a, b: p_char);

begin

a := b;

inc(a^);

end;

begin

c1 := 'A';

c2 := 'a';

p1 := @c1;

p2 := @c2;

fun(p1,p2);

writeln(c1, c2);

end.

输出：_________

3. var

len, maxlen: longint;

s, ss: string;

begin

maxlen := 0;

while true do

begin

readln(ss);

len := length(ss);

if ss[1] = '#' then

break;

if len > maxlen then

begin

s := ss;

maxlen := len;

end;

end;

writeln(s);

end.

输入：

I

am

a

citizen

of

China

#

输出：_________

4. var

n: longint;

function fun(n, fromPos, toPos: longint): longint;

var

t, tot: longint;

begin

if n = 0 then

exit(0);

for t := 1 to 3 do

if (t <> fromPos) and (t <> toPos) then

break;

tot := 0;

inc(tot, fun(n - 1, fromPos, t));

inc(tot);