有些古老的数据结构真题

ren1dan2 · 发表于 08-4-9 13:29:58

试题五北京邮电大学1992年硕士研究生入学考试试题
一. 回答下列问题：
1．利用两个栈sl,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空
运算。请简述这些运算的算法思想。
2．现有n*n阶对角矩阵M，非零元素集中在
以主对角线为中心的带状区域，其示意图
如图1所示。试问：
(1)该对角矩阵有多少非零元素?
(2)带状区域的非零mij的下标i，j与a之
间有何关系?试题5图1
3.设T是一棵二叉树，除叶子结点外，其
它结点的度数皆为2，若 T中有6个叶结点，试问：
（1） T树的最大深度Kmax=?最小可能深度Kmin=?
（2） T树中共有多少非叶结点？
（3）若叶结点的权值分别为1，2，3，4，5，6。请构造一棵哈曼夫树，并计算该哈曼夫树的权路径长度wpl。
二、图2中两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法

求A和B的并集AUB。要求该集合中的元素仍保持递增有序。且要利用A和B的原有结点空间。（15分）
三、写出下列各题的结果：（25分）
1．用无回溯法的模式匹配法（KMP法）及快速的无回溯的模式匹配法求模式串T的next[j]值，添入下面表中：

j 1 2 3 4 5 6 7
t a a b b a a b
Kmp法求得的next[j]值
快速无回溯法求得的next[j]值
2．已知广义表L=((((a))),((b)),(c),d)，试利用head和tail运算把原子项c从L中分离出来。
3．现有一组关键字序列为(13,29,23,44,55,87,25,21,10,79)。利用除留余数法(即H（key）= key MOD p)构造哈希表,并用线性探测再散列的方法解决冲突。设P=15，填装因子
a=0.7
(1)画出构造出的哈希表。
(2)求在查找此哈希表的元素时，在等概率的情况下，查找成功的平均查找长度ASL=?
4．写出图3双链表中对换值为23和l5的两个结点相互位置时修改指针的有关语句。

四、已知二叉树的中序遍历序列为GFBEANHM，后序遍历的结点序列为GEBFHNMA。    (20分)
(1)画出此二叉树的形态。
(2)写出根据二叉树的中序和后序遍历的结点序列，建立它的二叉链表存储结构的递归
算法。

五、某工程的AOE网络如图4所示。(15分)
图中弧上的权值分别为a1~a10的t个活动的期限。
1.画出该AOE网络的十字链表存储结构。
  2.求各事件的最早发生时间ve和最迟发生时间vl，以及各项活动的最早开始时间e和最迟开始时间l.填于下面表中。

事件 ve vl 活动 e l

1
2
3
4
5
6

a1
a2
a3
a4
a5
a6
a7
a8
a9
a10


3. 完成该项工程最少需要多少天？哪些活动为关键活动？关键路径是哪一条？
六、编写一个双向气泡排序的算法，即相邻两边向相反方向起泡。（10分）

ren1dan2 · 发表于 08-4-9 13:30:33

