|
第三届全国青少年信息学奥林匹克分区联赛初赛试题及答案(提高组)
第三届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题(提高组）
（PASCAL语言 竞赛用时：2小时）
一、基础部分
（1）WPS是属于________类的软件；FOXBASE是属于_______类的软件。 用FOXBASE的命令：.CREAT GZB，在磁盘中生成的是_______文件。
（2）在MS DOS的根目录中，有如下文件： TIME.EXE TIME.COM TIME.BAT 试问：c:\> TIME<回车> 执行的是什么命令？
（3）已知ASCII码表中的大写字母后有6个其他字符，接着便是小写字母。现已知：A 字母的ASCII码为(41)16{表示16进制数41}，试写出如下字母用十进制表示的ASCII 码：
G → ( )10 b → ( )10 t → ( )10
（4）设数组A[10..100，20..100]以行优先的方式顺序存贮，每个元素占4个字节，且已知 A[10，20]的地址为1000，则A[50，90]的地址是_____________。
（5）一个汉字的机内码目前常用二个字节来表示：第一字节是区位码的区号加(160)10；第 二个字节是区位码的位码加(160)10 已知：汉字“却”的区位码是4020，试写出机内码两个字节的二进制的代码：
（6）下图中用点表示城市，点与点之间的联线表示城市间的道路：
 试问：①能否找出一条从A城市出发，经过图中所有道路一次后又回到出发点的通 路来？ ②能否从A出发，找出去每个城市且只去一次的通路来？若能，则写出通路； 否则说明理由。 （7）为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀{运算符在前， 如X/Y写为/XY}和后缀{运算符在后，如X/Y写为XY/}的表达式。 在这样的表示中可以不用括号即可确定求值的顺序，如： (P+Q)*(R-S) →*+PQ-RS或 → PQ+RS-* ①试将下面的表达式改写成前缀与后缀的表示形式： (a) A+B*C/D (b) A-C*D+B^E ②试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示： +△A*B△C {前缀式中△表示一元运算符取负号，如△A表示（-A）
（8）一个将角编了号的正三角形可以进行如下二种运动： (a)沿过顶点1的高h翻转180°，我们将这个运动用字母a来表示：
(b)沿过三角形的外心，垂直于三角形所在平面的有向轴L（注意：三角形翻转时L 轴也随着翻转的），按右手法则旋转120°（右手法则是指用右手大拇指指向L轴的 方向，由其余四指决定旋转方向的法则），我们将这样的运动用字母b来表示：
如果将a，b作为运算对象，并将两个运动连续进行看作是一种运算（这里不妨也称 为乘法），则对图一的三角形而言，bb的结果便成为：
若将运动前后的三角形状态简称为元素，那么三角形状态就可与运动的表达式关联起 来。据此，请回答如下问题： ①从图一的三角形的原始状态出发，可以运动出多少种不同的状态的三角形，试写出 最简单的运算表达式（借助于a，b与乘法运算）： ②这样定义的乘法运算是否符合交换律与结合律？ ③如果将从三角形的某种状态运动回到原始状态称之为该元素的逆元素，例如：
∴ bb的逆元素为b，可表示为(bb)-1=b
试求：(1)a-1= (2)(ab)-1=
(3)((aa)a)-1= (4)b-1=
二、根据题意，将以下程序补充完整
1. [问题描述]：一个正整数（非素数）可以表示成它的因子（1与其本身除外）的乘积。
例如：12有因子2，2，3，4，6，所以可表示为：
12=2*2*3=4*3=2*6
给出任一个整数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[i，1]表示因子；a[i，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
readln(n); for i:=i 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;
while ⑥ do
begin
k:=j;
while b[k]=a[k,2] 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:=m*a[i,1];
if m=n then write(a[i,1])
else begin
write(a[i,1],'*');
c[i]:=c[i]-1;
end;
end;
writeln(')');
end
end
end.
2. [问题描述]：给出一个凸多边形，可以取得若干个内接三角形，同时约定内接三角形必 须有一条边（仅能有一条边）与凸多边形的边相重合，例如：下面的5边形中，可能有 的内接三角形有5种：
问题：当依次给出凸多边形的每个顶点的2个坐标之后，找出一个面积最大的内接三角
形，输出该三角形的面积与三个顶点的坐标。
[算法说明]：凸多边形的每个顶点用一对坐标(x,y)表示；
用数组p:array[1..2*n] of point; 存贮输入的顶点坐标；
同时编制一个由三角形的三个顶点计算其面积的函数sea。
[程序清单]：program exp5(input,output);
const n=6;
type point=record x,y:real end;
var p :array[1..2*n] of point;
i,j :integer;
q1,q2,q3 :point;
smax :real;
function sea(p1,p2,p3:point):real;
var s1,s2,s3,p4:real;
begin
s1:=sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
s2:=sqrt((p1.x-p3.x)*(p1.x-p3.x)+(p1.y-p3.y)*(p1.y-p3.y));
s3:=sqrt((p2.x-p3.x)*(p2.x-p3.x)+(p2.y-p3.y)*(p2.y-p3.y));
p4:= ① ; sea:=sqrt(p4*(p4-s1)*(p4-s2)*(p4-s3));
end;
begin
for i:=1 to n do readln(p[i].x,p[i].y); smax:=0;
for i:=1 to n-1 do ②
for i:=1 to n do
for j:= ③ do
if ④ then
begin
smax:=sea(p[i],p[i+1],p[j]);
q1:=p[i]; q2:= ⑤ ; q3:=p[j]
end;
writeln(smax,q1.x,q1.y,q2.x,q2.y,q3.x,q3.y)
end.
3. [问题描述]：拼图形：边长为1的正方形面积为1，从边长为1的正方形出发可以用2个
边长为1的正方形拼成面积为2的长方形：
同时约定：
1．边长对应相等的长方形被认为是相同的；（所以下边的两个面积为2的长方形只看作
一个长方形）；
2．长度相等的边才能拼接，且两个边必须重合。从面积为2的长方形出发，用2个面积为2的长方形可拼出面积为4的长方形（包括正方形），拼法如下：
同样再从面积为4的长方形（包括正方形）出发，可以拼成面积为8的长方形，拼法如
下：
可以按上面的方法继续拼下去。
问题：输入一个数N，输出面积不超过N的所有可能拼法。例如：当N=20时，
输出：(1,1),(2,1),(4,2),(8,2),(16,3)即面积为1的拼法1种，面积为2的拼法1种，面积为
4的拼法2种，面积为8的拼法2种，面积为16的拼法3种。
[算法说明]：矩形可以用三个数x,y,s来表示，其中x,y表示边长，s表示面积，并用数组
G[1..100,1..3]表示图形。
当给出n之后，可能拼接的次数为r满足：2r<=N<2r+1(不包括面积为1的拼法)；
用数组b[1..100]记录各种面积可能出现的拼法。
[程序清单]：program exp8(input,output);
type g=record x,y,z:integer end;
var g1 :array[1..100] of g;
i,j,n,s1,jj,j1,j2,i1 :integer;
b :array[1..100] of integer;
gw :g;
Function eq(gk:g):boolean;
var jeq:integer; p:boolean;
begin
p:=true; jeq:=1;
while (p and (jeq<=j)) do
if ((gk.x=g1[jeq].x) and (gk.y=g1[jeq].y))
or ((gk.x=g1[jeq].y) and (gk.y=g1[jeq].x))
then p:=false else jeq:=jeq+1;
eq:=p
end;
Begin
readln(n); n:=n+1; s1:=1; jj:=1;
while ① do
begin ② ; jj:=jj+1 end;
③ ; j1:=1; j:=1;
g1[j].x:=1; g1[j].y:=1; g1[j].z:=1;
for i:=2 to jj do
begin
j2:=j;
for i1:=j1 to j2 do
begin
gw.x:=g1[i1].x*2; gw.y:=g1[i1].y; gw.z:=g1[i1].z*2;
if ④ then begin
j:=j+1; g1[j]:=gw
end;
gw.x:=g1[i1].x; ⑤
if eq(gw) then begin
j:=j+1; ⑥
end;
end;
j1:=j2+1
end;
for i:=1 to n do b[i]:=0;
for i:=1 to j do ⑦
for i:=1 to n do if ⑧ then write('(',i,',',b[i],')');
End.
第三届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
（高中组）
参考答案
一、 基础部分：共44分
（1） 本题共3分。（1+1+1）：
①文字处理 ②数据库管理系统（DBMS） ③GZB.DBF
（2） 本题共2分。执行的是： 内部命令TIME 。
（3） 本题共3分。如下字母用十进制表示的ASCII码为：
G→（71）10 b→（98）10 t→（116）10
（4） 本题共2分。A[50，90]的地址是： 14240 。
（5） 本题共4分。两他字节二进制代码为：11001000，10110100
（6） 本题共6分（2+4）。根据问题，回答：
① 能。例如A→D→C→E→A→F→C→B→A
② 不能。本题的回答要点如下：要到达D，E，F，B四个点之一，必须由A，C出发才可，因为A，C只可能出发一次，所以这样的通路不存在。
（7） 本题共8分（1+1+1+1+2+2）。
①<a>前缀形式为：+A/*BCD；后缀形式为：ABC*D/+
<b>前缀形式为：+-A*CD∧BE；后缀形式为：ACD*-BE∧+
② 中缀形式为（-A）+B*（-C）；后缀形式为：A△BC△*+
（8） 本题共16分（6+2+8）
① 可有如下6种情况：
（1）b （2）bb或b2或aba （3）bbb或b3或aa
（4）a （5）ab或b2a或bba （6）abb或ab2或ba
② 符合结合律而不符合交换律
③（1）a-1=a （2）(ab)-1=bba （3）((aa)a)-1=a （4）b-1=bb
二、根据题目要求，补充完善以下程序：（共56分）
PASCAL 语言 BASIC 语言
（1）共20分（2+2+2+2+2++4+3+3分）
① A[0,1]:=1 40 A(0,1):=1
② S:=S+1 90 S=S+1
③ S>0 100 S=0
④ A[J,1]:=i 110 A[J,1]=i
⑤ S 110 S
⑥ B[K]=A[K,2] 165 B[k]=A[K,2]
⑦ K+1 TO J 180 K+1 TO J
⑧ S：=S*A[i，1] 215 S=S*A(i,1)
（2）共14分（4+2+3+3+2分） (2+2+3+4+3分)
① (S1+S2+S3)/2 40 g(n+i,1)=g(i,1)
② P[ n+i]:=P[i]; 50 g(n+i,2)=g(i,2)
③ i+3 TO i+2+n-4 80 i+3 TO i+n-2
④ Smax<Sea(P[i]. P[i+1], P[j] 120 (S1+S2+S3)/2
⑤ P[i+1] 140 S<SMAX
（3）共22分（3+2+2+3+4+2+3+3分）
① S1<N 40 S<=N
② S1:=S1+S1 40 S=S+S
③ JJ:=JJ-1 50 JJ=JJ-1
| 
