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

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


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

Pascal 语言

两小时完成


●●

全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效

一、 单项选择题 (共 20 题, 每题 1.5 分, 共计 30 分。 每题有且仅有一个正

确选项。 ) 1、在二进制下,1101001 + ( B ) = 1110110。 A、1011 B、1101 C、1010 D、1111 2、字符“0”的 ASCII 码为 48,则字符“9”的 ASCII 码为( B )。 A、39 B、57 C、120 D、视具体的计算机而定 3、一片容量为 8GB 的 SD 卡能存储大约( C )张大小为 2MB 的数码照片。 A、1600 B、2000 C、4000 D、16000

1 KB=1024 B 1 MB=1024KB= 1024 * 1024 B 1 GB=1024 MB=1024 * 1024 KB=1024 * 1024 * 1024 B
4、摩尔定律(Moore's law)是由英特尔创始人之一戈登·摩尔(Gordon Moore)提 出来的。根据摩尔定律,在过去几十年以及在可预测的未来几年,单块集成电路的集成度大 约每( C )个月翻一番。 A、1 B、6 C、18 D、36 5、 无向完全图是图中每对顶点之间都恰有一条边的简单图。 已知无向完全图 G 有 7 个 顶点,则它共有( B )条边。 A、7 B、21 C、42 D、49 6、寄存器是( D )的重要组成部分。 A、硬盘 B、高速缓存 C、内存 D、中央处理器(CPU) 7、如果根结点的深度记为 1,则一棵恰有 2011 个叶结点的二叉树的深度最少是 ( C )。 A、10 B、11 C、12 D、13 8、体育课的铃声响了,同学们都陆续地奔向操场,按老师的要求从高到矮站成一排。每个 同学按顺序来到操场时, 都从排尾走向排头, 找到第一个比自己高的同学, 并站在他的后面。 这种站队的方法类似于( B )算法。 A、快速排序 B、插入排序 C、冒泡排序 D、归并排序 9、一个正整数在二进制下有 100 位,则它在十六进制下有( C )位。 A、7 B、13 C、25 D、不能确定 10、有人认为,在个人电脑送修前,将文件放入回收站中就是已经将其删除了。这种想法 是( C )。 A、正确的,将文件放入回收站意味着彻底删除、无法恢复 B、不正确的,只有将回收站清空后,才意味着彻底删除、无法恢复 C、不正确的,即使将回收站清空,文件只是被标记为删除,仍可能通过恢复软件找回 D、不正确的,只要在硬盘上出现过的文件,永远不可能被彻底删除 11、广度优先搜索时,需要用到的数据结构是( B )。 A、链表 B、队列 C、栈 D、散列表 12、在使用高级语言编写程序时,一般提到的“空间复杂度”中的“空间”是指( A )。 A、程序运行时理论上所占的内存空间

B、程序运行时理论上所占的数组空间 C、程序运行时理论上所占的硬盘空间 D、程序源文件理论上所占的硬盘空间 13、在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素,最坏情况下运行 的时间复杂度是(C )。 A、O(1) B、O(log n) C、O(n) D、O(n log n) 14、生物特征识别,是利用人体本身的生物特征进行身份认证的一种技术。目前,指纹识 别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于生 物特征识别技术及其应用的是( C )。

A、指静脉验证 B、步态验证 C、ATM 机密码验证 D、声音验证 15、现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只 由 4 个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为 700、600、 300、 200。那么,“也”字的编码长度是( C )。 A、1 B、2 C、3 D、4 16、关于汇编语言,下列说法错误的是( D )。 A、是一种与具体硬件相关的程序设计语言 B、在编写复杂程序时,相对于高级语言而言代码量较大,且不易调试 C、可以直接访问寄存器、内存单元、以及 I/O 端口 D、随着高级语言的诞生,如今已完全被淘汰,不再使用 17、( A )是一种选优搜索法,按选优条件向前搜索,以达到目标。当探索到某一步 时,发现原先选择并不优或达不到目标,就退回一步重新选择。 A、回溯法 B、枚举法 C、动态规划 D、贪心法 18、1956 年( A)授予肖克利(William Shockley)、巴丁(John Bardeen) 和布拉顿(Walter Brattain),以表彰他们对半导体的研究和晶体管效应的发现。 A、诺贝尔物理学奖 B、约翰·冯·诺依曼奖 C、图灵奖 D、高德纳奖(Donald E. Knuth Prize) 19、对一个有向图而言,如果每个节点都存在到达其他任何节点 的路径,那么就称它是强连通的。例如,右图就是一个强连通图。 事实上,在删掉边( A )后,它依然是强连通的。 A、a B、b C、c D、d 20、从 ENIAC 到当前最先进的计算机,冯·诺依曼体系结构始 终占有重要的地位。冯·诺依曼体系结构的核心内容是( C )。 A、采用开关电路 B、采用半导体器件 C、采用存储程序和程序控制原理 D、采用键盘输入 二、问题求解(共 2 题,每题 5 分,共计 10 分)

1、每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时,它才 是有效的。例如,00000000、01010011 都是有效的序列号,而 11111110 不是。那 么,有效的序列号共有____128____个。 2、定义字符串的基本操作为:删除一个字符、插入一个字符和将一个字符修改成另一个字 符这三种操作。将字符串 A 变成字符串 B 的最少操作步数,称为字符串 A 到字符 串 B 的编辑距离。字符串"ABCDEFG"到字符串"BADECG"的编辑距离为___3___。 三、阅读程序写结果(共 4 题,每题 8 分,共计 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 输出:______165_______ 2、 Var map, tel : String; i : Integer; Begin 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 32 分)

输出:__336151610172011__ _________ 3、 Const SIZE = 100; Var

_____22366472011

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. 输入: 11 4 5 6 6 4 3 3 2 3 2 1 输出:_______3________ 4、 Var n, m : Integer; Function solve(n, m : Integer) : Integer; Var i, 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 输出:_________20_____ 四、完善程序(前 11 空,每空 2 分,后 2 空,每空 3 分,共计 28 分) 1、(子矩阵)输入一个 n1*m1 的矩阵 a,和 n2*m2 的矩阵 b,问 a 中是否存在子矩阵和 b 相等。 若存在, 输出所有子矩阵左上角的坐标; 若不存在输出 “There is no answer” 。 Const SIZE = 50; 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 Begin ③ For k1 := 1 To n2 Do For k2 := 1 To ④ Do ; j := 1 To ② Do ;

If a[i + k1 - 1][j + k2 - 1] <> b[k1][k2] The n good := FALSE; If good Then Begin Writeln(i, ' ', j); ⑤ End; End; If NOT haveAns Then Writeln('There is no answer'); End. 100 2、(大整数开方)输入一个正整数 n(1≤n<10 ),试用二分法计算它的平方根的整数 部分。 Const 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 ① + 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] D IV 10; ② ; := ans.num[i + j 1] ;

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 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; 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; 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 ⑦ ; 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. ) + 1]) -

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.128 2.3

