编辑noip初赛试题及答案完美word版.docx
《编辑noip初赛试题及答案完美word版.docx》由会员分享，可在线阅读，更多相关《编辑noip初赛试题及答案完美word版.docx（19页珍藏版）》请在冰点文库上搜索。
编辑noip初赛试题及答案完美word版
第十七届全国青少年信息学奥林匹克联赛初赛试题
（提高组Pascal语言两小时完成）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一、单项选择题（共20题，每题1.5分。
共计30分。
每题有且仅有一个正确选项。
）
1．在二进制下，1100011+（）=1110000。
A．1011B．1101C．1010D．1111
2．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。
A．66B．5AC．50D．视具体的计算机而定
3．右图是一棵二叉树，它的先序遍历是（）。
A．ABDEFCB．DBEFACC．DFEBCAD．ABCDEF
4．寄存器是（）的重要组成部分。
A．硬盘B．高速缓存C．内存D．中央处理器（CPU）
5．广度优先搜索时，需要用到的数据结构是（）。
A．链表B．队列C．栈D．散列表
6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。
A．程序运行时理论上所占的内存空间
B．程序运行时理论上所占的数组空间
C．程序运行时理论上所占的硬盘空间
D．程序源文件理论上所占的硬盘空间
7．应用快速排序的分治思想，可以实现一个求第K大数的程序。
假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。
A．O（n2）B．O（nlogn）C．O（n）D．O
（1）
8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。
A．微软B．美国计算机协会（ACM）C．联台国教科文组织D．万维网联盟（W3C）
9．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。
每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。
这种站队的方法类似于（）算法。
A．快速排序B．插入排序C．冒泡排序D．归并排序
10．1956年（）授予肖克利（WilliamShockley）、巴丁（JohnBardeen）和布拉顿（WalterBrattain），以表彰他们对半导体的研究和晶体管效应的发现。
A．诺贝尔物理学奖
B．约翰•冯•诺依曼奖
C．图灵奖
D．高德纳奖（DonaldE．KnuthPrize）
二、不定项选择题（共10题，每题1．5分，共计15分。
每题有一个或多个正确选项。
多选或少选均不得分。
）
1．如果根结点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（）。
A．10B．11C．12D．2011
2．在布尔逻辑中，逻辑“或”的性质有（）。
A．交换律：
PVQ=QVP
B．结台律：
PV（QVR）=（PVQ）VR
C．幂等律：
PVP=P
D．有界律：
PV1=1（1表示逻辑真）
3．一个正整数在十六进制下有100位，则它在二进制下可能有（）位。
A．399B．400C．401D．404
4．汇编语言（）。
A．是一种与具体硬件无关的程序设计语言
B．在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试
C．可以直接访问寄存器、内存单元、I/O端口
D．随着高级语言的诞生，如今已完全被淘汰，不再使用
5．现有一段文言文，要通过二进制哈夫曼编码进行压缩。
简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。
那么，“也”字的编码长度可能是（）。
A．1B．2C．3D．4
6．生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。
目前，指纹识别、虹膜识别、人脸识别等技术己广泛应用于政府、银行、安全防卫等领域。
以下属于生物特征识别技术及其
应用的是（）。
A．指静脉验证B．步态验证C．ATM机密码验证D．声音验证
7．对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（）会使逆序对的个数减少3。
A．7B．5C．3D．6
8．计算机中的数值信息分为整数和实数（浮点数）。
实数之所以能表示很大或者很小的数，是由于使用了（）。
A．阶码B．补码C．反码D．较长的尾数
9．对右图使用Dijkstra算法计算S点到其余各点的最短路径
长度时，到B点的距离d[B]初始时赋为8，在算法的执行过程
中还会出现的值有（）。
A．3B．7C．6D．5
10．为计算机网络中进行数据交换而建立的规则、标准或约定的集合成为网络协议。
下列英文缩写中，（）是网络协议。
A．HTTPB．TCP/IPC．FTPD．WWW
三、问题求解（共2题，每题5分，共计10分）
1．平面图是可以画在在平面上，且它的边仅在顶点上才能相交的简单
无向图。
4个顶点的平面图至多有6条边，如右图所示。
那么，5个顶
点的平面图至多有______条边。
2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。
举例说明，对于字符串”BcA”，可以将A移到B之前，变成字符串”ABC”。
如果要将字符串”DACHEBGIF”变成”ABCDEFGHI”，最少需要________次操作。
四、阅读程序写结果（共4题，每题8分，共计32分）
1．
Const
SIZE=100;
var
n,i,sum,x:
integer;
a:
array[1..SIZE]ofinteger;
begin
readln（n）;
fillchar（a,sizeof（a）,0）;
fori:
=1tondo
begin
read（x）;
inc（a[x]）;
end;
i:
=0;
sum:
=0;
whilesum<（ndiv2+1）do
begin
inc（i）;
sum:
=sum+a[i];
end;
writeln（i）;
end．
输入：
11
45664332321
输出：
2．
var
n:
integer;
proceduref2（x,y:
integer）;
forward;
proceduref1（x,y:
integer）;
begin
ifxf2（y,x+y）;
end;
proceduref2（x,y:
integer）;
begin
write（x,’’）;
f1（y,x+y）;
end;
begin
readln（n）;
f1（0,1）;
end．
输入：
30
输出：
_____________
3．
const
V=100;
var
visited:
array[1..v]ofboolean;
e:
array[1..V,1..V]ofinteger;
n,m,ans,i,j,a,b,c:
integer;
proceduredfs（x,len:
integer）;
var
I:
integer;
begin
visited[x]:
=true;
iflen>ansthen
ans:
=len;
fori:
=1tondo
if（notvisited[i]）and（e[x,i]<>-1）then
dfs（i,len+e[x,i]）;
visited[x]:
=false;
end;
begin
readln（n,m）;
fori:
=1tondo
forj:
=1tondo
e[i][j]:
=-1;
fori:
=1tomdo
begin
readln（a,b,c）;
e[a][b]:
=c;
e[b][a]:
=c;
end;
fori:
=1tondo
visited[i]:
=false;
ans:
=0;
fori:
=1tondo
dfs（i,0）;
writeln（ans）;
end.
输入：
46
1210
2320
3430
4140
1350
2460
输出：
__________
4.
const
SIZE=10000;
LENGTH=10;
var
sum:
longint;
n,m,i,j:
integer;
a:
array[1..SIZE,1..LENGTH]ofinteger;
functionh（u,v:
integer）:
integer;
var
ans,i:
integer;
begin
ans:
=0;
fori:
=1tondo
ifa[u][i]<>a[v][i]then
inc（ans）;
h:
=ans;
end;
begin
readln（n）;
filichar（a,sizeof（a）,0）;
m:
=1;
repeat
i:
=1;
while（i<=n）and（a[m][i]=1）do
inc（i）;
ifi>nthen
break;
inc（m）;
a[m][i]:
=1;
forj:
=i+1tondo
a[m][j]:
=a[m-1][j];
untilfalse;
sum:
=0;
fori:
=1tomdo
forj:
=1tomdo
sum:
=sum+h（i,j）;
writeln（sum）;
end.
输入：
7
输出：
____________
五、完善程序（第1题，每空2分，第2题，每空3分，共计28分）
1.（大整数开方）输入一个正整数n（1≤n<10100），试用二分法计算它的平方根的整数部分。
const
SIZE=200;
type
hugeint=record
len:
integer;
num:
array[1..SIZE]ofinteger;
end;
//len表示大整数的位数；num[1]表示个位、num[2]表示十位，以此类推
var
s:
string;
i:
integer;
target,left,middle,right:
hugeint;
functiontimes（a,b:
hugeint）:
hugeint:
var
i,j:
integer;
ans:
hugeint;
begin
filIchar（ans,sizeof（ans）,0）;
fori:
=1toa.1endo
forj:
=1tob.1endo
___①___:
=ans.num[i+j—1]+a.num[i]*b.num[j];
fori:
=1toa.len+b.1endo
begin
ans.num[i+1]:
=ans.num[i+1]+ans.num[i]div10;
___②___;
ifans.num[a.1en+b.1en]>0
thenans.len:
=a.1en+b.1en
elseans.len:
=a.1en+b.1en–1;
end;
times:
=ans;
end;
functionadd（a,b:
hugeint）:
hugeint;
var
i:
integer;
ans:
hugeint;
begin
fillchar（ans.num,sizeof（ans.num）,0）;
ifa.1en>b.1en
thenans.len:
=a.1en
elseans.len:
=b.len;
fori:
=1toans.1endo
begin
ans.num[i]:
=___③___;
ans.num[i+1]:
=ans.num[i+1]+ans.num[i]div10;
ans.num[i]:
=ans.num[i]mod10;
end;
ifans.num[ans.1en+1]>0
theninc（ans.len）;
add:
=ans;
end;
functionaverage（a,b:
hugeint）:
hugeint;
var
i:
integer;
ans:
hugeint;
begin
ans:
=add（a,b）;
fori:
=ans.1endownto2do
begin
ans.num[i-1]:
=ans.num[i-1]+（___④___）*10;
ans.num[i]:
=ans.num[i]div2;
end;
ans.num[i]:
=ans.num[i]div2;
ifans.num[ans.len]=0
thendec（ans.len）;
average:
=ans;
end;
functionplustwo（a:
hugeint）:
hugeint;
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]div10;
ans.num[i]:
=ans.num[i]mod10;
inc（i）;
end;
ifans.num[ans.len+1]>0
then___⑤___;
plustwo:
=ans;
end;
functionover（a,b:
hugeint）:
boolean;
var
i:
integer;
begin
if（___⑥___）then
begin
over:
=false;
exit;
end;
ifa.1en>b.1enthen
begin
over:
=true;
exit;
end;
fori:
=a.lendownto1do
begin
ifa.num[i]begin
over:
=false;
exit;
end;
ifa.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.1en:
=1ength（s）;
fori:
=1totarget.1endo
target.num[i]:
=ord（s[target.1en–i+1]）-___⑦___;
filichar（left.num,sizeof（1eft.num）,0）;
left.1en:
=1;
left.num[i]:
=1;
right:
=target;
repeat
middle:
=average（1eft,right）;
ifover（___⑧___）
thenright:
=middle
else1eft:
=middle;
untilover（plustwo（1eft）,right）;
fori:
=left.1endownto1do
write（1eft.num[i]）;
writeln;
end.
2.（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：
首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。
例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。
现输入序列的规模n（1≤n<100）和序列的n个元素，试求其对应的笛号尔树的深度d（根节点深度为1），以及有多少个叶节点的深度为d。
const
SIZE=100;
INFINITY=1000000;
var
n,maxDeep,num,i:
integer;
a:
array[1..SIZE]ofinteger;
proceduresolve（1eft,right,deep:
integer）;
var
i,j,min:
integer;
begin
ifdeep>maxDeepthen
begin
maxDeep:
=deep;
num:
=1;
end
elseifdeep=maxDeepthen
___①___;
min:
=INFINITY;
fori:
=1efttorightdo
ifmin>a[i]then
begin
min:
=a[i];
___②___;
end;
ifleft___③___;
ifj___④___;
end;
begin
readln（n）;
fori:
=1tondo
read（a[i]）;
maxDeep:
=0;
solve（1,n,1）;
writeln（maxDeep,‘’,num）;
end.
写在后面：
化了整整三个晚上，终于把这资料给整好了。
从扫描、校对到排版，真想不到有如此多的错误（可能是我的扫描仪太差了），虽然很累，却很开心。
以前都是我享用别人的奥赛资料，今天终于轮到我贡献一下了。
分享毕竟是快乐的！
感谢所有热衷于网络资料分享的人们，还有我自己。
——江郎2011-10-25
CCFNOIP2011提高组（Pascal语言）参考答案与评分标准
△workplacen.工作场所；工作地点一、单项选择题（共10题，每题1.5分，共计15分）
1
2
3
4
tinn.锡5
△Berlinn.柏林（德国首都）6
slidevt.&vi.（使）滑动；（使）滑行7
8
9
violinistn.小提琴演奏者10
inparticular尤其；特别B
simplifyvt.简化B
A
D
B
A
△coffinn.棺材C
D
B
straightforwardadj.简单的；直接的；A
二、不定项选择题（共10题，每题1.5分，共计15分，多选或少选均不得分）
qualityn.质量；品质；性质1
2
3
4
5
6
7
8
9
10
CD
ABCD
AB
BC
BC
ABD
CD
A
BCD
ABC
三、问题求解（共2题，每题5分，共计10分）
1．9
2．4
四、阅读程序写结果（共4题，每题8分，共计32分）
1．3
2．1251334
3．150
4．57344
五、完善程序（第1题，每空2分，第2题，每空3分，共计28分）
（说明：
以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）
1．①ans.num[i+j-1]
②ans.num[i]:
=ans.num[i]mod10;
③ans.num[i]+a.num[i]+b.num[i];
④ans.num[i]mod2（或ans.num[i]and1）
⑤inc（ans.len）（或ans.len:
=ans.len+1）
⑥a.len⑦ord（'0'）（或48）
⑧times（middle,middle）,target
2．①inc（num）（或num:
=num+1）
②j:
=i
③solve（left,j-1,deep+1）
④solve（j+1,right,deep+1）
升级会员 