13．一个有向图的邻接表和逆邻接表中的节点个数一定相等。（ ）

14．有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非无穷的元素个数。 （ ）

15．图G的某一最小生成树的代价一定小于其他生成树的代价。（ ） 四、综合题

l．请写出如图7-1所示无向图的邻接矩阵和邻接表两种存储结构。

2．依据无向图7-1，请写出：

（1）从顶点1出发图的深度优先搜索序列。 （2）从顶点回出发图广度优先搜索的序列。 （3）写出图的深度优先搜索算法。 （4）写出图的广度优先搜索算法。

3．使用Prim算法，依据无向图7-2做以下问题；

图7-2

（l）写出构造该图的最小生成树的过程。 (2) 写出相应的构造最小生成树算法。

4．使用Kruskal算法，依据无向图7-2做以下问题： （l）写出构造该图的最小生成树的过程。

(2) 写出相应的构造最小生成树算法的形式描述。

5． 假设图采用邻接表表示，写出一个从顶点v0对图按深度优先搜索遍历的非递归算法。

6．有一个无向图采用邻接表的存储结构，请编写算法，以遍历的形式输出从顶点v到顶点w的路径中长度为len的简单路径。

7．以邻接表作为存储结构，编写一个算法，利用深度优先搜索法，求出在无向图中通过给定点w的简单回路的算法。

29

习题八

一、选择题

1.顺序查找方法适合于存储结构为（ ）的线性表

A.散列存储 B.索引存储 C.散列存储或索引存储 D.顺序存储或链接存储 2.对线性表进行二分查找的时候，要求线性表必须（ ）。

A.以顺序存储方式 B.以链接存储方式

C.以顺序存储方式，且数据元素有序 D.以链接存储方式，且数据元素有序 3. 如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（ ）查找方法。 A.顺序 B.分块 C.折半 D.散列

4. 对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该( ) 。

A.以顺序存储方式 B.以链接存储方式 C.以索引存储方式 D.以散列存储方式

5. 在线性表的存储结构中,（ ）查找、插入和删除速度慢，但顺序存储和随机存取第i个元素速度快。 A.顺序表 B.链接表 C.散列表 D.索引表 6. 在( )上查找和存取速度快,但插入和删除速度慢。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 7. 在( )上查找、插入和删除速度快,但不能进行顺序存取。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 8. 在( )上插入、删除和顺序存取速度快,但查找速度慢。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 9. 采用顺序查找方法查找长度为n的线性表,查找每个元素的平均比较次数为( ) A. n B. n/2 C. (n+1)/2 D.(n-1)/2 10.顺序查找具有n个元素的线性表,其时间复杂度为( ) 。 A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n) 11.折半查找具有n个元素的线性表,其时间复杂度为( ) 。 A.O(n) B.O(lOg2n) C.O(n2) D.O(nlog2n) 12.己知一个有序表为(11,22,33,44,55,66,77, 88,99), 则折半查找元素55需要比较( )次。 A.1 B.2 C.3 D.4

13.已知一个有序表为(11,22,33,44,55,66,77,88,99), 则顺序查找元素 55 需要比较( )次。 A.3 B.4 C.5 D.6 14.顺序查找法与二分查找法对存储结构的要求是( ) 。 A. 顺序查找与二分查找均只是适用于顺序表

B. 顺序查找与二分查找均既适用于顺序表 , 也适用于链表 C. 顺序查找只是适用于顺序表 D. 二分查找适用于顺序表

15.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插到集言中。这种方式主要适合于( ) 。 A.静态查找表 B. 动态查找表 C.静态查找表与动态查找表 D. 两种表都不适合

16.若用二分查找取得的中间位置元素关键字值大于被查找值，则说明被查找值位于中间值

30

的前面,下次的查找区间为从原开始位置至( ) 。 A.该中间位置 B.该中间位置-1 C.该中间位置+1 D.该中间位置1/2

二、填空题

1.查找表是由同一类型的数据元素 ( 或记录 ) 组成的 , 是查找所依赖 。

2. 如果对查找表只进行查询某个\特定的\数据元素是否在查找表中, 以及查找某\特定的\数据元素的各种属性两种类型的基本操作,而不进行插入和删除数据元素的查找表称为 。

3. 如果在查找表中进行查找的过程中，同时插入查找表中不存在的数据元素，或者查找表中删除已存在的某个数据元素，则称此类查找表为 。 4. 关键字是数据元素(或记录)中某个 ，用它可以标识(识别)一个查表中

5. 在一个查找表中，能够惟一的标识一个数据元素(或记录)的关键字称为 。 6. 次关键字也称为 或 ，是在查找表中可以标识 的关键字。

7. 查找又称 ，它是根据给定的某个值，在查找表中确定是否有元素(或记 录)的关键字的操作。若操作之后确定表中存在这样的记录，则称为查找 的，否则称为 。

