一． 选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）
1.下列无符号数中，最小的数是（C）
A.（11011001）2　　B.(75)10　　C.(37)8　　D.(2A)16

2.在外部设备中，绘图仪属于（B）
A. 输入设备　　B.输出设备　　C. 辅（外）存储器　　D.主（内）存储器

3.计算机主机是由CPU与（D）构成的
A. 控制器　　B. 输入、输出设备　　C. 运算器　　D.内存储器

4.计算机病毒的特点是（C）
A. 传播性、潜伏性、易读性与隐蔽性　　B. 破坏性、传播性、潜伏性与安全性
C. 传播性、潜伏性、破坏性与隐蔽性　　D. 传播性、潜伏性、破坏性与易读性

5.WINDOWS 9X是一种（D）操作系统
A. 单任务字符方式　　B. 单任务图形方式　　C. 多任务字符方式　　D. 多任务图形方式

6.Internet的规范译名应为（B）
A. 英特尔网　　B. 因特网　　C. 万维网　　D. 以太网
²    全国科学技术名词审定委员会于1997.7.18为internet作出了命名，中文名词为“因特网”，注释是“指全球最大的、开放的、由众多网络相互连接而成的计算机网络”

7.计算机网络是一个（D）系统
A.管理信息系统　　B.管理数据系统　　C.编译系统　　D. 在协议控制下的多机互连系统

8.计算机系统总线上传送的信号有（B）
A.地址信号与控制信号　　B. 数据信号、控制信号与地址信号
C.控制信号与数据信号　　D. 数据信号与地址信号

9.计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。 已知64位的奔腾处理器一次能处理64个信息位，相当于（A）字节。
A.8个　　B.1个　　C.16个　　D. 2个

10.某种计算机的内存容量是640K，这里的640K容量是指（C）个字节
A.640　　B. 640*1000　　C. 640*1024　　D. 640*1024*1024

11.下面哪些计算机网络不是按覆盖地域划分的（D）
A.局域网　　B. 都市网　　C.广域网　　D. 星型网
²    一般的计算机网络按网络的涉及范围的距离划分为广域网(Wide Area Network)，城域网(Metropolitan Area Network)，局域网(Local Area Network)，都市网属于城域网。

12.在有N个叶子节点的哈夫曼树中，其节点总数为（B）
A.不确定　　B. 2N-1　　C. 2N+1　　D. 2N
²    由于哈夫曼树中没有度为1的结点（这类树又称严格的(Strict)（或正侧的）二叉树），则一棵有n个叶子结点的哈夫曼树共有2n-1个结点。

 
13.已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内
存时是从地址SA开始连续按行存贮分配的。
试问：A（5，8）的起始地址为（A）
A.SA+141　　B. SA+180　　C. SA+222　　D. SA+225
²    二维数组A[1..m,1..n]，求其中任一元素aij的地址公式为
²    Loc(aij)= Loc(a11)+n(i-1)+(j-1)，n是每一行中元素的个数，i，j分别表示行号和列号。
A（5，8）=SA+（10×（5-1）+（8-1））×3=SA+141

14.不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（C）
A.快存/辅存/主存　　B. 外存/主存/辅存　　C. 快存/主存/辅存　　D. 主存/辅存/外存
²    快存实质是高速缓存

15.某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在最坏的情况下，需检视（B）个单元。
A.1000　　B. 10　　C. 100　　D. 50
²    中间位置为MID
²    MID:=(1+1000) div 2=500；250；125；63；32；16；8；4；2；1


16.请仔读下列程序段：
PASCAL语言
Var
　　　a:array[1..3,1..4]of integer;
　　　b:array[1..4,1..3]of integer;
　　　x,y:integer;
　　　begin
　　　　for x:=1to3do
　　　　for y:=1to4do
　　　　　a[x,y]:=x-y;
　　　　for x:=4 downto 1 do
　　　　for y:=1 to 3 do
　　　　　b[x,y]:=a[y,x];
　　　writeln(b[3,2]);
　　end.
上列程序段的正确揄出是（A）
A.-1　　B. -2　　C. -3　　D. -4

