2006年南海青少年信息学奥林匹克竞赛初赛问题急求解答。
(普及组Pascal语言两小时完成)
●●●所有试题的答案都要求写在答题卡上，无效●●
a、单项选择题(***20题，每题1.5分，* * * 30分。每个问题有且只有一个正确答案。
1.在下列世界顶级奖项中，授予在计算机科学技术领域做出突出贡献的科学家的奖项是()。
A.沃尔夫奖b .诺贝尔奖c .菲尔兹奖d .图灵奖
2.以下软件中，不属于NOIP赛(复赛)的推荐语言环境是()。
A.gcc/g++ B. Turbo Pascal
C.莱茵河自由帕斯卡尔
3.断电后仍能保存数据的有()。
A.寄存器B. rom C. ram D .缓存
4.Linux是一种()。
A.绘图软件b .编程语言c .操作系统d .网页浏览器
5.CPU是()的简称。
A.硬盘b .中央处理器c .高级编程语言d .核心寄存器
6.在计算机中，防火墙的作用是()。
A.防止火势蔓延b .防止网络攻击
C.防止电脑死机d .防止用户误删数据。
7.下列关于计算机语言的说法中，()是不正确的。
A.Pascal和C都是编译和执行的高级语言。
b高级语言程序比汇编语言程序更容易从一台计算机移植到另一台计算机。
C.C++是历史上第一种支持面向对象的计算机语言。
D.与汇编语言相比，高级语言程序更容易阅读。
8.下列关于计算机算法的说法中，不正确的是()。
A.正确的算法必须至少有一个输入。
B.算法的改进极大地推动了计算机科学技术的进步。
c判断算法好坏的主要标准是算法的时间复杂度和空间复杂度。
d .目前还有很多关系国计民生的重要课题，还没有找到可以在计算机上实现的有效算法。
9.下列排序算法中，不以“比较”为主要运算的算法是()。
A.选择排序b .冒泡排序c .插入排序d .基数排序
10.编程时(使用任何高级语言，不一定是Pascal)，如果需要从磁盘文件输入大型二维数组(例如1000*1000的双数组)，按行读取(即外循环是关于行的)和按列读取(即外循环是关于列的)。
A.没有区别。b .逐行阅读较高。
C.按列阅读较高。d .这取决于数组是如何存储的。
11.在Pascal语言中，表达式(21 xor 2)的值是()。
A.441
12.在Pascal语言中，判断A不等于0，B不等于0的正确条件表达式是()。
A.not a=0或not b=0 B. not((a=0)和(b=0))
C.而不是(a=0，b = 0)d .(a & lt；& gt0)和(b & lt& gt0)
13.一个车站狭长，宽度只能容纳一辆车，只有一个出入口。已知某时刻车站状态为空，从该时刻开始的进出站记录为:“进、出、入、出、出、入、出”。假设车辆进站顺序为1，2，3，...，那么车辆出站的顺序是()。
A.1，2，3，4，5 B
C.1，4，3，7，6
14.高度为n的平衡二叉树是指如果去掉叶节点和相应的分支，它应该是高度为n-1的全二叉树。这里树的高度高于叶节点的最大深度，根节点的深度为0。如果一棵平衡二叉树* *有23，865，438+0个节点，那么树的高度是()。
A.10 b . 11c . 12d . 13
15.十进制数1770对应的八进制数是()。
A.3350 B. 3351 C. 3352 D. 3540
16.对一个由5个数字组成的序列进行排序，不管原来的顺序如何，都可以通过至少()次比较完成从小到大的排序。
A.6 B. 7 C. 8 D. 9
17.设A = B = D =真，C =假，下列逻辑运算表达式为真的有()。
A.(A∧B)∨(C∧D) B. ((A∨B∨D)∧C)
C.A∧(B∨C∨D) D
18的结果。(2010) 16+(32) 8是()。
A.(8234)10
C.(10000000110)2
19.设堆栈S的初始状态为空，元素a、b、c、d、e依次放入堆栈，下列弹出顺序是不可能的()。
A.答案是a，b，c，e，d
C.阿、英、中、乙、丁、丁、丙、英、乙、阿
20.已知6节点二叉树的第一次根遍历是1 2 3 4 5 6(数字为节点数，下同)，最后一次根遍历是3 2 5 6 4 1，那么二叉树可能的中间根遍历是()。
A.3 2 1 4 6 5 B. 3 2 1 5 4 6
C.2 1 3 5 4 6 D. 2 3 1 4 6 5
2.解题(***2题，每题5分，* * * 10分)
1.(寻找假币)硬币80个，其中一个是假币，重量略轻。所有真正的硬币都有同样的重量。如果用没有砝码的天平称重，至少需要称重几次才能查出假币？您还应该指出1时间的称重方法。请写下你的结果:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
2.(捡石头游戏)一共有五堆石头，石头的个数依次是3，5，7，19，50。甲乙双方轮流从任意一堆中挑选(一次只能拿一堆，拿最后一块石头的获胜。A先拿，问A有没有胜算策略(就是不管B怎么拿，只要不出错A就能赢)。如果有，A第一步应该拿多少？请写下您的结果:
_________________________________________________。
三个。阅读程序写作成绩(***4题，每题8分，32分***)
1.程序ex 301；
定义变量
u:array[0..3]的整数；
I，a，b，x，y:整数；
开始
y:= 10；
对于i:=0到3做什么
read(u[I])；
a:=(u[0]+u[1]+u[2]+u[3])div 7；
b:= u[0]div((u[1]-u[2])div u[3])；
x:=(u[0]+a+2)-u[(u[3]+3)mod 4]；
if(x & gt；10)
y:= y+(b * 100-u[3])div(u[u[0]mod 3]* 5)
其他
y:= y+20+(b * 100-u[3])div(u[u[0]mod 3]* 5)；
writeln (x，'，'，y)；
结束。{*注意:在这个例子中，给定的输入数据可以避免分母0或下标越界。}
输入:9 3 9 4
输出:_ _ _ _ _ _ _ _ _ _
2.程序ex302
常数
m:数组[0..4] of integer=(2，3，5，7，13)；
定义变量
I，j:整数；
t:longint；
开始
对于i:=0到4 do
开始
t:= 1；
对于j:=1到m[i]-1 do
t:= t * 2；
t:=(t * 2-1)* t；
写(t，' ')；
结束；
writeln
结束。
输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
3.程序ex303
常数
NN = 7；
类型
Arr1=array[0..30]的char
定义变量
s:arr 1；
k，p:整数；
函数fun(s:arr 1；答:charn:整数):整数；
定义变量
j:整数；
开始
j:= n；
while(a & lt；s[j])和(j & gt0)do dec(j)；
好玩:= j；
结束；
开始
对于k:=1到NN do
s[k]:= chr(ord(' A ')+2 * k+1)；
k:=fun(s，' M '，NN)；
writeln(k)；
结束。
输出:_ _ _ _ _ _ _ _ _ _ _
4 .程序ex304
定义变量
x，x2:longint；
程序数字(n，m:longint)；
var n2:整数；
开始
如果(m & gt0)然后
开始
N2:= n mod 10；
写(N2:2)；
如果(m & gt1)然后是数字(n格10，m格10)；
N2:= n mod 10；
写(N2:2)；
结束；
结束；
开始
writeln('输入一个数字:')；
readln(x)；
x2:= 1；
while(x2 & lt；x)do x2:= x2 * 10；
x2:= x2 div 10；
数字(x，x2)；
writeln五
结束。
输入:9734526
输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
4.完善程序(前4个空格2.5分，后6个空格3分，* * * 28分)。
1.(全排列)下面程序的功能是生成从1到n (n
123 132 213 231 321
312
程序:
程序ex 401；
定义变量
I，n，k:整数；
答:数组[1..10]的整数；
计数:longint{变量count记录不同排列的数量，用于控制此处的换行。}
过程perm(k:整数)；
var j，p，t:整数；
开始
如果①那么
开始
inc(计数)；
对于p:=1到k do
写(a[p]:1)；
写(')；
if ( ②)则写ln；
退出；
结束；
对于j:=k到n do
开始
t:= a[k]；a[k]:= a[j]；a[j]:= t；
③ ;
t:= a[k]；④ ;
结束
结束；
开始
writeln('条目n:')；
读作(n)；
计数:= 0；
对于i:=1到n做a[I]:= I；
⑤ ;
结束。
2.输入一个奇数p (p
(1)的所有数字。除了最后一行，每行输出50位数字。(2)乘积的位数。
例1:输入p=13，既然13 * 8547 = 11111，就应该是输出(1)。
例2:输入p=147，输出结果应该是(1)75585789871504157218442932728647013。
(2)42，即等式右端有42个1。
程序:
程序ex402
定义变量
p，a，b，c，t，n:longint；
开始
虽然(真的)做
开始
writeln('输入p，最后一位是1或3或7或9:')；
readln(p)；
if(p mod 2 & lt；& gt0)和(p mod 5 & lt& gt0)然后
⑥ ;{如果输入的数字符合要求，则结束循环}
结束；
a:= 0；n:= 0；
while(a & lt；p) do
开始
a:= a * 10+1；公司(n)；
结束；
t:= 0；
重复
b:= a div p；
写(b:1)；
Inc(t)；
if ( ⑦)然后writeln
c:=⑧；a:=⑨Inc(n)；
直到c & lt=0;
十二月(日)；
writelnwriteln('n= '，⑩)；
结束。
第十二届全国青少年信息学联赛(普及组)答案/noi/showNews.jsp？newsId=200190000064
普及组参考答案及评分标准(Pascal语言)
1.选择题:(65438+每题0.5分)
1.D 2。B 3。B 4。C 5。B 6。B 7。C 8。一个9。D 10。D
11.C 12。D 13。C 14。B 15。C 16。B 17。B 18。A 19。C 20。B
二、解题: (每题5分)
1.4倍(1分)，
第一步:分成3组:27、27、26，将前2组放在天平上(4分)。
2.有胜策(1分)，第1次从第5堆(4分)拿32颗石头。
第三，阅读程序写出结果
1.10，10 (4点为1的数，1点无逗号)
2.6 28 496 8128 33550336
(前两对1给1分，后三对1给2分。)
3.5
4.625437999734526(数字间无空格扣2分)
四、完善程序(前四次清空(①-④)，每次清空2.5分，后六次清空(⑤-⑩)，每次清空3分)
1.① k = n(或n=k)
②计数模式5=0
③烫发(k+1)
④a[k]:= a[j]；a[j]:=t
⑤烫发(1)
2.⑥断裂
⑦ t mod 50=0
8 A-P * B(或a-b*p)
⑨c * 10+1(或10*c+1)
⑩ n