8. 平均查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的 。

9. 最大查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的 。最大查找长度随所查找的 、 和 都有关系。最大查找长度通常是在考虑查找给定值在查找表中的情况。

10. 是一种最简单、最基本的查找方法，它的基本思想是：从表的一端开始，依次顺序扫描线性表，将扫描到记录的关键字逐个与给定值进行比较，若某个记录的关键字和给定的值相等，则说明找到所要的记录，查找成功；若扫描结束后，仍未找到关键字等于给定值的记录，则说明表中没有所查找的记录，查找不成功。 11. 折半查找( Binary Search)又称为 ， 是一种效率较高的一种查找算法。

12. 折半查找的思路是：每次将给定值与查找表中所要查找区域 的关键字进行比较，而不是查找表中的第一条或最后一条。

13. 分析折半查找的性能可以用二叉树来进行描述。把当前查找区间的中间位置上的结点作为根结点，左半区间和右半区间中结点分别作为左子树和右子树，由此得到的二叉可称为 。

14.分块查找(Blocking Search)又称为 ，是一种以 的形式来来进行的查找方法。分块查找是 的一种改进，它是一种介于 和折半查找之间的查找方法。

15. 二叉排序树(Binary Sort Tree)，又称为 ，它或者是一棵空树，或者是具有下列性质的一棵二叉树：

(1) 若左子树不空，则左子树上所有结点的值 。 (2) 若右子树不空，则右子树上所有结点的值 。 (3) 左右子树又分别是 。

16.平衡二叉树定义为：它或者是一棵空树；或者是具有这样性质的二叉树:它的左子树

31

和右子树都是 且左子树和右子树的深度之差的绝对值 。

17. 我们称在构造平衡二叉排序树的过程中，离插入结点最近，且以平衡因子绝对值大 于1 的结点作为根结点的子树为 。

18. 哈希表查找就是一种通过某种映射建立起 之间的对应关系，希望 或经过很少次比较即可获得所要查找的记录。

19. 哈希(Hash)表查找又称为 查找，它是一种重要的查找技术。哈希表查找因使用哈希函数(又称为 ) 而得名。哈希函数是一种 的函数。

20. 利用哈希函数可以实现记录关键字和关键字所对应记录存储地址的转换或映像，这种映像过程称为 或 ，映像结果产生的哈希函数值h (key)作为存储位置称为 或 ，利用哈希函数映像哈希地址，所得到的存储表称为 21. 有时候在向哈希表中存储关键字的时候，会出现一个待插入关键字的记录已经被占用的情况，这种 的现象称为冲突 ( Collision) 。

22. 具有相同哈希函数值的关键字对相应的哈希函数来说称为 ，由同义词产生的冲突称为 。

23. 构造哈希函数的 是取关键字或关键字的某个线性函数作为哈希地址。 24. 构造哈希函数的 是对关键字中数字进行分析，然后用提取其中一部分分布较为均匀的数字位作为哈希地址的方法。

25. 构造哈希函数的 是用关键字key除以某个正整数p，所得余数作为哈希地址的方法。

26. 构造哈希函数的 是取关键字平方的中间几位作为哈希地址的方法。 27. 构造哈希函数的 是先将关键字分割成位数相等的几段(其中最后一段的位数可以不相等)，然后取这几位的叠加和作为哈希地址。 中数位的叠加可以分为移位叠加和间界叠加两种。所谓移位叠加是 ，然后相加；间界叠加是 然后对齐相加。

28. 构造哈希函数应当尽量减少冲突，但是还是无法避免冲突的发生。一旦冲突发生了， 就必须寻求合适的方法来解决冲突。通常解决冲突可以采用 和 。

29. 开放定址法(Open Addressing)是指将哈希表中的空单元向处理冲突开放。开放定址法解决冲突，形成下一个地址的形式是：Hi=(h(key)+di)%m, i=1,2, … ,k(k≤m-l)其中，h (key) 为哈希函数，m为哈希表长，di为增量序列。根据上式形成增量序列di的不同，开放定址法又可以分成如下三种形式： 、 、 。 30. 分析哈希表的查找过程可以知道，造成哈希表冲突的首要因素是 ，第二个因素是 ，第三个因素是 。

31. 在有序表A[1..18]中，采用二分查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为 。

32. 有17个元素的有序表A[1..17]作二分查找，在查找其等于A[8]的元素时，被比较的元素的下标依次是 。

33. 假定有K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行 次探测。

34. 一个无序序列可以通过构造一个 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

35. 在有序表a [1..20]中，采用二分查找算法查找元素值等于a[12]的元素，所比较过的元素的下标依次为 。 36. 对于长度为 n 的线形表 , 若进行顺序查找 , 则时间复杂性为 ；若用二

32