17.线性表若采用链表存贮结构，要求内存中可用存贮单元地址（D）
A.必须连续　　B. 部分地址必须连续　　C. 一定不连续　　D. 连续不连续均可

18.下列叙述中，正确的是（D）
A.线性表的线性存贮结构优于链表存贮结构　　B.队列的操作方式是先进后出
C.栈的操作方式是先进先出　　　　　　　　　D. 二维数组是指它的每个数据元素为一个线性表的线性表

 
19.电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类；
一类是两端的小鸟相同；另一类则是两端的小鸟不相同。
已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（B）。
A.奇数　　B. 偶数　　C. 可奇可偶　　D. 数目固定
²    因为顶点上正好停着相同的小鸟，只能在中间增加不同小鸟的个数。
²    增加1只不同小鸟，产生2条不同小鸟的线段；
²    增加2只不同小鸟，产生2条或4条不同小鸟的线段；
²    增加n只不同小鸟，由于线段两端是相同的鸟，通过对称排列，必定是偶数个两端为不同小鸟的线段。
²    通过归纳分析，找出问题的规律性

20.一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每
一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，内屏幕左上角开始，位移为0，然后逐列存储。求位於屏幕（X，Y）的第一个字节的位移是（B）
A.（Y*80+X）*2-1　　B.（（Y-1）*80+X-1）*2
C.（Y*80+X-1）*2　　D.（（Y-1）*80+X）*2-1
²    本题实质为数据的行列存储结构问题。是线性方式即逐行或逐列，从左到右，从上到下的方式
²    位于屏幕（X，Y）的第一个字节的位移是：
前Y列所占用位移空间（Y-1）*80*2个字节，第Y列前（X-1）*2个字节，因此位于屏幕（X,Y）的第一个字节的位移是
（Y-1）*80*2 +（X-1）*2 =（（Y-1）*80 + X-1）*2

二.问题求解：（6+6=12分）

1.已知，按中序遍历二叉树的结果为：abc
问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。

2.设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。
²    用递推公式给出的某人从底层开始走完全部楼梯的走法为(用F(N))记录不同案数：
F(1)=1　F(2)=2　F(3)=4　F(N)=F(N-3)+F(N-2)+F(N-1)　(N≥4)

三、阅读程序，并写出正确的运行结果（每题10分，共20分）
1.PROGRAM NOI_003;
CONST N=7; M=6;
VAR I,J,X0,Y0,X1,Y1,X2,Y2:INTEGER;
D:REAL; P:BOOLEAN; G:ARRAY[0..N,0..M] OF 0..1;

