第十七届全国青少年信息学奥林匹克联赛初赛试题分析.docx
- 文档编号:18425112
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:16
- 大小:23.67KB
第十七届全国青少年信息学奥林匹克联赛初赛试题分析.docx
《第十七届全国青少年信息学奥林匹克联赛初赛试题分析.docx》由会员分享,可在线阅读,更多相关《第十七届全国青少年信息学奥林匹克联赛初赛试题分析.docx(16页珍藏版)》请在冰点文库上搜索。
第十七届全国青少年信息学奥林匹克联赛初赛试题分析
第十七届全国青少年信息学奥林匹克联赛初赛试题
( 普及组 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
1KB=1024B
1MB=1024KB=1024*1024B
1GB=1024MB=1024*1024KB=1024*1024*1024B
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 分,共计 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
输出:
______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
输出:
__336151610172011_______22366472011
_________
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.
输入:
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 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
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
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 + 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.
CCF NOIP2011普及组(Pascal语言)参考答案与评分标准
一、单项选择题(共20题,每题1.5分,共计30分)
1
2
3
4
5
6
7
8
9
10
B
B
C
C
B
D
C
B
C
C
11
12
13
14
15
16
17
18
19
20
B
A
C
C
C
D
A
A
A
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 :
= 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 ⑦ord('0')(或48) ⑧times(middle, middle), target 您可能也喜欢:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十七 全国青少年 信息学 奥林匹克 联赛 初赛 试题 分析
![提示](https://static.bingdoc.com/images/bang_tan.gif)