试题六北京邮电学院1993年硕士研究生入学试题
一、回答下列问题：（15分）
1．快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？
2．顺序检索，二分检索，哈希（散列）检索的时间分别为O(n),O(log2n),O(1)。既然有了高效的检索方法，为什么低效的方法还不放弃？
3．已知某二叉树的前序序列和后序序列，能否唯一的构造一棵二叉树。是举例说明之。
二、分析或推导下列各题：（18分）
1. 若一棵树中有度数为1至m的各种结点数为n1,n2,…nm(nm表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。
2. 在改进了的（无回溯）字符串模式匹配中，要先要求next数组的值。下面是求nextval值的算法。
TYPE SAR=ARRAY[1..m] OF INTEGER;
PTY=ARRAY[1..m] OF CHAR;
PROCEDURE next2(P:PTY;VAR NEXTVAL:SAR);
{在模式P中求nextval数组的值}
1 BEGIN
2 J:=1;NEXTVAL[1]:=0;K:=0
3 REPEAT
4    IF (K = 0)OR(P[J]=P[K])
5       THEN [J:=J+1;K:=K+1;
6          IF P[J]=P[K]
7             THEN NEXTVAL[J]:=NEXTVAL[K]
8             ELSE NEXTVAL[J]:=K
9       ELSE K:=NEXTVAL[K]
10    UNTIL J=M
11 END;
算法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]。两出比较语句相同。请分析说明此两处比较语句的含义是什么？
分析此算法在最坏情况下的时间复杂度是多少？
3．举例分析堆排序方法是否稳定。
三、对下述问题中，简述每一个问题较优的解决方法。（解决问题的基本思想）（17分）
1. 有如图1的二叉树，简述前序遍历非递归算法的较优方法。
2. 在已见好的堆中（父结点值≤左，右结点值），再插入两个元素，较好的方法是什么？
3. 在你所学的数据结构算法中，对某算法提出一个较好的改进设想（思路）。

四、某二叉树采用链接存储，其结点结构是： lc data rc Lc和rc分别指向左子树
根和右子树根的指针域。Data为结点数据域。试写出判断该二叉树是否为二叉排序树的算法（不许另设空间，但可以设一些辅助指针）。设二叉排序树，左子树每个结点值<根结点值，右子树每个结点的值≥根结点的值）。二叉树是递归定义的。按此定义写出判断某二叉树是否为二
叉排序树的算法。（20分）
五、图2是有向图按出度建立的邻接表，试写一算法，将此处度邻接表改称入度建立的邻接表。（15分）
六、线性表中有n个元素，每个元素是一个自负，现存于向量R[1..n]中，是写一算法，使R中的字符按字母自负，数字字符和其他字符的顺序排列。要求利用原来的空间，元素移动次数最小。（15分）

ren1dan2 · 发表于 08-4-9 13:30:52

试题七北京邮电学院1994年硕士研究生入学试题

一、（8分）数据结构和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？
二、（8分）在字符串模式匹配的KMP算法中，求模式的next数组织的定义如下：
0 当j=1时
next[j]= max{k|1<k<j且‘P1…Pk-1=’Pj-k+1…Pj-1}
1 其他情况
请问：（1）当j=1试，为什么要去next[1]=0,什么意思？；
（2）为什么要取max{K},K最大是多少？
（3）其他情况是什么情况，为什么取next[j]=1?
三、（8分）在二叉树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用示所保留的参数有什么作用？如何清除最后这个递归语句？
四、（8分）和为哈希表？其查找时间是O(1)吗？为什么？在使用线性探测解决冲突的哈希表，能否对表中元素真正删除，为什么？
五、（8分）对图1所示的二叉树，作如下回答：
（1）这是一棵什么样的二叉树。
（2）画出此二叉树三种不同顺序的存储结构图。
（3）对你所画的存储结构图比较各自的优缺点。
（4）如此二叉树是由树或森林转换而来的，请把次数还原成森林。

六、（8分）对图2所示有向图回答下面问题：
1．在有向图中判别是否存在回路有那些方法，是说明其中两种方法的基本思想。
2．使用弗洛伊德（Floyd）算法求下面这每一对顶点之间的最短路径，实话出矩阵A0,A1,A2,A3中的情况（即A(0),A(1),A(2),A(3)）。
七、（7分）由线性表(a1,a2,…,an),采用单链表存储，头指针为H，每个结点中存放线性表中的一个元素，现查找模个元素值=X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。
（1）线性表中的元素无序。
（2）线性表中的元素按递增有序。
（3）线性表中的元素按递减有序。
八、（10分）线性表中元素存放在向量A（1,…,n）中，元素是整形数。试写一递归算法求出A中的最大和最小元素。
九、（20分）是写一算法判别某二叉树是否是完全二叉树。
十、（15分）写出图的深度优先搜索DFS算法的非递归算法。

ren1dan2 · 发表于 08-4-9 13:31:14

北京邮电大学96考研题
解题要求：
  1试卷回答应字迹清楚，语意正确。
  2 算法题应说明算法的基本思想，并对主要数据类型及变量加以说明，算法力求结构清析，简明易懂，应加以必要的注释。
  3 算法可用类pascal语言编写，也可用你熟悉的高级语言编写，但应说明是哪一种语言。
一．回答下列问题。    （共15分）
⑴ 假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树的结点数可能达到的最大值和最小值各为多少？（4分）
⑵ 分析下面排序算法中各带标号语句的频度及此算法的时间复杂度，并指出此算法是属于哪一种排序法。（7分）
   PROCEDURE sort (VAR  a: ARRAY [1..n]  OF  integer);
      BEGIN
1 FOR  i:=1  TO  n-1  DO
[2 j:=i;
3 FOR  k:=j+1  TO  n  DO
4  IF a[k]<a[j]  THEN  j:=k;
4 t:=a;  a:=a[j];  a[j];=t
]
END;
  ⑶ 全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不须排出名次，问此种情况下，用何种排序方法速度最快？为什（4分）
二．下图所示的伙伴系统中，回收两块首地址分别为768及128，大小为的存储块，
请画出回收后该伙伴系统的状态图。  （10分）

三. 有如下递归算法：
   FUNCTION  sum( n:integer):integer;
BEGIN
IF  n=0 THEN  sum:=0
ELSE [read(x);  {x为整型变量}
sum:=sum(n-1)+x
]
END;
设n初值为4,读入x=4, 9, 6, 2.
  问：（1）若x为局部变量时，该函数递归结束后返回调用程序的sum=?
（2）若x为全局变量时，该函数递归结束后返回调用程序的sum=?
四．根据需要，用适当的语句填入下面算法的                中：
问题：设有n件物品，重量分别为w1,w2,w3,…wn和一个能装载总重量为T的背包。能否从n件物品中选择若干件恰好使它们的重量之和等于T。若能，则背包问题有解，否则无解解此问题的算法如下：  （10分）
FUNCTION    kaup---stack(var stack, w :ARRAY[1…n] of  real;
var top:integer;  T:real):boolean;
{w[1..n] 存放n件物品的重量，依次从中取出物品放入背包中检查背包的重量，若不超过T，则弃之，取下一个物品试之。若有解则返回函数之true,否则返回false}
BEGIN
top:=0;  i:=1;             { i指示待选物品}
WHILE                   ane                   do
   [IF                   or                   and (i<n)
      THEN  [top :=                ;stack[top] :=i;{第i件物品装入背包}
            T:=T-w];
      IF T=0
      THEN RETURN (                )  {背包问题有解}
         ELSE  [IF  (i=n )  and  (top>0)
               THEN  [i:=                   ;{取出栈顶物品}
                        top:=                ;
                        T:=                   ];  {恢复T值}
               i:=i+1       {准备挑选下一件物品}
            ];
];
RETURN(                   )          {背包无解}
END;
五．按下面要求解图2中二叉树的有关问题：（10分）
（1）对此二叉树进行后续后继线索化，（3分）
（2）将此二叉树变换为森林（4分）
（3）用后根序遍历该森林，写出遍历的结点序列。（3分）
六．已知有向网络的带权邻接矩阵如下：  （共15分）
         1    2    3    4    5    6
1    ∞ 20 15 ∞ ∞    ∞
2    2    ∞ ∞ ∞ 10    30
3    ∞ 4    ∞ ∞ ∞    10
4    ∞ ∞ ∞ ∞ ∞    ∞
5    ∞ ∞ ∞ 15 ∞    ∞
6    ∞ ∞ ∞ 5 10    ∞

（1）画出此有向网络（5分）；
（2）以该邻接矩阵为存储结构，分别画出用深度优先和广度优先搜索法得到的生成树或生成森林。（5分）
（3）用DIJKSTRAL法求顶点到其它各顶点的最短路径及其长度，填入下表中（请找出路径长度递增的次序填入）。

路始始点终点
路径路径长度

七.现有待查记录关键字序列为：（40，25，53，17，48，98，87，90）求（1）建立二叉排序树，并求出在等概率的情况下查找成功时的平均查找长度。（5分）
（2）此树是否为二叉平衡树？若不是，请调整为二叉平衡树。（5分）
八．写出算法，求出中序线索二叉树中结合给定值为x的结点之后继结点，返回该后继结点的指针。（20分）
线索树中结点结构如图3所示‘
Ltag lc data rc rtag
               （图3）
图中 data——存放结点的值
      lc，rc——为指向左，右孩子或该结点前驱或后继的指针
   lyag，rtag——为标志域，各值为：0，则lc，rc为指向左，右孩                                                                                              子的指针;  1，则lc，rc为指向某前驱后继结点的指针.

ren1dan2 · 发表于 08-4-9 13:34:26

Ch6树与森林
一、选择题

1、从供选择的答案中选择与下面有关二叉树和森林的叙述中各括号相匹配的词句，将其编号填入相应的括号内。  （每小题1分，共5分）
（1）设二叉树有n个结点且根结点处于第0层，则其高度为（  A  ）。
（2）设高度为h（空二叉树的高度为-1，只有一个结点的二叉树的高度为0）的二叉树只有度为2和度为0的结点，则该二叉树中所含结点至少有（  B  ）个。
（3）设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的右子树中有（  C  ）个结点。
（4）设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的左子树中有（  D  ）个结点。
（5）将含有82个结点的完全二叉树从根结点开始顺序编号，根结点为第0号，其他结点自上向下，同一层自左向右连续编号。则第40号结点的双亲结点的编号为（  E  ）。
【供选择的答案】
A：① n-1 ② log2（n+1） -1 ③ log2n +1 ④ 不确定
B：① 2h ② 2h -1 ③ 2h +1 ④ h +1
C~D：① n1-1 ② n1+n2+n3 ③ n2+n3+n4 ④ n1
E：① 20 ② 19 ③ 81 ④ 80

二、判断题

2、判断下列叙述的对错。如果正确，在题前的括号内填入“”，否则填入“”。
（1）二叉树是树的特殊情形。
（2）若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。
（3）若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。
（4）若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。
（5）若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

三、简答题

3、在结点个数为n（n>1）的各棵树中，高度最小的树的高度（根结点在第0层）是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度（根结点在第0层）是多少？它有多少个叶结点？多少个分支结点？

4、如果一棵树有n1个度为1的结点，有n2个度为2的结点，…，nm个度为m的结点，试问有多少个度为0的结点？

5、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度如何用n来表示（注意n可能为0）？

6、n个结点可构造出多少种不同形态的二叉树？若有3个数据1， 2， 3，输入它们构造出来的中序遍历结果都为1，2，3的不同二叉树有哪些？

7、假定在一棵二叉树中，度为2 的结点有15个，度为1的结点有20个，试问度为0的结点有多少个？

8、一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问:
（1）各层的结点个数是多少？
（2）编号为i的结点的父结点（若存在）的编号是多少？
（3）编号为i的结点的第m个孩子结点（若存在）的编号是多少？
（4）编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？
（5）若结点个数为 n，则高度h是n 的什么函数关系？

9、试分别找出满足以下条件的所有二叉树：
（1）二叉树的前序序列与中序序列相同；
（2）二叉树的中序序列与后序序列相同；
（3）二叉树的前序序列与后序序列相同。

10、已知一棵二叉树的前序遍历结果是ABECDFGHIJ，中序遍历结果是EBCDAFHIGJ，试画出这棵二叉树。

11、写出向堆中加入数据4， 2， 5， 8， 3， 6， 10， 14时，每加入一个数据后堆的变化。

12、判断以下序列是否是最小堆？如果不是，将它调整为最小堆。
（1） { 100， 86， 48， 73， 35， 39， 42， 57， 66， 21 }
（2） { 12， 70， 33， 65， 24， 56， 48， 92， 86， 33 }

13、给定权值集合{ 15， 03， 14， 02， 06， 09， 16， 17 }，构造相应的Huffman树，并计算它的带权外部路径长度。

14、假定用于通信的电文仅由8个字母c1， c2， c3， c4， c5， c6， c7， c8组成，各字母在电文中出现的频率分别为5， 25， 3， 6， 10， 11， 36， 4。试为这8个字母设计不等长Huffman编码，并给出该电文的总码数。

15、给定一组权值: 23， 15， 66， 07， 11， 45， 33， 52， 39， 26， 58，  试构造一棵具有最小带权外部路径长度的扩充4叉树，要求该4叉树中所有内部结点的度都是4，  所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少？（提示：如果权值个数不足以构造扩充4叉树，可补充若干值为零的权值，再仿照霍夫曼树的思路构造扩充4叉树）

四、算法设计题

16、若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：
（1）统计二叉树中叶结点的个数。
（2）以二叉树为参数，交换每个结点的左子女和右子女。

17、若用二叉链表作为二叉树的存储表示，试编写一个递归算法求二叉树中指定结点所在层次。（设二叉树的高度为h，空树时h = -1，只有一个结点的二叉树的高度为h = 0）

18、假设一棵树的存储结构采用双亲表示法，双亲指针数组为int parent[MaxSize]，其中MaxSize表示双亲指针数组的最大结点个数。树中各个结点按先根遍历次序存放，根结点存于parent[0]。试编写一个函数，计算p所指结点和q所指结点的最近公共祖先结点。

19、已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。试设计一个算法，从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。

20、设有一个采用二叉链表表示的二叉树，根结点指针为root。指针p和q分别指向二叉树中的不同的结点。试设计一个算法，寻找指针p和q所指结点的最近的公共祖先结点。

21、下面是一个二叉树的前序遍历的递归算法。
void PreOrder （ BinTreeNode *t ） {
   if （ t != NULL ） { //递归结束条件
cout << t->data； //访问（输出）根结点
PreOrder （ t->leftChild ）； //前序遍历左子树
      PreOrder （ t->rightChild ）； //前序遍历右子树
   }
}
（1）改写PreOrder算法，消去第二个递归调用PreOrder （t->rightChild ）；
（3）利用栈改写PreOrder算法，消去两个递归调用。

22、设二叉树采用二叉链表表示，指针root指向根结点，指针p指向二叉树中某一指定结点。试编写一个算法，找出从根结点到结点*p之间的路径。

23、设二叉树采用二叉链表表示，指针root指向根结点，指针p指向二叉树中某一指定结点。试编写一个算法，找出结点*p的双亲结点的地址。

24、在森林的二叉树表示中，用llink存储指向结点第一个子女的指针，用rlink存储指向结点下一个兄弟的指针，用data存储结点的值。若采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag代替llink，用rtag代替rlink。并设定若ltag = 0，则该结点没有子女，若ltag  0，则该结点有子女；若rtag = 0，则该结点没有下一个兄弟，若rtag  0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用llink - rlink表示的森林。

ren1dan2 · 发表于 08-4-9 13:34:45

Ch8图
一、选择题

1、下面关于工程计划的事件结点网络的叙述中, 哪一个是不正确的?
（1）  关键活动不按期完成就会影响整个工程的完成时间。
（2）何一个关键活动提前完成, 那么整个工程将会提前完成。
（3）有的关键活动都提前完成, 那么整个工程将会提前完成。
（4）某些关键活动若提前完成, 那么整个工程将会提前完成。
（5）任何一个关键活动延迟将会导致整个工程延迟。

2、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。  （每小题1分，共5分）
（1）对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（  A  ），所有边链表中边结点的总数为（  B  ）。
（2）采用邻接表存储的图的深度优先遍历算法类似于二叉树的（  C  ）。
（3）采用邻接表存储的图的广度优先遍历算法类似于二叉树的（  D  ）。
（4）判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（  E  ）。
【供选择的答案】
A：① n ② n+1 ③ n-1 ④ n+e
B：① e/2 ② e ③ 2e ④ n+e
C~D：① 中序遍历 ② 前序遍历 ③ 后序遍历 ④ 按层次遍历
E：① 求关键路径的方法 ② 求最短路径的Dijkstra方法
③ 深度优先遍历算法 ④ 广度优先遍历算法（p194）

二、判断题

3、判断下列叙述的对错。如果正确，在题前的括号内填入“”，否则填入“”。
（1）用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与
图中的顶点个数有关，而与图的边数无关。
（2）对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。
（3）有回路的有向图不能完成拓扑排序。
（4）有n （n≥1）个顶点的无向连通图最少有n-1条边。
（5）有n （n≥1）个顶点的有向强连通图最少有n条边。（P192）

四、填空题

4、填空题  （每小空1分，共5分）
在一个无向图中所有顶点的度数之和等于所有边数的（  A  ）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（  B  ）倍。
若已给出一个有向图的邻接矩阵，则计算第i个顶点的入度的方法是（  C  ），删除所有从第i个顶点发出的边的方法是（  D  ）。
在无向图的邻接矩阵A中，若A[j] = 1，则A[j] = （  E  ）。

五、简答题

5、用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？（p177）

6、对于如右图所示的有向图，试写出：
（1）从顶点①出发进行深度优先搜索所得到的深度优先生成树；
（2）从顶点②出发进行广度优先搜索所得到的广度优先生成树；（p178）

7、以右图为例，按Dijkstra算法计算得到的从顶点①到其它各个顶点的最短路径和最短路径长度。

8、若用一个连通图来表示一个通信网络, 如图所示。


其中, 顶点表示网络中的通信站点, 边表示网络中的通信线路, 则
（1）画出从顶点①出发的深度优先生成树；
（2）在原来的图中补充几条边, 使其中某一站点失效时整个通信网络仍然保持畅通。
（3）指出图中哪几个顶点是关节点（即万一它失效则通信网络将发生故障）。

9、试对下图所示的AOE网络
（1）这个工程最早可能在什么时间结束。
（2）求每个事件的最早开始时间Ve和最迟开始时间Vl。
（3）求每个活动的最早开始时间e（）和最迟开始时间l（）。
（4）确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整
个工程提前完成。（p191）

10、一项工程由六个子工程p1， p2， ， p6组成。这些子工程之间有下列关系：p1 < p2， p3 < p6， p4 < p3， p2 < p6， p4 < p5， p1 < p3， p5 < p6。符号“<”表示“领先于”的关系。例如，p2 < p6表示p2完成后p6才能开始。试给出该工程的三种可能的施工顺序。

六、算法设计题

11、设有一个有向图存储在邻接表中。试设计一个算法，按深度优先搜索策略对其进行拓扑排序。（190）

xumeng · 发表于 08-6-2 18:28:25

		自动登录	找回密码
密码			注册