FUNCTION DISP(X1,Y1,X2,Y2:INTEGER):REAL;
BEGIN DISP:=SQRT((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); END;

BEGIN
FOR I:=0 T0 N DO 　FOR J:=0 TO M DO 　G[I,J]:=0
READLN(X1,Y1,X2,Y2); G[X1,Y1]:=1; G[X2,Y2]:=1; P:=TRUE;
WHILE P DO
BEGIN
P:=FALSE; D:=DISP(X1,Y1,X2,Y2); X0:=X1; Y0:=Y1;
FOR I:=4 TO N DO FOR J:=0 TO M DO
IF (D>DISP(I,J,X2,Y2))AND(G[I,J]=0)THEN
BEGIN D:=DISP(I,J,X2,Y2); X0:=I; Y0:=J; END;
IF(X0<>X1) OR (Y0<>Y1) THEN
BEGIN X1:=X0; Y1:=Y0; P:=TRUE; G[X1,Y1]:=1; END;
D:=DISP(X1,Y1,X2,Y2); X0:=X2; Y0:=Y2;
FOR I:=0 TO 3 DO 　FOR J:=0 TO M DO
IF（D<DISP(X1,Y1,I,J)AND(G[I,J]=0) THEN
BEGIN D:=DISP(X1,Y1,I,J); X0:=I; Y0:=J END;
IF(X0<>X2)OR(Y0<>Y2) THEN
BEGIN X2:=X0;Y2=Y0;P:=TRUE; G[X2,Y2]:=1; END;
END; WRITELN(X1,Y1,X2,Y2)
END.
输入：7 6 0 0 　　输出：4　3　0　2

2.PROGRAM NOI_002;
VAR I,J,L,N,K,S,T:INTEGER; B:ARRAY[1..10] OF 0..9;
BEGIN
READLN(L,N); S:=L; K:=1; T:=L;
IF N>L THEN BEGIN
WHILE S<N DO
BEGIN K:=K+1;T:=T*L;S:=S+T END;
S:=S-T;N:=N-S-1;
FOR I:=1 TO 10 DO B[I]:=0;
J:=11;
WHILE N>0 DO
BEGIN J:=J-1; B[J]:=N MOD L; N:=N DIV L END;
FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD(’A ’)+B[I]));
READLN;
END
ELSE WRITELN(CHR(ORD(’A’)+N-1))
END
输入： 4 　167 　　输出：BBAC


　
 

四、完善程序（共38分）
1.问题描述：

将2n个0和2n个1，排成一个圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。
例如，当n=2时，即22个0和22个1排成如下一圈：



比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，…可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。
程序说明
以N=4为例，即有16个0，16个1，数组A用以记录32个0，1的排法，数组B统计二进制数是否已出现过。
程序清单
PROGRAM NOI00;
VAR
A :ARRAY[1..36] OF 0..1;
B :ARRAY[0..31] OF INTEGER;
I,J,K,S,P:INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1;A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27;
WHILE A[J]=1 DO J:=J-1;
（　①　）
FOR I:=J+1TO 27 DO（ ②　）
FOR I:=0 TO 31 DO B[1]:=O;
FOR I:=1 TO 32 DO
BEGIN
（　③　）
FOR K:=I TO I+4 DO S:=S*2+A[K];
（　④　）
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF（　 ⑤ 　）THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.

2问题描述
求出一棵树的深度和宽度。例如有如下的一棵树：
其树的深度为从根结点开始到叶结点结束的最大深度，树的宽度为同一层上结点数的最大值。在上图中树的深度为4，宽度为3。



用邻接表来表示树，上图中的树的邻接表示如下：

1
 2
 3
 4
 0
 0
 
2
 0
 0
 0
 0
 0
 
3
 5
 0
 0
 0
 0
 
4
 6
 0
 0
 0
 0
 
5
 0
 0
 0
 0
 0
 
6
 7
 0
 0
 0
 0
 
7
 0
 0
 0
 0
 0
 

程序清单
PROGRAM NOI00_6;
VAR I,J,SP1,SP2,L,MAX:INTEGER; TREE:ARRAY[1..20,1..6]OF INTEGER;
Q:ARRAY[1..100,0..6] OF INTEGER; D:ARRAY[0..20]OF INTEGER;
BEGIN
FOR I:=1 TO 14 DO FOR J:=1 TO 6 DO TREE[I,J]:=O;
FOR J:=1 TO 14 DO TREE[J,1]:=J;
TREE[1,2]:=2; TREE [1,3]:=3; TREE[1,4]:=4; TREE[2,2]:=5;
TREE[2,3]:=6; TREE [3,2]:=7; TREE[3,3]:=8; TREE[4,2]:=9;
TREE[4,3]:=10; TREE[4,4]:=11; TREE[7,2]:=12;
TREE[7,3]:=13; TREE[13,2]:=14;
SP1:=1; SP2:=1;
FOR I:=1 TO 6 DO Q[1,I]：=TREE[1，I]；
Q[1,0]:=1;
WHILE（　 ①　） DO
BEGIN
L:=（ ② ）; J:=2;
WHILE（ ③ ）DO
BEGIN
SP2:=SP2+1;Q[SP2,0]:=L;Q[SP2,1]:=Q[SP1,J];
FOR I:=2 TO 6 DO
Q[SP2,I]:=TREE[Q[SP1,J],I];
J:=J+1
END;
SP1：=SP1+1
END；
WRITELN（ ④ ）
FOR I:=0 TO 20 DO D[I]:=0;
FOR I:=1 TO SP2 DO
D[Q[I,0]]:=（ ⑤　）
MAX:=D[1];
FOR I:=2 TO 20 DO
IF D[I]>MAX THEN MAX:=D[I];
WRITELN(MAX);
READLN;
END.

　

　
 

 

