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

第十七届全国青少年信息学奥林匹克联赛初赛试题


第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 Pascal 语言 两小时完成 )

●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一、单项选择题(共 20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确选项。 ) 1、在二进制下,1101001 + ( A、1011 B、1101 ) = 1110110。 C、1010 D、1111

2、字符“0”的 ASCII 码为 48,则字符“9”的 ASCII 码为( A、39 B、57 C、120

) 。

D、视具体的计算机而定 )张大小为 2MB 的数码照片。 C、4000 D、16000

3、一片容量为 8GB 的 SD 卡能存储大约( A、1600 B、2000

4、摩尔定律(Moore's law)是由英特尔创始人之一戈登·摩尔(Gordon Moore) 提出来的。根据摩尔定律,在过去几十年以及在可预测的未来几年,单块集成电路的集成 度大约每( A、1 )个月翻一番。 B、6 C、18 D、36

5、无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个 顶点,则它共有( A、7 6、寄存器是( A、硬盘 )条边。 B、21 )的重要组成部分。 B、高速缓存 C、内存 D、 中央处理器 (CPU) C、42 D、49

7、 如果根结点的深度记为 1, 则一棵恰有 2011 个叶结点的二叉树的深度最少是 ( A、10 B、11 C、12 D、13

) 。

8、体育课的铃声响了,同学们都陆续地奔向操场,按老师的要求从高到矮站成一排。每 个同学按顺序来到操场时,都从排尾走向排头,找到第一个比自己高的同学,并站在他的
第 1 页 共 12 页

后面。这种站队的方法类似于( A、快速排序 A、7

)算法。 C、冒泡排序 C、25 D、归并排序 )位。 D、不能确定

B、插入排序 B、13

9、一个正整数在二进制下有 100 位,则它在十六进制下有(

10、有人认为,在个人电脑送修前,将文件放入回收站中就是已经将其删除了。这种想法 是( ) 。 A、正确的,将文件放入回收站意味着彻底删除、无法恢复 B、不正确的,只有将回收站清空后,才意味着彻底删除、无法恢复 C、不正确的,即使将回收站清空,文件只是被标记为删除,仍可能通过恢复软件找回 D、不正确的,只要在硬盘上出现过的文件,永远不可能被彻底删除 11、广度优先搜索时,需要用到的数据结构是( A、链表 B、队列 C、栈 ) 。 D、散列表 ) 。

12、在使用高级语言编写程序时,一般提到的“空间复杂度”中的“空间”是指( A、程序运行时理论上所占的内存空间 B、程序运行时理论上所占的数组空间 C、程序运行时理论上所占的硬盘空间 D、程序源文件理论上所占的硬盘空间

13、在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素,最坏情况下运行 的时间复杂度是( A、O(1) ) 。 B、O(log n) C、O(n) D、O(n log n)

14、生物特征识别,是利用人体本身的生物特征进行身份认证的一种技术。目前,指纹识 别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于 生物特征识别技术及其应用的是( ) 。

A、指静脉验证

B、步态验证

C、ATM 机密码验证
第 2 页 共 12 页

D、声音验证

15、现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只 由 4 个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为 700、600、 300、 200。那么,“也”字的编码长度是( A、1 B、2 16、关于汇编语言,下列说法错误的是( A、是一种与具体硬件相关的程序设计语言 B、在编写复杂程序时,相对于高级语言而言代码量较大,且不易调试 C、可以直接访问寄存器、内存单元、以及 I/O 端口 D、随着高级语言的诞生,如今已完全被淘汰,不再使用 ) 。 ) 。 D、4 C、3

17、 (

)是一种选优搜索法,按选优条件向前搜索,以达到目标。当探索到某一步时,

发现原先选择并不优或达不到目标,就退回一步重新选择。 A、回溯法 18、1956 年( B、枚举法 C、动态规划 D、贪心法

)授予肖克利(William Shockley) 、巴丁(John Bardeen)和

布拉顿(Walter Brattain) ,以表彰他们对半导体的研究和晶体管效应的发现。 A、诺贝尔物理学奖 B、约翰·冯·诺依曼奖 C、图灵奖 D、高德纳奖(Donald E. Knuth Prize) 19、对一个有向图而言,如果每个节点都存在到达其他任何节点的路径, 那么就称它是强连通的。例如,右图就是一个强连通图。事实上,在删掉边( 它依然是强连通的。 A、a B、b C、c D、d )后,

20、 从 ENIAC 到当前最先进的计算机, 冯· 诺依曼体系结构始终占有重要的地位。 冯· 诺 依曼体系结构的核心内容是( A、采用开关电路 C、采用存储程序和程序控制原理 ) 。 B、采用半导体器件 D、采用键盘输入

二、问题求解(共 2 题,每题 5 分,共计 10 分)
第 3 页 共 12 页

1、每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时,它才 是有效的。例如,00000000、01010011 都是有效的序列号,而 11111110 不是。那 么,有效的序列号共有________个。 2、定义字符串的基本操作为:删除一个字符、插入一个字符和将一个字符修改成另一个 字符这三种操作。将字符串 A 变成字符串 B 的最少操作步数,称为字符串 A 到字符串 B 的编辑距离。字符串"ABCDEFG"到字符串"BADECG"的编辑距离为________。 三、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1、 Var n, m, i, ans : Integer; Begin Readln(n, m); ans := 0; i := n; While i <= m Do Begin ans := ans + i; Inc(i); End; Writeln(ans); End. 输入:10 20 输出:__________________

2、 Var map, tel : String; i : Integer; Begin
第 4 页 共 12 页

map := '22233344455566677778889999'; Readln(tel); For i := 1 To Length(tel) Do If (tel[i] >= '0') AND (tel[i] <= '9') Then Write(tel[i]) Else If (tel[i] >= 'A') AND (tel[i] <= 'Z') Then Write(map[Ord(tel[i]) - Ord('A') + 1]); End. 输入:CCF-NOIP-2011 输出:__________________ 3、 Const SIZE = 100; Var n, i, sum, x : Integer; a : Array[1..SIZE] Of Integer; Begin Readln(n); FillChar(a, SizeOf(a), 0); For i := 1 To n Do Begin Read(x); Inc(a[x]); End; i := 0; sum := 0; While sum < (n DIV 2 + 1) Do Begin Inc(i); sum := sum + a[i]; End; Writeln(i); End.
第 5 页 共 12 页

输入: 11 4 5 6 6 4 3 3 2 3 2 1 输出:__________________ 4、 Varn, m : Integer; Function solve(n, m : Integer) : Integer; Vari, sum : Integer; Begin If m = 1 Then Begin solve := 1; Exit; End; sum := 0; For i := 1 To n - 1 Do sum := sum + solve(i, m - 1); solve := sum; End; Begin Readln(n, m); Writeln(solve(n, m)); End. 输入:7 4 输出:__________________ 四、完善程序(前 11 空,每空 2 分,后 2 空,每空 3 分,共计 28 分) 1、 (子矩阵)输入一个 n1*m1 的矩阵 a,和 n2*m2 的矩阵 b,问 a 中是否存在子矩阵和 b 相等。 若存在, 输出所有子矩阵左上角的坐标; 若不存在输出 “There is no answer” 。 Const SIZE = 50;
第 6 页 共 12 页

Var n1, m1, n2, m2, i, j, k1, k2 : Integer; a, b : Array[1..SIZE, 1..SIZE] Of Integer; good, haveAns : Boolean; Begin Readln(n1, m1); For i := 1 To n1 Do For j := 1 To m1 Do Read(a[i][j]); Readln(n2, m2); For i := 1 To n2 Do For j := 1 To m2 Do ①; haveAns := FALSE; For i := 1 To n1 - n2 + 1 Do For j := 1 To ② Do Begin ③; For k1 := 1 To n2 Do For k2 := 1 To ④ Do If a[i + k1 - 1][j + k2 - 1] <> b[k1][k2] Then good := FALSE; If good Then Begin Writeln(i, ' ', j); ⑤; End; End; If NOT haveAns Then Writeln('There is no answer'); End. 2、 (大整数开方)输入一个正整数 n(1≤n<10100) ,试用二分法计算它的平方根的整数 部分。 Const
第 7 页 共 12 页

SIZE = 200; Type hugeint = Record len : Integer; num : Array[1..SIZE] Of Integer; End; //len 表示大整数的位数;num[1]表示个位、num[2]表示十位,以此类推 Var s : String; i : Integer; target, left, middle, right : hugeint; Function times(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的乘积 Var i, j : Integer; ans : hugeint; Begin FillChar(ans, SizeOf(ans), 0); For i := 1 To a.len Do For j := 1 To b.len Do ① := ans.num[i + j - 1] + a.num[i] * b.num[j]; For i := 1 To a.len + b.len Do Begin ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10; ②; If ans.num[a.len + b.len] > 0 Then ans.len := a.len + b.len Else ans.len := a.len + b.len - 1; End; times := ans; End; Function add(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的和 Var i : Integer; ans : hugeint; Begin
第 8 页 共 12 页

FillChar(ans.num, SizeOf(ans.num), 0); If a.len > b.len Then ans.len := a.len Else ans.len := b.len; For i := 1 To ans.len Do Begin ans.num[i] := ③; ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10; ans.num[i] := ans.num[i] MOD 10; End; If ans.num[ans.len + 1] > 0 Then Inc(ans.len); add := ans; End; Function average(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的平均数的整数部分 Var i : Integer; ans : hugeint; Begin ans := add(a, b); For i := ans.len DownTo 2 Do Begin ans.num[i - 1] := ans.num[i - 1] + ( ④ ) * 10; ans.num[i] := ans.num[i] DIV 2; End; ans.num[1] := ans.num[1] DIV 2; If ans.num[ans.len] = 0 Then Dec(ans.len); average := ans; End; Function plustwo(a : hugeint) : hugeint; // 计算大整数 a 加 2 后的结果 Var i : Integer; ans : hugeint; Begin ans := a; ans.num[1] := ans.num[1] + 2;
第 9 页 共 12 页

i := 1; While (i <= ans.len) AND (ans.num[i] >= 10) Do Begin ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10; ans.num[i] := ans.num[i] MOD 10; Inc(i); End; If ans.num[ans.len + 1] > 0 Then ⑤; plustwo := ans; End; Function over(a, b : hugeint) : Boolean; // 若大整数 a > b 则返回 1, 否则返回 0 Var i : Integer; Begin If ( ⑥ ) Then Begin over := FALSE; Exit; End; If a.len > b.len Then Begin over := TRUE; Exit; End; For i := a.len DownTo 1 Do Begin If a.num[i] < b.num[i] Then Begin over := FALSE; Exit; End; If a.num[i] > b.num[i] Then Begin over := TRUE; Exit; End; End; over := FALSE;
第 10 页 共 12 页

End; Begin Readln(s); FillChar(target.num, SizeOf(target.num), 0); target.len := Length(s); For i := 1 To target.len Do target.num[i] := Ord(s[target.len - i + 1]) FillChar(left.num, SizeOf(left.num), 0); left.len := 1; left.num[1] := 1; right := target; Repeat middle := average(left, right); If over( ⑧ ) Then right := middle Else left := middle; Until over(plustwo(left), right); For i := left.len DownTo 1 Do Write(left.num[i]); Writeln; End. ⑦ ;

第 11 页 共 12 页

CCF NOIP2011 普及组(Pascal 语言)参考答案与评分标准
一、单项选择题(共 20 题,每题 1.5 分,共计 30 分) 1 B 11 B 2 B 12 A 3 C 13 C 4 C 14 C 5 B 15 C 6 D 16 D 7 C 17 A 8 B 18 A 9 C 19 A 10 C 20 C

二、问题求解(共 2 题,每题 5 分,共计 10 分) 1.1282.3 三、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1.165 2.223664720113.34.20

四、完善程序(前 11 空,每空 2 分,后 2 空,每空 3 分,共计 28 分) (说明: 以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上 机验证,不一定上报科学委员会审查) 1.①read(b[i][j]) ②m1 - m2 + 1 ③good :=true ④m2 ⑤haveAns := true 2.①ans.num[i + j - 1] ②ans.num[i] := ans.num[i] mod 10; ③ans.num[i] + a.num[i] + b.num[i]; ④ans.num[i] mod 2 (或 ans.num[i] and 1) ⑤inc(ans.len) (或 ans.len := ans.len + 1) ⑥a.len<b.len ⑦ord('0')(或 48) ⑧times(middle, middle), target

第 12 页 共 12 页


赞助商链接
相关文章:
全国青少年信息学奥林匹克联赛初赛试题2009-2015
第 22 页共 65 页 第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 Pascal 语言 两小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上...
第十二届全国青少年信息学奥林匹克联赛初赛试题
第十二届全国青少年信息学奥林匹克联赛初赛试题_学科竞赛_初中教育_教育专区。奥林匹克联赛初赛试题 第十二届全国青少年信息学奥林匹克联赛初赛试题 (普及组 C 语言 ...
第十七届全国青少年信息学奥林匹克联赛初赛试题
第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 Pascal 语言 两小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●●一、单项...
CCF NOIP2010全国青少年信息学奥林匹克联赛初赛试题
第十六届全国青少年信息学奥林匹克联赛初赛试题试题及答案 NOIP2010(Pascal 提高组) 一、单项选择题 1.与 16 进制数 A1.2 等值的 10 进制数是 () A.101.2...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:20...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:...
第十三届全国青少年信息学奥林匹克联赛初赛试题
第十三届全国青少年信息学奥林匹克联赛初赛试题_其它课程_高中教育_教育专区。第十三...三.阅读程序写结果 3. 答案: 2 3 5 7 11 13 31 37 41 43 47 17 19...
第十二届全国青少年信息学奥林匹克联赛初赛试题
第十二届全国青少年信息学奥林匹克联赛初赛试题_学科竞赛_小学教育_教育专区。第十二届全国青少年信息学奥林匹克联赛初赛试题( 提高组 C 语言 二小时完成 ) ●● ...
noip2011年第十七届全国青少年信息学奥林匹克联赛初赛答案
noip2011年第十七届全国青少年信息学奥林匹克联赛初赛答案_学科竞赛_初中教育_教育专区。NOIP2011 普及组(Pascal 语言)参考答案与评分标准 一、单项选择题(共 20 题...
第十届全国青少年信息学奥林匹克联赛初赛试题及答案
2004 第十届全国青少年信息学奥林匹克联赛初赛试题及答案 第十届全国青少年信息学奥林匹克联赛初赛试题 (普及组 Pascal 语言 二小时完成) 一、选择一个正确答案代码...
更多相关标签: