全国第七届青少年信息学奥林匹克竞赛分区联赛初赛试题 [2001年]

1. 中央处理器CPU能访问的最大存储器容量取决于( )

2. 计算机软件保护法是用来保护软件( )的

3. 64KB的存储器用十六进制表示，它的最大的地址码是( )

4. 在树型目录结构中，不允许两个文件名相同主要指的是( )

5. 下列设备哪一项不是计算机输入设备( )

6. 在计算机硬件系统中，cache是( )存储器

7. 若我们说一个微机的CPU是用的PII300，此处的300确切指的是( )

8. Email邮件本质上是一个( )

9. 2KB的内存能存储( )个汉字的机内码

10. 以下对Windows的叙述中，正确的是( )

11. 运算式(2047)10-(3FF)16+(2000)8的结果是( )

12. TCP/IP协议共有( )层协议

13. 若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是( )

14. 计算机病毒是( )

15. 下面关于算法的错误说法是( )

16. [x]补码=10011000，其原码为( )

17. 以下哪一个不是栈的基本运算( )

18. 在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为( )

19. 一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点

20. 无向图G=(V，E)，其中V={a,b,c,d,e,f} E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)} 对该图进行深度优先遍历,得到的顶点序列正确的是( )

1. 已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：
答案：ABCEGDFHIJ

2. 平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？
答案：2250

1.

program gao7_1：
　function ack(m，n：integer)：integer；
　　begin
　　　if m=0 then ack:=n+1
　　　　　　 else if n=0 then ack:=ack(m-1,1)
　　　　　　　　　　　　 else ack:=ack(m-1,ack(m,n-1))
　　end；
　　 begin   writeln(ack(3,4))； readln； end.
输出：125

2.

program  gao7_2；
　var p,q,s,t：integer；
　begin
　　readln(p)；
　　for q:=p+1 to 2*p do
　　begin
　　　t:=0；s:=(p*q)mod(q-p)；
　　　if s=0 then begin t:=p+q+(p*q)div(q-p)；write(t：4)；end；
　　 end；
　　end.
输入12
输出：181 110  87  76  66  62  61  60

3.

program gao7_3；
　var i,j,h,m,n,k：integer；
　　　b：array[1..10]of integer；
　begin
　　readln(n)；
　　　for i:=1 to 10 do
　　　　begin
　　　　m:=n；j:=11；
　　　　while m>0 do
　　　　　begin j:=j-1；b[j]:=m mod 10；m:=m div 10       end；
　　　　for h:=j to 10 do     n:=n+b[h]；
　　　　end；
　　 writeln(n)；
　end. 
输入1234
输出：1348

4.

program gao7_4；
　var x,y1,y2,y3：integer；
　begin
　　readln(x);y1:=0;y2:=1;y3:=1;
　　while y2<=x do
　　　begin
　　　　y1:=y1+1;y3:=y3+2;y2:=y2+y3
　　　 end;
　　　writeln(y1);
　　end.
输入：23420
输出：153

1. 存储空间的回收算法。设在内存中已经存放了若干个作业A，B，C，D。其余的空间为可用的(如图)。

　　此时，可用空间可用一个二维数组dk[1..100，1..2 ]表示，(如下表一中(a))，其中：dk[i，1]对应第i个可用空间首址，dk[i，2]对应第i个可用空间长度如上图中，dk：

　　现某个作业释放一个区域，其首址为d，长度为L，此时将释放区域加入到可用空间表中。要求在加入时，若可用空间相邻时，则必须进行合并。因此出现下面的4种情况(如上图一(b)所示)。
　(1)下靠，即回收区域和下面可用空间相邻，例如，d=80，L=20，此时成为表二中的(a)。
　(2)上靠，例如，d=600，L=50，此时表成为表二中的(b)。
　(3)上、下靠，例如，d=150，L=150，此时表成为表二中的(c)。
　(4)上、下不靠，例如，d=430，L=20，此时表成为表二中的(d)。

　程序说明：对数组dk预置2个标志,即头和尾标志,成为表二中(b),这样可使算法简单,sp为dk表末地址。
程序清单：

