习题解答

度是1；v1到v5的最短路径长度是6；v1到v6的最短路径长度是3；v1到v7的最短路径长度是6；v1到v8的最短路径长度是7。如图所示。

图7-26 图示例 图7-27 AOV网

4．写出图7-27所示的AOV网的拓扑排序序列。 答：该网只有顶点v3的入度为0，所以只能从它开始进行拓扑排序，其拓扑序列为： v3-> v1-> v4-> v5-> v2-> v6

5．已知无向连通网的邻接矩阵如下所示，试画出该无向连通网以及所对应的最小生成树。

答：无向连通网以及所对应的最小生成树如图(a)、(b)所示。

第8章习题解答

一、填空

1．记录的集合是实施查找的数据基础。在讨论查找问题时，常把T称为 查找表 。 2．能够唯一确定记录的数据项，被称为 关键字 。 3．如果查找只是为了得知是否成功或获取相应的记录信息，并不去改变查找表的内容，那么这种查找称为 静态 查找；如果查找过程会伴随着对数据元素的变更，那么这种查找称为 动态 查找。 4．有序表和分块有序表是一种 静态 查找表；二叉查找树是一种 动态 查找表。 5．在AVL树的平衡调整中，称离插入结点最近且其平衡因子绝对值大于1的那个结点为根结点的子树为“ 最小不平衡树 ”。

- 33 -

习题解答

6．在散列查找中使用的函数，称为“ 散列函数 ”。在散列法中的查找表，称为散列表或哈希表。 7．散列法中，如果两个不同的关键字经过散列函数的计算后，得到了相同的索引地址，那么这种现象被称作“ 冲突 ”。

8．散列法中，计算后得到相同索引地址的那些不同关键字，被称作“ 同义词 ”。

二、选择 1．在对线性表进行折半查找时，要求线性表必须 B 。 A．以顺序方式存储

B．以顺序方式存储，且结点按关键字有序排列 C．以链式方式存储

D．以链式方式存储，且结点按关键字有序排列 2．采用顺序查找法查找长度为n的线性表时，其平均查找长度为 C 。 A．n B．n/2 C．(n+1)/2 D．(n-1)/2 3．有一个有序表： 1，3，9，12，32，41，45，62，75，77，82，95，100

采用折半查找法查找值为82的记录时，要经 C 次关键字比较后，查找成功。 A．1 B．2 C．4 D．8 4．设散列表长m=14，散列函数h(key)=key。表中已有四个记录，关键字分别为15、38、61、84，采用二次探测法解决冲突。那么关键字为49的记录的散列地址为 D 。 A．1 B．3 C．5 D．9 5．在下列各种查找方法中，只有 A 查找法的平均查找长度与表长n无关。 A．散列查找 B．二叉查找树 C．折半查找 D．分块查找 6．在开放地址法中，由于散列到同一个地址而引起的“堆积”现象，是由 B 产生的。 A．同义词之间发生冲突

B．非同义词之间发生冲突

C．同义词之间或非同义词之间发生冲突 D．散列表“溢出” 7．在最坏的情况下，查找成功时二叉查找树的平均查找长度 C 。 A．小于线性表的平均查找长度

B．大于线性表的平均查找长度 C．与线性表的平均查找长度相同

D．无法与线性表的平均查找长度相比较 8．在散列中采用线性探测法解决冲突时，产生的一系列后继散列地址 C 。 A．必须大于、等于原散列地址

B．必须小于、等于原散列地址

C．可以大于或小于但不能等于原散列地址 D．地址大小没有具体限制

三、问答

1． （1）给出关键字序列：loop、if、for、while、repeat，依照创建二叉查找树算法，画出所对应的二叉查找树。该树的平均查找长度是多少？（2）又给出关键字序列：while、repeat、loop、if、for，依照创建二叉查找树算法，画出所对应的二叉查找树。该树的平均查找长度又是多少？

- 34 -

习题解答

答：（1）的二叉查找树如图(a)所示，平均查找长度是： ASLa=(1+2*2+2*3)/5=11/5=2.2 (2) 的二叉查找树如图(b)所示，平均查找长度是： ASLb=(1+2+3+4+5)/5=15/5=3

2．利用折半查找法对一个长度为10的有序表进行查找，请填写查找表中每个元素时所需要的比较次数。

答：根据折半查找算法，因此首先用给定值K与区间[1，10]的中点比较，因此下标为5的元素比较次数为1。若没有找到，接着应该在区间[1，4]或[6，10]中继续折半查找，因此下标为2和下标为8的元素的比较次数为2。继续下去，下标为1、3、6、9的元素的比较次数为3。最后，下标为4、7、10的元素的比较次数为4。于是，所填结果为：

四、应用

1．有关键字序列：20、10、30、15、25、5、35、12、27，请一步步画出构造二叉查找树的过程。 答：构造二叉查找树的过程如下：

2．给出如图8-21所示的一棵二叉查找树，在其基础上分别做操作：（1）删除关键字为15的记录；（2）插入关键字为20的记录。画出这两个操作完成后该树的形态。

- 35 -

习题解答

图8-21 二叉查找树示例

答：1）删除关键字为15的记录后，该树的形态如图(a)或(b)所示，(a)是用待删结点的直接前驱（或左子树根结点）取代所得，而(b)则是用待删结点的直接后继（或右子树根结点）取代所得；（2）插入关键字为20的记录后，该树的形态如图(c)所示。

3．设散列函数为h(key)=key % 11，散列表长为11（索引地址为0~10）。给定： SUN，MON，TUE，WED，THU，FRI，SAT

取单词第1个字母在英语字母表中的序号为关键字值（比如S的关键字值为19），采用链地址法解决散列地址冲突。请画出对应的散列表。 答：对应的散列表如下。

4．有关键字序列：36、27、68、33、97、40、81、24、23、90、32、14，散列表长为13，采用的散列函数为：h(key)=key，使用开放地址法的线性探测解决冲突。请完成下面散列表的填写（比如，第1个插入的是36，它的散列地址为10，由于没有发生冲突，所以比较一次就存放在了地址为10的位置），求出其平均查找长度ASL。

- 36 -