当前位置:首页 >> 学科竞赛 >>

NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组Pascal试题


第十九届全国青少年信息学奥林匹克联赛初赛
普及组 Pascal 语言试题 竞赛时间:2013 年 10 月 13 日 14:30~16:30
选手注意:
? ? 试题纸共有 9 页,答题纸共有 2 页,满分 100 分。请在答题纸上作答,写在试题纸上的 一律无效。 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。

r />一、单项选择题(共 20 题,每题 1.5 分,共计 30 分;每题有且仅有一个正确选 项)
1. 一个 32 位整型变量占用( A. 2. 4 B. 8 )。 C. 6.25 D. 11.125 )个字节。 C. 32 D. 128

二进制数 11.01 在十进制下是( A. 3.25 B. 4.125

3.

下面的故事与(

)算法有着异曲同工之妙。

从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:?从前有座山,山 里有座庙,庙里有个老和尚在给小和尚讲故事:‘从前有座山,山里有座庙,庙里有个 老和尚给小和尚讲故事....’? A. 4. 枚举 B. 递归 C. 贪心 D. 分治

逻辑表达式( A. C. (A ? B) ? ? A

)的值与变量 A 的真假无关。 B. D. (A ? B) ? ? B (A ? B) ? ? ? B A

(A ? B) ? (? ? B) A

5.

将(2, 6, 10, 17)分别存储到某个地址区间为 0~10 的哈希表中,如果哈希函数 h(x) = ( A. C. ),将不会产生冲突,其中 a mod b 表示 a 除以 b 的余数。 x mod 11 2x mod 11 B. D. x2 mod 11 ?√ ? mod 11, 其中?√ ?表示√ 下取整 )。 D. 16

6.

在十六进制表示法中,字母 A 相当于十进制中的( A. 9 B. 10 C. 15

CCF NOIP2013 初赛普及组 Pascal 语言试题 第 1 页,共 9 页

7.

下图中所使用的数据结构是( 压入 A A A. 哈希表 B. 栈

)。 弹出 B A C. 队列 D. 二叉树 压入 C

压入 B

B A

C A

8.

在 Windows 资源管理器中,用鼠标右键单击一个文件时,会出现一个名为“复制”的 操作选项,它的意思是( A. B. C. D. ) 。 用剪切板中的文件替换该文件 在该文件所在文件夹中,将该文件克隆一份 将该文件复制到剪切板,并保留原文件 将该文件复制到剪切板,并删除原文件 )个节点有 2 个子节点。 D. 7

9.

已知一棵二叉树有 10 个节点,则其中至多有( A. 4 B. 5 C. 6

10. 在一个无向图中,如果任意两点之间都存在路径相连,则称其为连通图。下图是一个有 4 个顶点、6 条边的连通图。若要使它不再是连通图,至少要删去其中的( )条边。

A.

1

B.

2

C.

3

D.

4

11. 二叉树的( A. 先序遍历

)第一个访问的节点是根节点。 B. 中序遍历 C. 后序遍历 D. 以上都是 )。

12. 以 A0 作为起点,对下面的无向图进行深度优先遍历时,遍历顺序不可能是(

A.

A0, A1, A2, A3

B.

A0, A1, A3, A2

C.

A0, A2, A1, A3

D.

A0, A3, A1, A2

CCF NOIP2013 初赛普及组 Pascal 语言试题 第 2 页,共 9 页

13. IPv4 协议使用 32 位地址,随着其不断被分配,地址资源日趋枯竭。因此,它正逐渐被 使用( A. 14. ( A. 40 )位地址的 IPv6 协议所取代。 B. 48 C. 64 D. 128

)的平均时间复杂度为 O(n log n),其中 n 是待排序的元素个数。 快速排序 B. 插入排序 C. 冒泡排序 D. 基数排序 )。

15. 下面是根据欧几里得算法编写的函数,它所计算的是 a 和 b 的( function euclid(a, b : longint) : longint; begin if b = 0 then euclid := a else euclid := euclid(b, a mod b); end; A. C. 最大公共质因子 最大公约数 B. D. 最小公共质因子 最小公倍数 )。