PROGRAM GAO7_5;
　var   i,j,sp,d,l：integer;
　　　dk    ：array[0..100,1..2]of integer;
　begin
　　readln(sp);
　for i:=1 to sp do 
　　readln(dk[i,1],dk[i,2]);
　　dk[0,1]:=0;dk[0,2]:=0;　sp:=sp+1　;
　　dk[sp,1]:=10000;dk[sp,2]:=0;readln(d,l);i:=1;
　while dk[i,1]<d do i:=i+1;　i:=i-1　;
　if(dk[i,1]+dk[i,2]=d)then
　　　　if(d+l=dk[i+1,1])then
　　　　　begin
　　　　　　dk[i,2]:=　dk[i,2]+l+dk[i+1,2]　　;
　　　　　　for j:=i+1 to sp-1 do
　　　　　　　dk[j]:=dk[j+1];
　　　　　　sp：=sp-1;
　　　　　 end
　　　　 else dk[i,2]:=dk[i,2]+l
else if(d+l=dk[i+1,1])then
　　　　　begin
　　　　　　dk[i+1,1]:=　d　;dk[i+1,2]:=dk[i+1,2]+l
　　　　　end
　　 else begin
　　　 　for j:=sp downto i+1 do　　dk[j+1]:=dk[j];
　　　 　　dk[i+1,1]　:=d;　　　dk[i+1,2]:=l;sp:=sp+1;
　　　 end;
　for i:=1 to sp-1 do　    writeln(dk[i,1]:4,dk[i,2]:4);readln;
end.

2. 求关键路径
　设有一个工程网络如下图表示(无环路的有向图)：
　其中，顶点表示活动，①表示工程开始，⑤表示工程结束(可变，用N表示)，边上的数字表示活动延续的时间。

如上图中，活动①开始5天后活动②才能开始工作，而活动③则要等①、②完成之后才能开始，即最早也要7天后才能工作。
　在工程网络中，延续时间最长的路径称为关键路径。上图中的关键路径为：①—②—③—④—⑤共18天完成。
　关键路径的算法如下：
1.数据结构：
　R[1..N，1..N]OF INTEGER；　　　表示活动的延续时间，若无连线，则用-1表示；
　EET[1..N]　　　　　　　　　　　表示活动最早可以开始的时间
　ET[1..N]　　　　　　　　　　 　表示活动最迟应该开始的时间
关键路径通过点J，具有如下的性质：EET[J]=ET[J]
2.约定：
　结点的排列已经过拓扑排序，即序号前面的结点会影响序号后面结点的活动。
程序清单：

program gao7_6；
　var i,j,n,max,min,w,x,y：integer；
　　　r：array[1..20,1..20]　of integer；
　　　eet,et：array[1..20]　of integer；
　begin
　　readln(n)
　　for i:=1 to n do
　　　for j:=1 to n do 
　　　　r[i,j]:=-1;
　　readln(x,y,w);{输入从活动x到活动y的延续时间,以0为结束}
　while x<>0 do
　　　begin
　　　　r[x,y]:=w;　readln(x,y,w)　;
　　　end;
　　eet[1]：=0;{认为工程从0天开始}
　　for i：=2 to n do 
　　　begin
　　　　max:=0;
　　　　for j:=1 to n do 
　　　　　if r[j,i]<>-1 then
　　　　　　　if　r[j,i+eet[j]>max　then max:=r[j,i]+eet[j];
　　　　eet[i]:=max;
　　　end;
　　　　et[n]:=eet[n]　 ;
　　　for i：=n-1 downto 1 do
　　　　begin
　　　　　min：=10000;
　　　　　for j：=1 to n do 
　　　　　　if r[i,j]<>-1 then
　　　　　　　　if　et[j]-r[i,j]<min　then min：=et[j] - r[i,j];
　　　　　　　et[i]：=min;
　　　　　　end;
　　　　writeln(eet[n]);
　　　　for i：=1 to n -1 do 
　　　　　if　eet[i]=et[i]　then write(i,'→');
　　write(n);readln
end.