一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题1.5分，多选无分，共30分)
1、中央处理器CPU能访问的最大存储器容量取决于(A )
　A)地址总线 　B)数据总线 　C)控制总线　 D)内存容量

2、计算机软件保护法是用来保护软件(D)的。
　A)编写权 　B)复制权 　C)使用权 　D)著作权

3、64KB的存储器用十六进制表示，它的最大的地址码是(B)
　A)10000 　B)FFFF 　C)1FFFF 　D)EFFFF

4、在树型目录结构中，不允许两个文件名相同主要指的是(D)
　A)同一个磁盘的不同目录下 　B)不同磁盘的同一个目录下
　C)不同磁盘的不同目录下 　 C)同一个磁盘的同一个目录下

5、下列设备哪一项不是计算机输入设备(C )
　A)鼠标 　B)扫描仪 　C)数字化仪 　D)绘图仪

6、在计算机硬件系统中，cache是(D)存储器
　A)只读 　B)可编程只读 　C)可擦除可编程只读 　D)高速缓冲

7、若我们说一个微机的CPU是用的PII300，此处的300确切指的是(A )
　A)CPU的主时钟频率 　　　　B)CPU产品的系列号
　C)每秒执行300百万条指令 　D)此种CPU允许最大内存容量

8、Email邮件本质上是一个(A)
　A)文件 　B)电报 　C)电话 　D)传真

9、2KB的内存能存储(A)个汉字的机内码
　A)1024 　B)516 　C)2048 　D)218

10、以下对Windows的叙述中，正确的是(A)
　A)从软盘上删除的文件和文件夹，不送到回收站
　B)在同一个文件夹中，可以创建两个同类、同名的文件
　C)删除了某个应用程序的快捷方式，将删除该应用程序对应的文件
　D)不能打开两个写字板应用程序

11、运算式(2047)10—(3FF)16+(2000)8的结果是(A)
　A)(2048)10 　B)(2049)10 　C)(3746)8 　D)(1AF7)16

12、TCP/IP协议共有(C )层协议
　A)3 　 B)4 　C)5 　D)6 
&sup2;    什么是TCP/IP协议
　　TCP/IP（Transmission Control Protocol/Internet Protocol的简写，中文译名为传输控制协议/互联网络协议）协议是Internet最基本的协议，简单地说，就是由底层的IP协议和TCP协议组成的。
在Internet没有形成之前，各个地方已经建立了很多小型的网络，称为局域网，Internet的中文意义是"网际网"，它实际上就是将全球各地的局域网连接起来而形成的一个"网之间的网（即网际网）"。然而，在连接之前的各式各样的局域网却存在不同的网络结构和数据传输规则，将这些小网连接起来后各网之间要通过什么样的规则来传输数据呢？这就象世界上有很多个国家，各个国家的人说各自的语言，世界上任意两个人要怎样才能互相沟通呢？如果全世界的人都能够说同一种语言（即世界语），这个问题不就解决了吗？TCP/IP协议正是Internet上的"世界语"。TCP/IP协议的开发工作始于70年代，是用于互联网的第一套协议。