三、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1.165 2.22366472011 3.3 4.20

四、完善程序(前 11 空,每空 2 分,后 2 空,每空 3 分,共计 28 分) (说明: 以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上 机验证,不一定上报科学委员会审查) 1.①read(b[i][j]) ②m1 - m2 + 1 ③good := ④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 true

⑦ord('0')(或 48) ⑧times(middle, middle), target
您可能也喜欢:


相关文章:
第十七届全国青少年信息学奥林匹克联赛初赛试题
第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组●● Pascal 语言 两小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一、 单项...
第十七届全国青少年信息学奥林匹克联赛初赛试题
第十七届全国青少年信息学奥林匹克联赛初赛试题(提高组 C 语言 两小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●●一、单项选择题(共...
第十七届全国青少年信息学奥林匹克联赛初赛试题(提高组_C++)
第十七届全国青少年信息学奥林匹克联赛初赛试题(提高组_C++)_学科竞赛_高中教育_教育专区。第十七届全国青少年信息学奥林匹克联赛初赛试题(提高组 C++语言 ●● 两小...
第十七届全国青少年信息学奥林匹克联赛初赛试题
第十七届全国青少年信息学奥林匹克联赛初赛试题_营销/活动策划_计划/解决方案_应用...= -1)) dfs(i, len + e[x][i]); CCF NOIP2011初赛 提高组 C 6 ...
全国青少年信息学奥林匹克联赛初赛试题2009-2015
第 22 页共 65 页 第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 Pascal 语言 两小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上...
第十届全国青少年信息学奥林匹克联赛初赛试题及答案
2004 第十届全国青少年信息学奥林匹克联赛初赛试题及答案 第十届全国青少年信息学奥林匹克联赛初赛试题 (普及组 Pascal 语言 二小时完成) 一、选择一个正确答案代码...
第十七届全国青少年信息学奥林匹克联赛初赛试题 (普及组 PASCAL语言)
第十七届全国青少年信息学奥林匹克联赛初赛试题 (普及组 PASCAL语言) NOIP2011NOIP2011隐藏>> 分享到: X 分享到: 使用一键分享,轻松赚取财富值, 了解详情 嵌...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:20...
第十七届全国青少年信息学奥林匹克联赛提高组初赛试题_
第十七届全国青少年信息学奥林匹克联赛提高组初赛试题__学科竞赛_高中教育_教育专区。第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高组●● C 语言 两小时完成...
2011第十七届全国青少年信息学奥林匹克联赛普及组初赛试题
2011第十七届全国青少年信息学奥林匹克联赛普及组初赛试题_教学案例/设计_教学研究_教育专区。第十七届全国青少年信息学奥林匹克联赛初赛试题 (普及组 Pascal 语言两...
更多相关标签:
小学奥林匹克信息学 | 奥林匹克信息学竞赛 | 青少年信息学奥林匹克 | 奥林匹克信息学 | 奥林匹克信息学有用吗 | 奥林匹克信息学 江苏 | 奥林匹克信息学试题 | 福建奥林匹克信息学 |