13年电大数据结构1到9章过程性测试习题答案 下载本文

习题解答

度是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 -