第十四届全国青少年信息学联赛(提高组)试题及答案
(提高小组的Pascal语言两个小时)
●●●所有试题的答案都要求写在答题卡上，无效●●
a、单项选择题(* * 10题，每题1.5分，* * 15分。每个问题有且只有一个正确答案)。
1.下列各项中，()不是操作系统软件。
A.Solaris B . Linux C . Sybase D . Windows Vista E . Symbian
2.在微型计算机中，控制器的基本功能是()。
A.控制机器各部分协调工作。b .实现算术运算和逻辑运算。c .存储各种控制信息。
D.访问外部信息，例如存储程序和数据
3.设字符串S =“Olympic”，S的非空字符串个数为()。
C.16 D.17 E.7
4.如果一棵完全二叉树有2*N-1个节点，则其叶节点数为()。
A.N-1 b . 2 * N C . N d . 2n-1 E . N/2
5.将数组{8，23，4，16，77，-5，53，100}中的元素由大到小排序，一次交换任意两个元素，至少交换()次。
a4 b . 5 c . 6d . 7 e . 8
6.假设堆栈S的初始状态为空，元素A、B、C、D、E、F依次放入堆栈，弹出的顺序为B、D、C、F、E、A，那么堆栈容量至少应为()。
A.6 B.5 C.4 D.3 E.2
7.等于十进制数28.5625的四进制数是()。
a . 123.21 b . 131.22 c . 130.22d . 130.21 e . 130.20
8.递归过程和函数调用通常使用一个名为()的数据结构来处理参数和返回地址。
A.队列b .多维数组c .线性表d .链表e .栈
9.TCP/IP是一组网络协议，它们构成了互联网的基础，从字面上看，互联网包括两组协议:传输控制协议(TCP)和互联网协议(IP)。TCP/IP协议将Internet网络系统描述为具有四层功能的网络模型，其中()提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择。
A.链路层b .网络层c .传输层d .应用层e .会话层
10.在有序数组{5，13，19，21，37，56，64，75，88，92，100}上做二分搜索法，在等概率下成功找到平均搜索长度。
a . 35/11 b . 34/11 c . 33/11d . 32/11 e . 34/10
二、不定选择题(* * 10题，每题1.5分，* * * 15分。每个问题的正确答案数大于或等于1。选多选少都不计分)。
11.下列关于图灵的说法正确的是()。
美国计算机协会在1966设立了一个图灵奖，专门用来鼓励那些对计算机做出重要贡献的个人。
B.图灵奖被称为“计算机科学的诺贝尔奖”。
c到目前为止，还没有中国计算机科学家获此殊荣。
图灵奖的名字取自计算机科学先驱、英国科学家艾伦。图灵
12.如果电脑在工作过程中突然断电，()中的信息不会丢失。
A.硬盘B. CPU C. ROM D. RAM
13.如果A =真，B =假，C =真，D =假，下面的逻辑运算表达式真的有()。
A.(A∧B)V(C∧DV？A) B .((？A∧B)VC)∧？B
C.(BVCVD)VD∧A D.A∧(DV？C)∧B
14.Web2.0是近年来互联网上的热门概念之一，其核心是互动和分享。以下网站中，()是Web2.0的典型应用。
A.新浪，Flickr，雅虎，谷歌
15.(2008) 10+(5b) 16的结果是()。
A.(833)16 b .(2099)10 c .(4063)8d .(100001000111)2
16.二叉树T，给定其前件遍历为1 2 4 3 5 7 6(数字为节点号，下同)，后件遍历为4 2 7 5 6 3 1，则二叉树的根遍历为()。
a . 4 2 1 7 5 3 6 b . 2 4 1 7 5 3 6 c . 4 2 1 7 5 6 4d . 2 4 1 5 7 3 6
17.面向对象编程是一种编程方法论，它以对象为编程的基本单位，将数据和程序封装在对象中，以提高软件的可重用性、灵活性和可扩展性。下列关于面向对象编程的说法正确的是()。
A.面向对象的编程方法通常采用自顶向下的设计方法。
B.面向对象编程方法具有继承性、封装性和多态性等特点。
C.支持面向对象特性的称为面向对象编程语言。目前比较流行的语言有C++、JAVA、C#等。
D.面向对象编程的原型来自于Simula语言，后来在SmallTalk语言完善和标准化的过程中，又进行了扩展和重新注释。时至今日，SmallTalk语言仍被视为面向对象的基础。
18.设T是有n个不动点的树，下列说法正确的是()。
A.t连通，无环b.t连通，n-1边。
C.t是非循环的，有n-1条边。以上都不是真的。
19的推荐语言环境。NoIP竞赛是()。
A.dev-c++ B . Visual c++ C . Free Pascal D . Lazarus
20.下列关于防火墙的说法中，正确的是()。
A.防火墙是一种帮助确保信息安全的设备。它将根据特定的规则允许或限制数据的通过。
防火墙可以是专用硬件，也可以是安装在通用硬件上的一套软件。
C.网络层防火墙可以看作是一个IP包过滤，只允许符合特定要求的数据包通过，其余的都禁止通过防火墙。
d应用层防火墙工作在TCP/IP的“应用层”，可以拦截进出一个应用的所有数据包。
三、解题(***2题，每题5分，* * * 10分)
1.有6个城市，任意两个城市由一条路连接。两个城市的距离如下表所示，所以城市1到城市6的最短距离是_ _ _ _ _ _ _ _ _。
城市1城市2城市3城市4城市5城市6
城市102311215
城市2 2 0 2 5 3 12
城市3 3 2 0 3 6 5
城市4 1 5 3 0 7 9
城市5 12 3 6 7 0 2
城市6 15 12 5 9 2 0
2.书架上有21本书，编号从1到21不等。其中，有_ _ _ _ _ _ _ _ _ _ _。
四、阅读程序写结果(***4题，每题8分，32分***)。
1.var
I，a，b，c，d:整数；
f:数组[0..3]的整数；
开始
对于i:=0到3做什么
读作(f[I])；
a:= f[0]+f[1]+f[2]+f[3]；
a:= a div f[0]；
b:= f[0]+f[2]+f[3]；
c:=(b * f[1]+a)div f[2]；
d:= f[(b div c)mod 4]；
if(f[(a+b+c+d)mod 4]>；f[2])那么
开始
a:= a+b；
书面记录(a)
结束
其他
开始
c:= c+d；
writeln(c)；
结束；
结束。
输入:9 19 29 39
输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
2 .过程foo(a，b，c:整数)；
开始
如果a & gtb然后foo(c，a，b)
其他
writeln(a，'，b，'，c)
结束；
var a，b，c:整数；
开始
readln(a，b，c)；
foo(a，b，c)；
结束。
输入:2 1 3
输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _
3 .过程f(a，b，c:整数)；
开始
写(a，b，c，'/')；
如果(a=3)和(b=2)和(c=1)则退出；
if(b & lt；c)然后f(a，c，b)
其他
如果a & ltb那么
如果a & ltc则f(c，a，b) else f(b，c，a)；
结束；
var a，b，c:整数；
开始
readln(a，b，c)；
f(a，b，c)；
结束。
输入:1 3 2
输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
4.var
s:字符串；
I，j，len，k:整数；
开始
readln(s)；
len:=长度(s)；
for i:=1到len do
if(order(s[I])& gt；=ord('A '))和(ord(s[I])& lt；=ord('Z '))那么
s:= chr(ord(s[I])-ord(' A ')+ord(' A ')；
for i:=1到len do
if(ord(s[I])& lt；order(' X '))那么s:= chr(order(s[I])+3)
其他
s:= chr(ord(s[I])-23)；
写；
写('/')；
对于j:=1到3 do
开始
I:= 1；
而我& lt=len-j do
开始
s[I]:= s[I+j]；
I:= I+j；
结束；
结束；
书写内容；
结束。
输入:ABCDEFGuvwxyz
输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
5.改进程序(前6个空格3分，后5个空格2分，* * * 28分)。
1.(求第k个最大的数)给定一个长度为100000的无序正整数序列，另一个数n (1
Var a:array[1..1000000]的整数；
n，m，ans:整数；
过程交换(var a，b:整数)；
var t:整数；
开始
如果(a & lt& gtb)然后开始
t:= a；a:= b；b:= t；
结束；
结束；
函数FindKth(left，right，n:integer):integer；
Var tmp，value，I，j:整数；
开始
如果left=right那么exit(left)；
tmp:=random(右-左)+左；
swap(a[tmp]，a[left])；
值:=____①_____
我:=左；j:=对；
而我& ltj do
开始
while(我& ltj)和(_ _ _ _ _ _ _ _②_ _ _ _ _ _ _ _)做dec(j)；
如果我& lt那就开始吧
a:= a[j]；inc(一)；
结束else break
while(我& ltj)和(_ _ _③_ _)do Inc(I)；
如果我& lt那就开始吧
a[j]:= a[I]；第十届会议；
结束else break
结束；
____④_____
如果我& ltn然后开始公司(I)；exit(FindKth(_ _ _ _ _ _ _⑤_ _ _ _ _)；结束；
如果我& gtn然后开始dec(j)；退出(_ _ _ _ _ _ _⑥_ _ _ _ _ _ _ _)；结束；
退出(一)；
结束；
var i:整数；
开始
随机化；
ans:=-1；
m:= 5；
对于i:=1到m do
读(a[I])；
读作(n)；
ans:=FindKth(1，m，n)；
writeln(a[ans])；
结束。
2.(矩阵中的数)有一个n*n(1≤n≤5000)的矩阵A，对于1 ≤ I < n，1≤j≤n，a[i，j]& lt；a[i+1，j] a[j，I]& lt；a[j，i+1].即矩阵中两个相邻的元素，右边的元素一定比左边的大。对于两个相邻的元素，下面的元素必须大于上面的元素。给定矩阵A中的一个数K，找出K所在的行和列(注意:输入的数据保证矩阵中的数是不同的)。
定义变量
n，k，answerx，answery:整数；
答:数组[1..5000,1..5000]的整数；
过程查找位置；
Var I，j:整数；
开始
I:= n；j:= n；
而j & gt0开始吧
如果a[n，j]& lt；k然后破；
第十届会议；
结束；
______①_________
而a[i，j]& lt；& gtk do
开始
while (___②_____)和(i & gt1)做dec(一)；
while (___③_____)和(j & lt= n)do Inc(j)；
结束；
_______④________
_______⑤________
结束；
var i，j:整数；
开始
读作(n)；
对于i:=1到n do
对于j:=1到n do
read(a[i，j])；
读(k)；
FindKPosition
writeln(answerx，' '，answery)；
结束。NOIP2008改进小组(Pascal语言)参考答案和评分标准
1.选择题:(65438+每题0.5分)
1.C 2。A 3。B 4。C 5。B
6.D 7。D 8。E 9。B 10。C
二、不定选择题(* * 10题，每题1.5分，* * * 15分。每个问题的正确答案数大于或等于1。选多选少都不计分)。
11.ABD 12。AC 13。公元前14年。B 15。美国广播公司
16.ABD 17。BCD 18。ABC 19。ACD 20。AcceleratedBusinessCollectionandDelivery（美国邮局采用的）加快收寄投递系统
三、解题:(***2题，每题5分，* * * 10分)
1.7
2.3060
四、阅读程序写结果(***4题，每题8分，32分作***)
1.23(信心问题)
2.1，3，2(简单递归)
3.132/213/231/312/321/(全部安排)
4.defghijxyzabc/hfizxjaybcccc(字符串替换)
5.改进程序(前6个空格3分，后5个空格2分，* * * 28分)。
(注意:在下面的过程中可能有一些等价的填空方法。各省可以请自己的专家在电脑上审核，不一定要报科委审核。)
1.①a[左]
②a[j]& lt；值(或a [j] < =值)
③a[I]& gt；值(或a[i] > =值)
④ a[i] :=值；
⑤我，右，n
⑥ FindKth(左，I，n)
2.①Inc(j)；(或者j:= j+1；)
② a[i，j]& gt；k
③ a[i，j]& lt；k
④answerx:= I；
⑤answery:= j；