数据结构习题课第8、7、6章(网上的答案有些有问题的)

8.9 对于如图8.37 所示的有向网，用Dijkstra 方法求从顶点A 到图中其他顶点的最短路径，并写出执行算法过程中距离向量d 与路径向量p 的状态变化情况。

解：

Dijkstra算法的基本思想：

把图中所有顶点分成两组，第一组包括已确定最短路径的顶点，初始时只含有一个源点，记为集合S；第二组包括尚未确定最短路径的顶点，记为V-S。按最短路径长度递增的顺序逐个把V-S中的顶点加到S中去，直至从v0出发可以到达的所有顶点都包括到S中。在这个过程中，总保持从v0到第一组（S）各顶点的最短路径都不大于从v0到第二组（V-S）的任何顶点的最短路径长度，第二组的顶点对应的距离值是从v0到此顶点的只包括第一组（S）的顶点为中间顶点的最短路径长度。对于S中任意一点j，v0到j的路径长度皆小于v0到（V-S）中任意一点的路径长度。

(后面四行需要在集合S加上E)

从表中可以看出源点A 到其它各顶点的最短距离及路径为： A→B：48 路径：A→B A→C：57 路径：A→D→F→C A→D：15 路径：A→D A→E：28 路径：A→E A→F：48 路径：A→D→F A→G：38 路径：A→D→G

8.10 试写出如图8.38 所示的AOV 网的4 个不同的拓扑序列。

(这里也有点问题，等待老师再次讲解) 解：拓扑排序过程：

1) 输入AOV网络。令 n 为顶点个数。

2) 在AOV网络中选一个没有直接前驱（入度为0）的顶点, 并输出之; 3) 从图中删去该顶点, 同时删去所有它发出的有向 边; 4) 重复以上(2)、(3)步, 直到

全部顶点均已输出，拓扑有序序列形成，拓扑排序完成； 图8.38 所示的AOV 网的4 个不同的拓扑序列为： （1）ABDCEFGIH （2）ABDECFGIH （3）DABCEFGIH （4）DAECBFGIH

8.11 计算如图8.39 所示的AOE 网中各顶点所表示的事件的发生时间ve(j)，vl(j)，各边所表示的活动的开始时间e(i)，l(i)，并找出其关键路径。

解：

(1):e（i）：表示活动ai的最早开始时间。 l（i）：表示活动最迟开始时间的向量。 关键活动特征：e（i）=l（i）

l（j）-e（j）的值表示完成活动aj的时间余量，提前完成非关键活动并不能提高整个工程的进度。

事件可能的最早开始时间ve（i）：对于某一事件vi，它可能的最早发生时间 事件允许的最晚发生时间vl（i）：对于某一事件vi，它允许的最晚发生时间是在保证按时完成整个工程的前提下，该事件最晚必须发生的时间

可以得出：

第7章 二叉树

7.1 选择题。

（1）前序遍历和中序遍历结果相同的二叉树为（ F ）；前序遍历和后序遍历结果相同的二叉树为（ B ）。

A．一般二叉树 B．只有根结点的二叉树

C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树

E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树。 （2）以下有关二叉树的说法正确的是（ B ）。 A．二叉树的度为2 B．一棵二叉树的度可以小于2

C．二叉树中至少有一个结点的度为2 D．二叉树中任一个结点的度均为2 （3）一棵完全二叉树上有1001 个结点，其中叶子结点的个数为（ D ）。 A．250 B．500 C．254 D．501