2011 义乌市信息学奥赛试题(初中)

2011年义乌市中小学生信息学奥赛选拔赛试题（初中）
（初中组 PASCAL语言 ）
●●全部试题答案都要求写在答卷纸上，写在试卷上一律无效●●
一．选择一个正确答案代码（A/B/C/D），填入每题的括号内：
（每题1.5分，每题只有一个正确答案，多选或错选都无分。共30分）
1）ASCII码是一种字符编码，每一字符存储时需占用的字节数是（ ）
A）8 B）2 C）4 D）1
2）GB 2312是一种汉字编码，每一汉字存储时需占用的字节数是（ ）
A）1 B）2 C）4 D）8
3）我们一般把能播放VCD、CD光盘来看电影、听音乐的电脑称为“多媒体电脑”，下列硬件设备中，是多媒体电脑必须具备的是（ ）。
A) CD-ROM光驱 B) 网卡 C) 扫描仪 D) 打印机
4）计算机有计算功能，那么这个“计算”是在下列哪个硬件设备中完成的？
A) CPU B) ROM C) 内存 D) 显示卡
5）主要用于文字处理的软件是（ ）
A）VB B）Photoshop C）Excel D）Word
6）十进制数65对应的二进制数是（ ）
A) 1000001 B) 1000100 C) 1110011 D) 1111111
7）二进制数(1101)2表示成十进制数是( )
A）11 B）15 C）13 D）1101
8）pascal程序设计中，下列整数中不能用longint类型变量正确保存的是（ ）
A) －32650 B) 4×1015 C) －108 D) 65537
9）浏览某一网站后，为了方便以后能快速地访问该网站，我们可以利用网络浏览器中的收藏夹功能来实现。收藏夹的主要功能是收藏（ ）
A）文档 B）网址 C）图片 D）音乐
10）信息表达的规范化，就是表达信息时要遵守一定的标准，有利于信息的交流。下列属于电子邮件的协议是( )
A）MP3 B）POP3 C）HTTP D）TCP/IP
11）“全国青少年信息学奥林匹克联赛”的英文缩写是（ ）
A) APIO B) CTSC C) NOI D) NOIP
12）软件的使用者，应遵守相关的法律规定，下列行为正确的是( )
A）使用盗版软件 B）复制传播正版软件
C）使用经授权的软件 D）自行研究和编制病毒程序
13）王董事长一回到家，第一件事情就是对电脑喊一声“开机”，该台电脑就乖乖地开机了。这种现象说明了该台电脑使用了( )
A）网络技术 B）语音识别技术 C）字符识别技术 D）自动关机技术
14）电子公告板亦称论坛，是网上学习讨论的一种很好的交流方式。电子公告板的英文简称是( )
A）BBS B）QQ C）MSN D）Email
15）下列分辨率的显示器显示出的图像，最清晰的是（ ）
A) 800*600 B) 640*480 C) 800*800 D) 1024*768
16）若我们说一个微机的CPU型号为PIII800，此处800确切指的是（ ）
A) CPU的知识产权编号 B) CPU内部的最大一级缓存
C) CPU的主时钟频率 D) 每秒执行800万条指令
17）当一个应用程序窗口被最小化后，该应用程序将（ ）
A) 继续在前台执行 B) 被终止执行 C) 被暂停执行 D) 转入后台执行
18）下列排序算法中，算法时间复杂度是O(n2)的算法是（ ）
A) 堆排序 B) 插入排序 C) 归并排序 D) 快速排序
19）如果我们把一棵二叉树的根节点称为第一层（根节点所在深度为1），那么一棵深度为k的二叉树中，最多可以包含的节点数是（ ）
A) 2k-1 B) 2*k C) 2k D) 2k-1
20）下列关于二叉树遍历的说法中，正确的是（ ）
A) 已知一棵二叉树的前序和后序遍历，可以唯一地确定一棵二叉树。
B) 已知一棵二叉树的后序遍历，可以唯一地确定一棵二叉树。
C) 已知一棵二叉树的前序和中序遍历，可以唯一地确定一棵二叉树。
D) 已知一棵二叉树的前序遍历，可以唯一地确定一棵二叉树。
二．问题求解：（3＋7＝10分）
1．海上航行时，每到晚上，大海中的轮船就通过安装在轮船上的一排探照灯来相互打招呼。每个探照灯都有“亮”和“灭”两种状态，这样通过一排探照灯（假定从左到右有序）的“亮”和“灭”的组合就可以表达很多约定的信息。现在一艘轮船上从左到右一共安排了10盏探照灯，那么这一排探照灯最多能表达的信息种类数是多少？
2．新田忌赛马。田忌有3匹马（奔跑速度分别是40、60、90），齐王有3匹马（速度分别是50、70、100），田忌的马和齐王的马逐对进行比赛，由于每次出场顺序由田忌确定，所以田忌通过巧妙的策略赢得了最终的胜利（比齐王多赢一场），具体对阵形式如下（按田忌马速度从小到大排列，对阵形式中左边为田忌马的速度，右边为齐王马的速度）：
40－100 60－50 90－70
现在田忌有8匹马（速度分别为10、20、30、40、50、60、70、80），齐王也有8匹马（速度分别为35、48、56、65、77、98、105、112），出场顺序仍由田忌来确定，问：田忌是否能找到一种出场顺序（回答“能”或者“不能”），使得田忌最终能赢得比赛（田忌赢的场次多于齐王）？如果回答“能”，请写出田忌胜的场次中，两匹马对阵的形式（格式仿照前面的例子书写，按照田忌马匹的速度从小到大书写）。
三．阅读程序并写出运行结果（7＋7＋8＋8＝30分。）：
1．
program test1;
var
x,y,s,tot:integer;
begin
readln(x,y);
x:=x+y;
y:=x+y;
s:=x+y;
writeln(s);
end.
输入：
10 20
输出：
2．
program test2;
var
x,y,i,j,code:integer;
t1,t2:string;
begin
x:=1024;
y:=32;
i:=x mod y;
j:=x div y;
str(i,t1);
str(j,t2);
writeln(t1+t2);
end.
输出：
3.
program test3;
var
a:array[1..10] of byte;
i,j,k,s,t:integer;
begin
s:=33;t:=1;
repeat
a[t]:=s mod 2;
s:=s div 2;
t:=t+1;
k:=s;
until k=0;
for i:=t-1 downto 1 do write(a[i]);
end.
输出：
4．
Program test4;
Const error=1e-8;
Var
sum:array[0..2,0..100]of double;
n:array[1..2]of Longint;
i,j,k,x,y:Longint;
c:double;
Function find(t:Longint):Longint;
Var
i:Longint;
min:double;
Begin
min:=1e15;
For i:=1 to n[t] do
If (abs(sum[t,i-1]-sum[t,n[t]]+sum[t,i]))+errormin:=abs(sum[t,i-1]-sum[t,n[t]]+sum[t,i]);
find:=i;
End;
End;
Begin
read(n[1],n[2]);
For i:=1 to n[1] do
For j:=1 to n[2] do Begin
read(c);
sum[1,i]:=sum[1,i]+c;
sum[2,j]:=sum[2,j]+c;
End;
For i:=1 to n[1] do sum[1,i]:=sum[1,i-1]+sum[1,i];
For i:=1 to n[2] do sum[2,i]:=sum[2,i-1]+sum[2,i];
x:=Find(1);
y:=Find(2);
writeln('Center= (',x,',',y,')');
End.
输入：
3 3
0.22 0.21 0.20
0.2 0.3 0.12
0.13 0.32 0.11
输出：
四．完善程序
（根据问题要求和已有程序，在空格处填入适当的语句或符号，使程序完整。本题30分）
1．【从小到大排序】（3＋3＋3＋3＝12分）
下列程序用来实现对输入的10个整数进行从小到大的排序，最后输出排序好的10个整数，输出时，每两个整数之间用一个空格分隔。
输入和输出的样例如下：
【样例输入】
5 6 8 7 3 2 1 4 9 10
【样例输出】
1 2 3 4 5 6 7 8 9 10
请完善下列程序：
program test5;
var
a:array[1..10] of integer;
i,j,t,k:integer;
begin
for i:=1 to 10 do ① ;
for i:=1 to 9 do
begin
② ;
for j:=i+1 to 10 do if a[t]>a[j] then ③ ;
if t<>i then begin ④ ;a[i]:=a[t];a[t]:=k;end;
end;
for i:=1 to 10 do write(a[i],' ');
end.
2．（最大连续子段和）给出一个数列（元素个数不超过100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为 4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8 时，输出16和7。
var
a: array[1..100] of integer;
n, i, ans, len, tmp, beg: integer;
begin
read(n);
for i := 1 to n do
read(a[i]);
tmp := 0;ans := 0;len := 0;
beg := ① ;
for i := 1 to n do
begin
if tmp + a[i] > ans then
begin
ans := tmp + a[i];
len := i - beg;
end
else if ( ② ) and (i - beg > len) then
len := i - beg;
if tmp + a[i] ③ then
begin
beg := ④ ;
tmp := 0;
end
else
⑤ ;
end;
writeln(ans, ' ', len);
end.