B) 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果是唯一的。
C) 若图G的邻接矩阵是对称的，则G一定是无向图
c a D) 有向图的邻接矩阵一定是非对称矩阵 e 11. 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（） d b A．5 B．3 C．2 D．1 12．下图为用边表示活动的AOE-网。则V8的最早发生时间是 。
二、解答题
1. 已知图的邻接矩阵如下所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
2. 已知某无向图的邻接表存储结构如下图所示，求解下列问题： （1）画出它的无向图；
（2）画出它的的邻接矩阵存储结构；
（3）从顶点A出发，画出其广度优先生成树。
0 A 1 4 1 B 0 2 5 2 C 1 3 4 3 D 2 5 4 E 0 2 5
3. 已知无向带权图G abcde的邻接矩阵如下所示。f5 F 1 3 4
a???b?6c?2?d?5e???6?5?325?565?5???36???????4??2?6??11
（1）画出该无向带权图G；
（2）从顶点a出发，求其深度优先生成树；
（3）从顶点a出发，根据普里姆算法构造最小生成树，过程在下面的图(1)至(5)中画出。 （4）给出邻接表存储结构；
4. 对于如下图所示的带权有向图，求解关键路径, 计算各事件（顶点）的最早发生时间和最迟发生时间，各活动（弧）的最早
开始时间和最迟开始时间。请填写在答题纸的表格中。
6 a b 1 e 8 g 2 k 4 5 c 1 7 h 4 表1 计算各事件（顶点）的最早发生时间和最迟发生时间，请填写在表1的空白处。 顶a b c d e f g h k 点 ve 0 6 4 5 7 15 14 18 vl 0 8 10 16 14 18 表2 计算各活动（弧）的最早开始时间和最迟开始时间，请填写在表2的空白处。 弧 ab ac ad be ce df eg eh fh ghk k e 0 0 0 6 4 5 7 115 4 l 3 8 1110 6 4 5. 对于右图，求解下列问题：
d d 2 4 f 12
（1）写出该图的邻接矩阵； （2）写出全部拓扑排序序列；
（3）从顶点V1出发，给出深度优先遍历生成树；
（4）按照迪杰斯特拉算法，求V1结点到各点的最短路径，填写表1的空白处。
终从V1到各终点的距离和最短路径的点 求解过程 i=i=2 i=3 i=4 i=5 i=6 i=7 1 V2 ----------------------------------V3 3 ------------------------------V∞ ------------------------V∞ ∞ 13 13 ------------V∞ ∞ ∞ ------------------V∞ ∞ ∞ ∞ ∞ ------V∞ ∞ ∞ ∞ 16 16 16 vj v2 v3 第九章 习题 一．单选或填空题
1．已知一个长度为11的有序表，使用折半查找的方法，查找第8个元素时所需进行的关键字比较次数为 。 2. 已知一个长度为16的有序表，使用折半查找的方法，查找一个不存在的元素，则所需进行的关键字比较次数最多是 。
A．4 B．5 C．6 D．7
3. 在二叉排序树中，关键字值最大的结点
A）左指针一定为空 B）右指针一定为空
C）左右指针均为空 D）左右指针均不为空 4．给定关键字集合（51，24，62，43，75，18，55），从一棵空的二叉排序树开始，按表中元素的次序构造一棵二叉排序树，关键字62所在结点的左孩子结点中保存的关键字是（ ） A. 18 B. 24 C. 55 D. 75 5．AVL树是一种平衡的二叉排序树，树中任一结点的
A．左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1
C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度
6. 以下关于查找方法的描述中，错误的是 ．．
A) 平衡二叉树一定也是二叉排序树。
13
B) 有序表的折半查找判定树是二叉排序树。
C) 中序遍历一棵二叉排序树，可以得到其数据元素的升序排列。
D) 后序遍历一棵二叉排序树，可以得到其数据元素的降序排列。
7.下列二叉排序树中，满足平衡二叉树定义的是（ ）
8. 在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（ ）
A. 13，48 B. 24，48 C. 24，53 D. 24，90
9．设哈希表长为14，哈希函数是H(key)=key，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。
A．8 B．3 C．5 D．9
二、解答题
1.画出对长度为12的有序表进行折半查找的判定树，并求其等概率查找成功时的平均查找长度。 2. 已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
错误！未找到引用源。 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
错误！未找到引用源。 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
错误！未找到引用源。 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
14
3.设记录关键字集合key={33,20,53,55,23,38,40,65}，选取哈希函数为H(x)=key mod 11；解决冲突的方法为“线性探测法”。 （1）请按上述条件将key中各值依次填入下表中：
012345678910
（2）求该哈希表查找成功和查找不成功情况下的平均查找长度。 4. 设记录关键字集合key={32,13,49,55,22,39,20}，选取哈希函数为H(x)=key mod 7；解决冲突的方法为“链地址法”。 （1）画出所构造的哈希表； （2）求该哈希表查找成功和查找不成功情况下的平均查找长度。 5. 设哈希表的地址范围为0～17，哈希函数为：H（key）=key。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：
错误！未找到引用源。 画出哈希表的示意图；
错误！未找到引用源。 若查找关键字63，需要依次与哪些关键字进行比较？
错误！未找到引用源。 若查找关键字60，需要依次与哪些关键字比较？
错误！未找到引用源。 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
6. 选取哈希函数H(key)=(3*key) mod 11。用开放定址法处理冲突，di=i((7*key) % 10+1)(i=1,2,3…)。试在0~10的散列地址空间对关键字序列（22，41，53，46，30，13，01，67）： 1） 构造该序列对应的哈希表；
2） 求等概率情况下查找成功的平均查找长度。 哈希表如下图所示：
012345678910
7. 从空树开始，依次插入13，34，51，24，62，43，75，18，画出建立2-3树后的状态，并分别画出删除43、24后的2-3树状态。
三、算法题
1. 试写出顺序表的顺序查找算法。 2. 试写出折半查找算法。
15