16. 通常在搜索引擎中,对某个关键词加上双引号表示( A. B. C. D. 排除关键词,不显示任何包含该关键词的结果 将关键词分解,在搜索结果中必须包含其中的一部分 精确搜索,只显示包含整个关键词的结果 站内搜索,只显示关键词所指向网站的内容 )。 C. .chn

17. 中国的国家顶级域名是( A. .cn B. .ch

D. )。

.china

18. 把 64 位非零浮点数强制转换成 32 位浮点数后,不可能( A. C. 大于原数 等于原数 B. D. 小于原数

与原数符号相反 ) 。

19. 下列程序中, 正确计算 1, 2, …, 100 这 100 个自然数之和 sum (初始值为 0) ( 的是 A. i := 1; repeat sum := sum + i; inc(i); until i > 100; B. i := 1; repeat sum := sum + i; inc(i); until i <= 100;

CCF NOIP2013 初赛普及组 Pascal 语言试题 第 3 页,共 9 页

C.

i := 1; while i < 100 do begin sum := sum + i; inc(i); end;

D.

i := 1; while i >= 100 do begin sum := sum + i; inc(i); end; )。 D. NOI DOS

20. CCF NOIP 复赛全国统一评测时使用的系统软件是( A. NOI Windows B. NOI Linux C.

NOI Mac OS

二、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部答对得 5 分,没有部 分分)
1. 2. 7 个同学围坐一圈,要选 2 个不相邻的作为代表,有_________种不同的选法。 某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1, s2, …, sn,均为 0 或 1。 该系统每次随机生成 n 个数 a1, a2, …, an, 均为 0 或 1, 请用户回答(s1a1 + s2a2 + … + snan)除以 2 的余数。如果多次的回答总是正确,即认为掌握密码。该系统认为,即使 问答的过程被泄露,也无助于破解密码——因为用户并没有直接发送密码。 然而,事与愿违。例如,当 n = 4 时,有人窃听了以下 5 次问答: 问答编号 a1 1 2 3 4 5 1 0 0 1 1 系统生成的 n 个数 a2 1 0 1 1 0 a3 0 1 1 1 0 a4 0 1 0 0 0 1 0 0 0 0 掌握密码的用户的回答

就破解出了密码 s1 = _________,2 = _________,3 = _________,4 = _________。 s s s

三、阅读程序写结果(共 4 题,每题 8 分,共计 32 分)
1. var a,b: integer; begin readln(a, b);
CCF NOIP2013 初赛普及组 Pascal 语言试题 第 4 页,共 9 页

writeln(a, '+', b, '=', a+b); end. 输入:3 5 输出:_________ 2. var a, b, u, i, num : integer; begin readln(a, b, u); num := 0; for i:= a to b do begin if (i mod u = 0) then inc(num); end; writeln(num); end. 输入:1 100 15 输出:_________ 3. const SIZE = 100; var n, f, i, left, right, middle : integer; a:array[1..SIZE] of integer; begin readln(n, f); for i := 1 to n do read(a[i]); left := 1; right := n; repeat middle := (left+right) div 2;

CCF NOIP2013 初赛普及组 Pascal 语言试题 第 5 页,共 9 页

if (f <= a[middle]) then right := middle else left := middle+1; until (left >= right); writeln(left); end. 输入: 12 17 2 4 6 9 11 15 17 18 19 20 21 25 输出:_________ 4. const SIZE = 100; var n, ans, i, j : integer; height, num : array[1..SIZE] of integer; begin read(n); for i := 1 to n do begin read(height[i]); num[i] := 1; for j := 1 to i-1 do begin if ((height[j] < height[i]) and (num[j] >= num[i])) then num[i] := num[j]+1; end; end; ans := 0; for i := 1 to n do begin if (num[i] > ans) then ans := num[i]; end;

CCF NOIP2013 初赛普及组 Pascal 语言试题 第 6 页,共 9 页

writeln(ans); end. 输入: 6 2 5 3 11 12 4 输出:_________

