第十二届全国青少年信息学奥林匹克联赛初赛试题
（ 提高组 Pascal 语言 二小时完成 ）
（ECDEC ECBAB）
一、 单项选择题 （共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。
1. 在以下各项中。（ E ）不是CPU的组成部分。
A. 控制器 B. 运算器 C. 寄存器 D. ALU E. RAM
2. BIOS（基本输入输出系统）是一组固化在计算机内（ C ）上一个ROM芯片上的程序。 A. 控制器 B. CPU C. 主板 D. 内存条 E. 硬盘
3. 在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（ D ）。
A. 沃尔夫奖 B. 诺贝尔奖 C. 菲尔兹奖 D. 图灵奖 E. 南丁格尔奖
4．在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（ E ）。
A. 没有区别 B. 有一些区别，但机器处理速度很快，可忽略不计 C. 按行读的方式要高一些 D. 按列读的方式要高一些 E. 取决于数组的存储方式。
5．在Pascal语言中，表达式 (21 xor 2)的值是（ C ） A. 441 B. 42 C.23 D.24 E.25
xor是异或操作，两者不同为1。 10101 xor 10=10111
6．在Pascal语言中，判断a不等于0且b不等于0的正确的条件表达式是（ E ）
A. not a=0 or not b=0 B. not((a=0)and(b=0)) C. not(a=0 and b=0) D. (a<>0)or(b<>0) E. (a<>0)and (b<>0)
7．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（ C ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5
8．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（ B ）。
A. 10 B. 11 C. 12 D. 13 E. 2 – 1
第 1 页 共 11 页
10
陈剑秋
1+2+4+……+2n=2n+1-1 11
2=2024，前面10层是满的，加最后一层，所以答案是11
9. 与十进制数1770.625 对应的八进制数是（ A ）。
A. 3352.5 B. 3350.5 C. 3352.1161 D. 3350.1151 E. 前4个答案都不对
小数的二进制转化：二进制转十进制，还是乘以2个若干次方累加，小数点后 第一位是2的－1次方，第二位是－2次方，依次类推。十进制转二进制，拿小 数部分乘以2，取整数个位上的数字，如果是1的话，要把乘积减去1，再不断 的乘以2，取个位上的数字。注意十进制转二进制可能无限循环的，如果这样的 话，题目会告诉你保留几位小数的。 此方法中的二改成八就行了。
10．将5个数的序列排序，不论原先的顺序如何，最少都可以通过（ B ）次比较，完成从小到大的排序。
A. 6 B. 7 C. 8 D. 9 E. 10
本题得分率极低，用任何一种经典的排序算法都是8次比较，实际本题就是针对5这个特例的一道“脑筋急转弯”题。
二、 不定项选择题 （共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。
(ABC AB C BC ABCD AD CD AB BD)
11. 设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（ ABC ）。 A. (A∧B)∨(C∧D)∨¬E B. ¬ (((A∧B)∨C)∧D∧E) C. A∧(B∨C∨D∨E) D. (A∧(B∨C)) ∧D∧E
12. (2010)16 + (32)8的结果是（ AB ）。 A. (8234) B. (202A)
1016C. (100000000110)2 D. (2042)16
13. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ C ）。
A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a
14. 已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ BC ） A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5
第 2 页 共 11 页
陈剑秋
根据答案来选，1是根，23是左子树，456是右子树。32和23都是可能的。右子树4是根，56分别是左右子树，不能是同一子树，因为它们在先序和后序中都是56。
15. 在下列各数据库系统软件中，以关系型数据库为主体结构的是（ ABCD ）。 A. ACCESS B. SQL Server C. Oracle D. Foxpro
关系型数据库就是二维表格
16.在下列各软件中，属于NOIP竞赛（复赛）推荐使用的语言环境有（ AD ）。 A. gcc/g++ B. Turbo Pascal C. Turbo C D. free pascal
17. 以下断电之后将不能保存数据的有（ CD ）。
A. 硬盘 B. ROM C. 显存 D. RAM
18. 在下列关于计算机语言的说法中，正确的有（ AB ）。 A. Pascal和C都是编译执行的高级语言
B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C. C++是历史上的第一个支持面向对象的计算机语言
D. 高级语言比汇编语言更高级，是因为它的程序的运行效率更高
19. 在下列关于计算机算法的说法中，正确的有（ BD ）。 A. 一个正确的算法至少要有一个输入
B. 算法的改进，在很大程度上推动了计算机科学与技术的进步
C. 判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间
D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法 20. 在下列关于青少年信息学竞赛的说法中，你赞成的是（ ）（本题不回答为0分，答题一律满分）。
A. 举行信息学竞赛的目的，是为了带动广大青少年学科学、爱科学，为造就一大批优秀的计算机科学与技术人才奠定良好的基础
B. 如果竞赛优胜者不能直接保送上大学，我今后就不再参与这项活动了 C. 准备竞赛无非要靠题海战术，为了取得好成绩，就得拼时间、拼体力
D. 为了取得好成绩，不光要看智力因素，还要看非智力因素。优秀选手应该有坚韧不拔的意志，有严谨求实的作风，既要努力奋进，又要胜不骄败不馁
三．问题求解（共2题，每题5分，共计10分）
1．将2006个人分成若干不相交的子集，每个子集至少有3个人，并且： （1）在每个子集中，没有人认识该子集的所有人。 （2）同一子集的任何3个人中，至少有2个人互不认识。
（3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。 则满足上述条件的子集最多能有___________个？
第 3 页 共 11 页
陈剑秋
答案：无解
本题改编自一道数学竞赛题，原题是2005，答案是401。现在改成2006，实际是不存在。每个子集只能是一个五边形，没有其他形状。
2．将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）。设n=10，则该正三角形的不同的通路的总数为_____________。
答案：9!
考虑第i层上一点P，实际它所有的走法，关键是看它从上一层哪个位置走上来的，如果从这个走下来，下来就走到P的话，只能是唯一的走法。所以f(i)=(i-1)*f(i-1),f(2)=1.所以f(i)=(i-1)!.
四．阅读程序写结果（共4题，每题8分，共计32分）
1. Program ex401; var
u,v:array[0..3] of integer; i,x,y:integer; begin
x:=10; y:=10; for i:=0 to 3 do read(u[i]);
v[0]:=(u[0]+u[1]+u[2]+u[3]) div 7; v[1]:=u[0] div ((u[1]-u[2]) div u[3]); v[2]:=u[0]*u[1] div u[2]*u[3]; v[3]:=v[0]*v[1];
x:=(v[0]+v[1]+2)-u[(v[3]+3) mod 4]; if (x>10) then
y:=y+(v[2]*100-v[3]) div (u[u[0] mod 3]*5) else
y:=y+20+(v[2]*100-v[3]) div (u[v[0] mod 3]*5); writeln (x,',',y);
end. {*注：本例中，给定的输入数据可以避免分母为0或下标越界。 )
第 4 页 共 11 页
陈剑秋
输入：9 3 9 4
输出：_______________
答案：-13 57
2.Program ex402; const
m:array[0..4] of integer=(2,3,5,7,13); var
i,j:integer; t: longint; begin
for i:=0 to 4 do begin t:=1;
for j:=1 to m[i]-1 do t:=t*2; t:=(t*2-1)*t; write (t,' '); end; writeln; end.
输出:____________________
答案：6 28 496 8128 33550336
3. Program ex403; Const NN=7; Type
Arr1=array[0..30] of char; var
s:arr1;
k,p:integer;
function fun1(s:arr1; a:char;n:integer):integer; var
j:integer; begin j:=n;
while (a Function fun2(s:arr1; a:char; n:integer):integer; var j:integer; begin j:=1; 第 5 页 共 11 页 陈剑秋 while (a>s[j])and(j s[k]:=chr(ord('A')+2*k+1); k:=fun1(s,'M',NN)+fun2(s,'M',NN); writeln(k); end. 输出：_____________ 答案：11 首先得到s的值对应的ASCII码是[68,70,72,74,76,78,80]，M的ASCII码是77 fun1是在s中找恰好比M的小的数的位置，5。fun2是在s中找恰好比M大的数的位置，6。 K＝5＋6 4. program ex404; var x,x2:longint; procedure digit(n,m:longint); var n2:integer; begin if(m>0) then begin n2:=n mod 10; write(n2:2); if(m>1) then digit(n div 10,m div 10); n2:=n mod 10; write(n2:2); end; end; begin writeln('Input a number:'); readln(x); x2:=1; while(x2 输出：______________________________ 答案：6 2 5 4 3 7 9 9 7 3 4 5 2 6 第 6 页 共 11 页 陈剑秋 基本递归程序的阅读，方法参看我以前的试题分析。 06年阅读程序总体十分简单，不拿满分可惜了。 五．完善程序 (前5空，每空2分，后6空，每空3分，共28分) 1．（选排列）下面程序的功能是利用递归方法生成从1到n(n<10)的n个数中取k(1<=k<=n)个数的全部可能的排列（不一定按升序输出）。例如，当n=3，k=2时，应该输出（每行输出5个排列）： 12 13 21 23 32 31 程序： Program ex501; Var i,n,k:integer; a:array[1..10] of integer; count:longint; Procedure perm2(j:integer); var i,p,t:integer; begin if ① then begin for i:=k to n do begin inc(count); t:=a[k]; a[k]:=a[i]; a[i]:=t; for ② do write(a[p]:1); write(' '); t:=a[k];a[k]:=a[i];a[i]:=t; if (count mod 5=0) then writeln; end; exit; end; for i:=j to n do begin t:=a[j];a[j]:=a[i];a[i]:=t; ③ ; t:=a[j]; ④ ; end end; begin writeln('Entry n,k (k<=n):'); read(n,k); count:=0; for i:=1 to n do a[i]:=i; ⑤ ; 第 7 页 共 11 页 陈剑秋 end. 答案： （1）j=k （或k=j） （2）p:=1 to k （3）perm2(j+1) （4）a[j]:=a[i];a[i]:=t （5）perm2(1) 分析： 本题是一个基本的利用递归来生成排列的算法。递归生成p(n,k)，可以看成1号位依次放1到n，后面是一个p(n-1,k-1)的子问题。 Procedure perm2(j:integer); var i,p,t:integer; begin if _____j=k_______ then （递归搜索到第k层，就是前k个数都得到了） begin for i:=k to n do begin inc(count); （总情况数加1，现在得到一个排列了） t:=a[k]; a[k]:=a[i]; a[i]:=t; （枚举第k位的数字） for ____ p:=1 to k _____ do write(a[p]:1); （输出排列） write(' '); t:=a[k];a[k]:=a[i];a[i]:=t; （回溯，把刚才换来的数字换回去） if (count mod 5=0) then writeln; end; exit; end; for i:=j to n do begin t:=a[j];a[j]:=a[i];a[i]:=t; (把当前数字依次和后面的换) _____ perm2(j+1)_____ ; （递归搜索下一个数字） t:=a[j]; ______ a[j]:=a[i];a[i]:=t ______ ; （回溯，把刚才换来的数字换回去） end end; begin writeln('Entry n,k (k<=n):'); read(n,k); count:=0; for i:=1 to n do a[i]:=i; _____ perm2(1)_____ ; end. 2．（TSP问题的交叉算子）TSP问题(Traveling Salesman Problem)描述如下：给定n个城市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环路，每个城市恰好经过一次，求使总代价达到最小的一条环路。 第 8 页 共 11 页 陈剑秋 遗传算法是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法之一是1到n这n个数字的一个排列，每个数字为一个城市的编号。例如当n=5时，“3 4 2 1 5”表示该方案实施的路线为3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作，产生两个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下： (1)选定中间一段作为互换段，该段的起止下标为t1，t2，随机生成t1，t2后，互换两段。 (2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：(2.1) 将两个互换段中，共同的数字标记为0，表示已处理完。 (2.2) 将两个互换段中其余数字标记为1，按顺序将互换段外重复的数字进行替换。 例如：n=12，两个个体分别是： a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11 a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9 t1=5，t2=8。上述每一行中，两个星号间的部分为互换段。假定数组的下标从1开始，互换后有： a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11 a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9 然后，将数字6,7对应的项标记为0，星号内数字2,9,10,11对应的项标记为1，并且按顺序对应关系为: 10<->2 ，11<->9。于是，将a1[9]=10替换为a1[9]=2，将a2[2]=2替换为a2[2]=10，类似再做第2组替换。这样处理后，就得到了两个新个体： a1: 1 3 5 4 6 7 10 11 2 12 8 9 a2: 3 10 1 12 2 6 7 9 8 5 4 11 （3）输出两个新个体的编码。 程序： program ex502; type arr1=array[1..20] of integer; var a1,a2,kz1,kz2:arr1; n,k,t1,t2:integer; function rand1(k:integer):integer; var t:integer; begin t:=0; while (t<2) or(t>k) do t:=random(k+1)-2; rand1:=t; end; procedure read1(var a:arr1;m:integer); {读入数组元素a[1]至a[m]，a[0]=0，略。} procedure wrt1(var a:arr1;m:integer); {输出数组元素a[1]至a[m]，略。} procedure cross(var a1,a2:arr1;t1, t2,n:integer); var i,j,t,kj:integer; begin for i:=t1 to t2 do begin 第 9 页 共 11 页 陈剑秋 t:=a1[i]; ① ; end; for i:=1 to n do if (i kz1[i]:=-1;kz2[i]:=-1; end else begin ② ; end; for i:=t1 to t2 do for j:=t1 to t2 do if(a1[i]=a2[j]) then begin ③ ; break; end; for i:=t1 to t2 do if(kz1[i]=1) then begin for j:=t1 to t2 do if(kz2[j]=1) then begin kj:=j; break; end; for j:=1 to n do if ④ then begin a1[j]:=a2[kj];break; end; for j:=1 to n do if ⑤ then begin a2[j]:=a1[i]; break; end; kz1[i]:=0;kz2[kj]:=0; end; end; begin writeln('input (n>5):'); readln(n); writeln('input array 1:'); read1(a1,n); writeln('input array 2:'); read1(a2,n); t1:=rand1(n-1); repeat t2:=rand1(n-1); until(t1<>t2); if(t1>t2) then begin k:=t1; t1:=t2; t2:=k; end; ⑥ ; wrt1(a1,n); wrt1(a2,n); end. 答案： (1)a1[i]:=a2[i];a2[i]:=t (2)kz1[i]:=1;kz2[i]:=1; 第 10 页 共 11 页 陈剑秋 (3)kz1[i]:=0;kz2[j]:=0; (4)(a1[j]=a1[i])and(kz1[j]=-1) (5)(a2[j]=a2[kj])and(kz2[j]=-1) (6)cross(a1,a2,t1,t2,n) 算法实在简单，看明白它怎么做就行了。实在没啥好写的，就解释下主要的cross过程吧。 procedure cross(var a1,a2:arr1;t1, t2,n:integer); （交换a1、a2数组从t1到t2位置的数字，并调整） begin for i:=t1 to t2 do begin t:=a1[i]; a1[i]:=a2[i];a2[i]:=t ; （交换a1、a2数组从t1到t2位置的数字） end; for i:=1 to n do if (i kz1[i]:=-1;kz2[i]:=-1; （两数组不需要交换的标－1） end else begin kz1[i]:=1;kz2[i]:=1 ; end; （需要交换的开始都标1） for i:=t1 to t2 do for j:=t1 to t2 do if(a1[i]=a2[j]) then begin kz1[i]:=0;kz2[j]:=0 ; break; end; （交换后成功，不要调整的标0） for i:=t1 to t2 do （开始调整） if(kz1[i]=1) then （需要调整的） begin for j:=t1 to t2 do if(kz2[j]=1) then （在另一个数组中也找个需要调整的） begin kj:=j; break; end; for j:=1 to n do if (a1[j]=a1[i])and(kz1[j]=-1) then （在a1中找当前需要调整的，而且是在没交换位置重复出现的） begin a1[j]:=a2[kj];break; end; for j:=1 to n do if (a2[j]=a2[kj])and(kz2[j]=-1) then （对称结构，在a2中找当前需要调整的，而且是在没交换位置重复出现的） begin a2[j]:=a1[i]; break; end; kz1[i]:=0;kz2[kj]:=0; （这两位置标为调整后的） end; end; 第 11 页 共 11 页
因篇幅问题不能全部显示，请点此查看更多更全内容