试将TCP/IP和OSI（开放系统互连）的体系结构进行比较。讨论其异同之处。
答  （1）OSI和TCP/IP的相同点是二者均采用层次结构，而且都是按功能分层。
（2）OSI和TCP/IP的不同点：
OSI分七层，自下而上分为物理层、数据链路层、网络层、运输层、会话层、表示层和应用层，而TCP/IP分四层：网络接口层、网间网层（IP）、传输层（TCP）和应用层。严格讲，TCP/IP网间网协议只包括下三层，应用程序不算TCP/IP的一部分。

13.若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是(C) 
　A)i 　B)n-1 　C)n-i+1 　D)不确定

14.计算机病毒是(B)
　A)通过计算机传播的危害人体健康的一种病毒
　B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合
　C)一种由于计算机元器件老化而产生的对生态环境有害的物质
　D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒

15.下面关于算法的错误说法是(B)
　A)算法必须有输出 　B)算法必须在计算机上用某种语言实现
　C)算法不一定有输入 D)算法必须在有限步执行后能结束

16.[x]补码=10011000，其原码为(B)
　A)011001111 　B)11101000 　C)11100110 　D)01100101

17.以下哪一个不是栈的基本运算(B)
　A)删除栈顶元素 　B)删除栈底的元素 
　C)判断栈是否为空 D)将栈置为空栈

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

19.一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有(B)个结点
　A)2h-1 　B)2h-1 　C)2h+1 　D)h+1

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)}对该图进行深度优先遍历,得到的顶点序列正确的是(D)
  A)a,b,e,c,d,f　B)a,c,f,e,b,d　C)a,e,b,c,f,d　D)a,b,e,d,f,c
&sup2;    无向图(f,d) =(d,f)
&sup2;    (a,b)→ (b,e)→ (e,d)→ (d,f)→ (f,c)

 
二、问题求解(5+7=12分)
1.    已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：
中序遍历        T            T            T                后序遍历                T                    T    T
结点    C    B    G    E    A    F    H    D    I    J        结点    C    G    E    B    H    F    J    I    D    A

答：该二叉树先序遍历的顺序为：ABCEGDFHIJ
            A                
    B                D        
C        E        F        I    
    G                H        J

2.    平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？
答：不在同一直线上的三个点能组成一个三角形？这个问题可以用组合的知识来处理 
 

答：用这些点为顶点，能组成2250个不同四边形。

三、阅读程序，写出程序正确的运行结果(4+7+8+9=28分)

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

四、完善程序(每空3分，共30分)

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



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

100 
 50 
 
300 
 100 
 
50 
 100 
 

 0 
 0 
 
100 
 50 
 
300 
 100 
 
500 
 100 
 
10000 
 0 
 
 
表一(a) 
 表一(b) 
 

　　现某个作业释放一个区域，其首址为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)。

80 70 
300 100 
50 100 
 100 50 
300 100 
500 150 
 100 300 
500 100 

 100 50 
300 100 
430 20 
500 100 
 