四、完善程序(共 2 题,每题 14 分,共计 28 分)
1. (序列重排)全局数组变量 a 定义如下: const int SIZE = 100; int a[SIZE], n; 它记录着一个长度为 n 的序列 a[1], a[2], …, a[n]。 现在需要一个函数,以整数 p (1 ≤ p ≤ n)为参数,实现如下功能:将序列 a 的前 p 个数与后 n – p 个数对调,且不改变这 p 个数(或 n – p 个数)之间的相对位置。例如, 长度为 5 的序列 1, 2, 3, 4, 5,当 p = 2 时重排结果为 3, 4, 5, 1, 2。 有一种朴素的算法可以实现这一需求, 其时间复杂度为 O(n)、 空间复杂度为 O(n): procedure swap1(p : longint); var i : longint; b : array[1..SIZE] of longint; begin for i := 1 to p do b[ (1) ] := a[i]; (2) (3) ; do //(3 分) //(3 分) //(2 分) for i := p + 1 to n do b[i - p] := for i := 1 to a[i] := b[i]; end; 我们也可以用时间换空间,使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法: procedure swap2(p : longint); var i, j, temp : longint;
CCF NOIP2013 初赛普及组 Pascal 语言试题 第 7 页,共 9 页

begin for i := p + 1 to n do begin temp := a[i]; for j := i downto a[j] := a[j - 1]; (5) end; end; 2. (二叉查找树) 二叉查找树具有如下性质: 每个节点的值都大于其左子树上所有节点的 值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。 输入的第一行包含一个整数 n,表示这棵树有 n 个顶点,编号分别为 1, 2, …, n,其 中编号为 1 的为根结点。之后的第 i 行有三个数 value, left_child, right_child,分别表示 该节点关键字的值、左子节点的编号、右子节点的编号;如果不存在左子节点或右子节 点,则用 0 代替。输出 1 表示这棵树是二叉查找树,输出 0 则表示不是。 program Bst; const SIZE = 100; const INFINITE = 1000000; type node = record left_child, right_child, value : longint; end; var a : array[1..SIZE] of node; i, n : longint; function is_bst(root, lower_bound, upper_bound : longint) : longint; var cur : longint; begin if root = 0 then begin is_bst := 1; := temp; //(3 分) (4) do //(3 分)

CCF NOIP2013 初赛普及组 Pascal 语言试题 第 8 页,共 9 页

exit; end; cur := a[root].value; if (cur > lower_bound) and ( (is_bst( is_bst := 1 else is_bst := 0; end; begin readln(n); for i := 1 to n do read(a[i].value, a[i].left_child, a[i].right_child); writeln(is_bst( end. (5) , -INFINITE, INFINITE)); //(2 分) (2) , (1) (3) ) and , (4) //(3 分) ) = 1) then (is_bst(a[root].left_child, lower_bound, cur) = 1) and //(3 分,3 分,3 分)

CCF NOIP2013 初赛普及组 Pascal 语言试题 第 9 页,共 9 页


相关文章:
NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组Pascal试题【整理版附答案】
NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组Pascal试题【整理版附答案】_学科竞赛_高中教育_教育专区。NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及...
2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题
2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_高中教育_教育专区。...输入:3 5 输出:___ CCF NOIP2013 第十九届 初赛普及组 Pascal 语言试题 ...
2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题
2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_学科竞赛_初中教育_教育...CCF NOIP2013 第十九届 初赛普及组 Pascal 语言试题 输入:3 5 输出:___ 2...
第十九届(2013年)全国青少年信息学奥林匹克联赛初赛_答案
第十九届(2013年)全国青少年信息学奥林匹克联赛初赛_答案_学科竞赛_初中教育_教育专区。第十九届(2013 年)全国青少年信息学奥林匹克联赛初赛 答案 普及组 Pascal 语...
NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析
NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析_学科竞赛_高中教育_教育专区。NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析NOIP...
NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案
NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考...NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛 ...[j] Pascal语言 分值 2 2 2 3 3 3 3 3 2 ...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_...NOIP2002普及组初赛试题 6页 免费 NOIP2012普及组初赛及答... 9页 1下载券©...
2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题
第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题竞赛时间:2013 ...; end. CCF NOIP2013 初赛提高组 Pascal 语言试题 第 11 页,共 11 页 ...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:...
更多相关标签:
noip普及组初赛pascal | noip2016普及组初赛 | noip2015普及组初赛 | noip2014普及组初赛 | noip2012普及组初赛 | noip2013普及组初赛 | noip普及组初赛分数线 | noip2007普及组初赛 |