第1个回答 2006-10-11
click here
2006年南海区青少年信息学奥林匹克竞赛初赛试题
（高中组，两小时完成）
◆◆请将正确答案在答题卷上填写，在本试题卷上答题无效◆◆
一、 选择填空
(1—10小题为单选题，11—20小题为多选题，多选题多选、少选、错选均不能得分。每题1.5分，共30分)
1、线性表若采用链表存贮结构,要求内存中可用存贮单元地址（ ）
A.必须连续 B.部分地址必须连续 C.一定不连续 D.连续不连续均可
2、计算机中可以采用16*16、32*32等数字化点阵字模，字模中的每一个点在存储器中用—个二进制位(bit)存储。那么，—个16x16点阵的汉字在计算机中需要（ ）字节的存储空间。
A.16 B.24 C.32 D.48 E.56
3、关键路径是指AOE(Activity On Edge)网中（ ）。
A.最长的回路 B.最短的回路 C.从源点到汇点(结束顶点)的最长路径
D.从源点到汇点(结束顶点)的最短路径
E.最短路径的条数
4、设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ ）。
A．2 B．3 C．4 D．5 E.6
5、一个具有767个结点的完全二叉树，其叶子结点个数为（ ）。
A.383 B.384 C.385 D.386 E.387
6、若一个具有n个结点k条边的非连通无向图是一个森林(n>k),则该森林中必有（ ）棵树。
A.k B.n C.n-k D.n+k E.n+k-1
7、若G是—个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有（ ）个顶点。
A.11 B.10 C.9 D.8 E.7
8、将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行关键字比较（ ）次。
A. I B. n-1 C. n D. 2n E.n-I
9、网络中DNS是指（ ）
A．域名服务器 B．数据库名称系统 C．网络数据库
D．数据传送系统 E．数据服务器
10．显示器的主要参数之一是分辨率，其含义指的是（ ）。
A.显示器可分辨的颜色数 B. 可显示不同颜色的总数
C.同一幅画面允许显示不同颜色的最大数目
D.显示屏幕的水平和垂直扫描频率
E. 显示屏幕上光栅的列数和行数
以下为不定项选择题：（共10题，每题1.5分，共计15分。多选或少选均不得分）
11、以下序列中不符合堆定义的是（ ）。
A．(102，87，100，79，82，62，84，42，22，12，68)
B．(102，100，87，84，82，79，68，62，42，22，12)
C．(12，22，42，62，68，79，82，84，87，100，102)
D．(102，87，42，79，82，62，68，100，84，12，22)
E．（102，87，42，86，82，62，68，79，84，12，22）
12、下面描述用多维数组表示的数据结构的语句中，正确的是( )。
A．每个元素都必须一样 B．各维的下标范围必须一样
C．数组在内存中的地址是连续的 D．数组是随机存取的数据结构
E. 其他形式的数组都是在一维数组的基础上衍生出来的
13、下列逻辑运算正确的是（ ）。
A．A·（A + B ）= A B．A +（A·B）= A
C．A·（B + C ）= A·B + A·C D．A +（B·C）=（A + B）·（A + C）
E． A+1=A
14、Linux操作系统的发展非常迅猛，这与Linux具有的良好特性是分不开的。Linux包含了Unix的全部功能和特性，以下是linux的主要特征的有（ ）。
A. 开放性、设备独立性 B. 多用户多任务 C.良好的用户界面
D. 提供了丰富的网络功能 E. 可靠的系统安全，良好的可移植性
15、计算机系统总线上传送的信号有（ ）。
A．地址信号 B．邮件标识 C．数据信号 D．应答密码 E．控制信号
16、计算机中的数有浮点数和定点数两种，其中用浮点数表示的数，通常由( )组成。
A．指数 B．基数 C．阶码 D．整数 E．尾数
17、下列哪个(些)不是操作系统软件的名字？（ ）
A．WindowsXP B．Windows NT C．DOS D．Linux E．Foxpro
18、如果A的 ASCII是65,则Z的ASCII码为（ ）。
A．(132)8 B．(91)10 C．(1011101)2 D．(5B)16 E．(264)4
19、下列哪些是计算机网络的协议？（ ）
A．TCP/IP B．IPX/SPX C．NetBEUI D．E-mail E．WWW
20、在PASCAL中，下列属于动态数据类型的是（ ）
A．布尔型 B．指针类型 C．记录类型 D．集合类型 E．整型
二．问题求解 （每题5分，共10分）
1、观察下面数的规律；第22行起第一个数是（ ）。
2、下式中每个汉字表示1—7中的一个数字，不同的汉字代表不同的数字，已知:
我2+喜2+欢2=信2+息2+学2，那么信+息+学=（ ）。
三．读程序写结果（每题8分，共32分）
1、program p1;var m,n:integer;function f(m,n:integer):integer;begin if m*n=0 then f:=m+n+1 else f:=f(m-1,f(m,n-1));end;begin read(m,n); write(f(m,n));end.(输入：3 2) 2、program p2;const n=8;var I,j:integer; c:array[0..10] of char; temp:char;beginfor I:=1 to n do read(c[I]);for I:=2 to n dobegin temp:=c[I];j:=I-1; while (temp>c[j]) and (j>0) do begin c[j+1]:=c[j];j:=j-1;end; c[j+1]:=temp; end;for I:=1 to n do write(c[I]);writelnend.(输入：xinxixue
3、program GZ33; var a:array[1..13] of boolean; i,t,s,k,p:integer; begin for i:=1 to 13 do a[i]:=true; i:=1;t:=0;s:=2;p:=0;k:=0; repeat while p<>I do begin k:=k+1; if k>13 then k:=1; if a[k] then p:=p+1; end; a[k]:=false; t:=t+1; i:=i+s;s:=s+1; until t=8; write(k:6); readln; end. 4、program p4;const m=10;var i,j,k,n:integer; c:array [1..m,1..m] of char;begin n:=6; i:=1; j:=1;for k:=1 to n*(n+1) div 2 dobegin c[i,j]:=chr(64+k); if odd(j) then if i=n+1-j then begin i:=i-1; j:=j+1 end else i:=i+1 else if i=1 then j:=j+1 else i:=i-1end;for i:=1 to n do begin for j:=1 to n+1-i do write(c[i,j]:3); writeln end;end.
四、完善程序 (第3小题第③个 为4分,其它每空3分，共28分)
1、用高精度计算出S=1!+2!+3!+……n!(n≤)，其中“ ！”表示阶乘。输入正整数N，输出计算结果S。
program p5;
const maxlen=100;
var i,j,n:integer;
sum,fac:array[1..maxlen+1] of integer;
begin
write('input n:');
readln(n);
for i:=1 to maxlen do sum[i]:=0;
for i:=1 to maxlen do fac[i]:=0;
fac[1]:=1;
for i:=1 to n do
begin
for j:=1 to maxlen do ① ;
for j:=1 to maxlen do
begin
fac[j+1]:=fac[j+1]+fac[j] div 10;
② ;
end;
for j:=1 to maxlen do ③ ;
for j:=1 to maxlen do
begin
sum[j+1]:=sum[j+1]+sum[j] div 10;
sum[j]:=sum[j] mod 10
end;
end;
i:=maxlen;
while sum[i]=0 do i:=i-1;
write('s=');
for j:=i downto 1 do write(sum[j]);
writeln
end.
2、【问题描述】
有n种基本物质（n≤10），分别记为P1，P2，……，Pn，用n种基本物质构造物质，这些物品使用在k个不同地区（k≤20），每个地区对物品提出自己的要求，这些要求用一个n位的数表示：a1a2……an，其中：
ai = 1表示所需物质中必须有第i种基本物质
= -1表示所需物质中必须不能有第i种基本物质
= 0无所谓
【问题求解】
当k个不同要求给出之后，给出一种方案，指出哪些物质被使用，哪些物质不被使用。
【程序说明】数组 b[1],b[2]……b[n] 表示某种物质
a[1..k,1..n] 记录k个地区对物品的要求，其中：
a[i,j]=1 表示第i个地区对第j种物品是需要的
a[i,j]=0 表示第i个地区对第j种物品是无所谓的
a[i,j]= -1 表示第i个地区对第j种物品是不需要的
【程序】
program p6;
var
i,j,k,n : integer ;
p : boolean ;
b : array[0..20] of 0..1 ;
a : array[1..20,1..10] of integer ;
begin
readln(n,k);
for i:=1 to k do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
for i:=0 to n do b[i]:=0;
p:=true;
while ① do
begin
j:=n;
while b[j]=1 do j:=j-1;
②
for i:=j+1 to n do b[i]:=0;
③
for i:=1 to k do
for j:=1 to n do
if (a[i,j]=1) and (b[j]=0) or (a[i,j]=-1) and (b[j]=1)
then p:=true;
end;
if p
then writeln(‘Can not find！’)
else for i:=1 to n do
if (b[i]=1) then writeln (‘matter’,i,’need’)
else writeln(‘matter’,i,’not need’);
end.
3、【问题描述】
设有n个（n=2m ）选手的循环比赛，要求每一位选手都要与其他n-1位选手比赛一次。每名选手每天赛一场，循环赛共进行n-1天。
【问题求解】
编程排出比赛时间表。
第一天 第二天 ...... 第n-1天
1
2
......
n
【算法提示】
我们先从m=1即只有两个选手的情况来看，显然可得到以下的安排表矩阵：
由于各种情况性质一致，只是规模不同，参照这一矩阵，可知，对于不同的选手数量所组成的安排表矩阵，若横竖等分为四块时，对角的两块应是相等的，即：
例如，当m=2时，即有4位选手参赛时，根据上述规律可得到以下安排表矩阵：
【程序】
program gZP43;
var n,m,i,j,k,t,t1:integer;
a:array[1..100,1..100] of integer;
begin
readln(m);n:=1;
for i:=1 to m do n:=n*2;
for i:=1 to n do ① ; {矩阵第一行按自然序列排列}
t1:=1;
for k:=1 to m do
begin
t1:=t1*2;
for t:=1 to (n div t1) do {对于k，划分为n/2k个矩阵，用t记录}
for i:=(t1 div 2 + 1) to t1 do {每个矩阵规模为2k*2k}
for j:= ② to t1 do
begin {由两个已知 2k-1*2k-1 矩阵，定义当前的2k*2k 矩阵t}
a[i,j+t1*(t-1)]:=a[i-(t1 div 2),j+t1*(t-1)-(t1 div 2)];
a[i,j+t1*(t-1)-(t1 div 2)]:= ③
end;
end;
for i:=1 to n do begin for j:=1 to n do write(a[i,j]:3);writeln end;
end.