表二(a)(下靠) 
 表二(b)(上靠) 
 表二(c)(上，下靠) 
 表二(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；　①　；
　　DK[SP，1]:=10000；DK[SP，2]:=0；READLN(D，L)；I:=1；
　WHILE DK[I，1]<D DO I:=I+1；　②　；
　IF(DK[I，1]+DK[I，2]=D)THEN
　　　　　　　　　　　　　　　IF(D+L=DK[I+1，1])THEN
　　　　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　　　　DK[I，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]::=　④　；DK[I+1，2]:=DK[I+1，2]+L
　　　　　　　　　　　　　END
　　 ELSE BEGIN
　　　　　　FOR J:=SP DOWNTO I+1 DO　　DK[J+1]:=DK[J]；
　　　　　　　⑤　:=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；　①　
　　　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　②　THEN MAX:=R[J，I]+EET[J]；
　　　　EET[I]:=MAX；
　　　END；
　　　　③　 
　　　FOR I：=N-1 DOWNTO 1 DO
　　　　BEGIN
　　　　　MIN：=10000；
　　　　　FOR J：=1 TO N DO 
　　　　　　IF R[I，J]<>-1 THEN
　　　　　　　　IF　④　THEN MIN：=ET[J] - R[I，J]；
　　　　　　　ET[I]：=MIN；
　　　　　　END；
　　　　WRITELN(EET[N])；
　　　　FOR I：=1 TO N -1 DO 
　　　　　IF　⑤　THEN WRITE(I，'→')；
　　WRITE(N)；READLN
END. 
 

四、根据题意，将程序补充完整(每个点3分，共30分)
 题一                      
① SP：=SP+1
② I：I -1
③ DK[I，2]+L+DK[I+1，2]
④ D
⑤ DK[I+1，1]

题二
① READLN(X，Y，W)
② R[J，I]+EET[J]>MAX
③ ET[N]：=EET[N]；
④ ET[J]-R[I，J]<MIN
⑤ EET[I]=ET[I]

这时00，01的高中初赛，还要的话说

谢谢了~~天行~~~这都是我想要的[em5]~~~~我多多都要[em2]
呵呵！！！！是不是很贪心~~~嫌麻烦的话可以发我我邮箱rrllkk@163.com

不麻烦啊,你还可以帮我加分,赫赫(肯加分的人很少的啊)
第三届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
（高中组） 
（PASCAL 语言   竞赛用时：2小时）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●

一、基础部分：
  <1> WPS是属于________类的软件;FOXBASE 是属于_______类的软件。用FOXBASE 的命令：“CREATE  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>一个汉字的机内码目前通常用2个字节来表示：第一个字节是区位码的区号加（160）10；第二个字节是区位码的位码加（160）10 。
已知：汉字“却”的区位码是4020，试写出机内码两个字节的二进制的代码：


     
  <6> 下图中用点表示城市，点与点之间的联系表示城市间的道路：

              D                      　                 C
          
                              
                   
                                           
                  A                    　                   B
试问：
① 能否找出一条从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翻转1800，我们将这个运动用字母a来表示：
                            1                           1

                        
                           h             a            h
                     2             3            3             2
                           图一                      图二
    (b) 沿过三角形的外心，垂直于三角形所在平面的有向轴L（注意：三角形翻转时L轴也随着翻转的），按右手法则旋转1200（右手法则是指用右手大拇指指向L轴的方向，由其余四指决定旋转方向的法则），我们将这样的运动用字母b来表示：
                     1                              3   
                    L                                 L

                     h             b                  h
              2            3                   1             2

       如果将a,b作为运算对象，并将两个运动连续进行看作是一种运算（这里不妨也称为乘法）则对图一的三角形而言，aa的结果便成为：
                              1                          2
                  
                                                     h 
                             h             aa          
                       2             3            3             1

若将运动前后的三角形状态简称为元素，那么三角形状态就可与运动的表达式关联。据此，请回答下列问题：

①    从图一的三角形的原始状态出发，可以运动出多少种不同状态的三角形，试写出最简单的运算表达式（借助于a,b与乘法运算）；
②    这样定义的乘法运算是否符合交换律与结合律？
③    如果将三角形的某种状态运动回到原始状态称之为该元素的逆元素，例如：
                 1                   3                     1
                  
                               b                    bb
               2           3        1          2         2          3
     ∴ bb的逆元素为b ,可以表示为（bb）-1 =b 
     试求：（1）a-1 =   （2）（ab）-1 =    (3) ((aa)a) -1 =   (4) b-1 = 

饿，我不行了，你可以去这里找，挺不错的
http://jsoi.czyz.com.cn/noipshiti.htm

呵呵 ~~早发个URL不就完事了！！！[em13]