第3届信息学分区联赛普及组初赛试题

第三届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题（初中组）
（PASCAL 语言 竞赛用时：2小时）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
基础部分：
<1>我国先后自行研制成功“银河”系列的巨型计算机，其中：
“银河”于1983年问世，其运算速度为每秒___________次；
“银河Ⅱ”于1992年诞生，其运算速度为每秒__________次；
“银河Ⅲ”于1997年通过国家鉴定，其运算速度为每秒__________次。
<2>下列软件均属于操作系统的是:___________________
A. WPS 与 PC DOS B. Windows 与 Ms dos
C. Word 与 Windows D. Foxbase 与 Os/2
<3>在MS DOS 的根目录中，有如下文件：
TIME.EXE TIME.BAT
试问：C:\>TIME < 回车 > 执行的是什么命令？
<4>设数组A[10..100,20..100] 以行优先的方式顺序存储，每个元素占4个字节，且已知A[10，20]的地址为1000，则A[50，90]的地址是 。
<5>下面是一个求：1/1+1/2+2/3+3/5+5/8+8/13+13/21+21/32…前20项的和的程序段，试将程序补充完整：
s:=0 ;a:=1 ; b:=1 ;
for k:=1 to 10 do
begin
s:=____① ；A：= _ ②____；
S:= __ _③ ；
B:= _ ④ ；
END；
WRITELN（S）；
<6>一个汉字的机内码目前通常用二个字节来表示：第一个字节是区位码的区号加（160）10；第二个字节是区位码的位码加（160）10 。
已知：汉字“却”的区位码是4020，试写出机内码两个字节的二进制的代码：
<7>已知ASCⅡ码表中的大写字母后有6个其它字符，接着便是小写字母。现已知：A字母的ASCⅡ码为（41）16{ 表示16进制数41 }，试写出如下字母用十进制表示的ASCⅡ码：
G → （ ）10 b → ( )10 t → ( )10
<8>下图中用点表示城市，点与点之间的联系表示城市间的道路：
D 　 C
A 　 B
试问：
①能否找出一条从A城市出发，经过图中所有道路一次后又回到出发点的通路来？
②能否从A出发，找出去每个城市且只去一次的通路来？
若能，则写出通路，否则说明理由。
<9>为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀{运算符在前，如X/Y写为/XY} 和后缀 { 运算符在后，如X/Y写为XY/}的表达形式。
在这样的表示中可以不用括号即可确定求值的顺序，如：
（P+Q）*（R-S）→*+PQ-RS 或 → PQ + RS -*
试将下面的表达式改写成前缀与后缀的表示形式：
　　 A+B*C/D A-C*D+B∧E
　　② 试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示：
　　+△A *B△C {前缀式中△表示一元运算符取负号，如△A表示（-A）}
<10>一个将角编了号的正三角形可以绕着外心O（中心）逆时针旋转1200，如下图所示：
1 3
●0 ●0
2 3 1 2
图一 图二
如果将这一旋转用字母a 来表示，看作运算对象，同时用aa或a2 表示旋转1200后再旋转1200 ，也就是说将连续运动看作乘法运算，那么三角形状态（可简称为元素）即可与运动表达式关联起来，请回答：
如果将图一的原始三角形连续旋转1200N次，简单地表示为an （N为任意自然数），试求an 的值（指三角形旋转后的结果状态）；
　 ②　如果将下面的旋转看作是a的逆元素，记为a-1 ，则有a-1 = a2
试求：a-n
3 1
●0 ●0
1 2 2 3
图三
根据题意，补充完善以下程序：
1．[问题描述]：读入n个不相同且不为0的数(1<=n<=100)，不用排序，求出其中第r个大的数(1≤r≤n)，即有r-1个数比它大，其余的数都比它小。
例如：输入3，14，22，15，17，6，其中第3个大的数为15。
[算法说明]：以数组a[1..100]记录读入的n个数，并以0结束（0本身不是n个数中的数）。然后从第一个数开始，将它与其余的数进行比较并记录出比它大的数的个数（存于变量y中），若y=r-1时，得到所求结果：否则对下一个数进行同样的处理。
[程序清单]：program exp2(input,output)
Var r,i,j,k,x,y : integer;
a : array[1..100] of integer;
p : boolean;
Begin
j:=0;
readln(x);
while ① do
begin
② ;
a[j]:=x;
③
end;
readln(r); p:=true; i:=1;
while p do
begin
④ ; y:=0;
for k:=1 to j do
if xif ⑥ then begin
writeln(x);
p:=false
end
else i:=i+1
end
End.
2．[问题描述]：在进行正整数的除法运算时，可以通过减法来实现。
例如xy=Q..R（Q:商，R:余数）可通过下列的方式实现：
q:=0; r:=x;
while r>=y do begin r:=r-y; q:=q+1 end;
结果，商在q中，余数在r中。
[算法说明]：上面的算法有一个缺点，就是当x比较大、y比较小时，则运算的次数非常多，速度太慢。为提高速度，下面给出改进的算法：先找一个非常接近x的数w，且满足：w=y2k，y2 k-1<=x[程序清单]：program exp3(input,output)
var x,y,w,r,q:integer;
Begin
readln(x);
r:=x;
①
while w<=r do ②
q:=0;
while ③ do
begin
w:=w div 2;
④
if r>=w then begin
⑤ ;
R:= ⑥ ;
end;
end;
writeln(q, ‘…’, R);
End.
3．[问题描述]：一个正整数（非素数）可以表示成它的因子（1与其本身除外）的乘积。
例如：12有因子2，3，4，6，所以可表示为：
12=223=43=26
给出任一个正整数N，求出它所有的因子乘积的表达式（交换律得出的不同式子算同一种）。
[算法说明]：读入一个整数N，首先求出它的所有的因子以及每个因子可能的次数。
例如：整数48：
因子：2 3 4 6 8 12 16 24
次数：4 1 2 1 1 1 1 1
将上面的结果存入数组A:ARRAY[0..20,1..2]中。其中：A[ ,1]表示因子；A[ ,2]表示次数。
然后用简单回溯的方法求出所有可能的表示：
数组B[0..20]记录取数情况：c:array[0..20]工作单元。
[程序清单]：program exp4(input,output);
var a : array[0..20,1..2] of integer;
c,b : array[0..20] of integer;
n,m,I,j,s,k,l : integer;
Begin
WRITELN;readln(n);
for i:=1 to 20 do a[i,1]:=0;
① ; a[0..2]:=1; j:=0;
for i:=2 to n-1 do
begin
s:=0; m:=n;
while(m<>0) and (m mod i=0) do
begin
m:=m div i;
② ;
end;
if ③ then begin
j:=j+1; ④ ;
a[j,2]:= ⑤ ;
end
end;
for i:=0 to j do b[i]:=0;
whil b[0]=0 do
begin
k:=j;
while ⑥ do k:=k-1;
b[k]:=b[k]+1;
for L:= ⑦ do b[L]:=0;
s:=1;
for i:=1 to j do
if b[i]<>0 then for L:=1 to b[i] do
⑧ ;
if s=n then begin
for i:=1 to j do c[i]:=b[i];
WRITE(‘(‘); M:=1;
for i:=1 to j do
while(c[i]>0) and (M<>N) do
begin
M:=MA[i.1];
if M=N then write(a[i,j])
else begin
write(A[i,1],’’);
c[i]:=c[i]-1;
end;
end;
writeln(‘)’);
end
end
End.
E
F
a
aa