v1v2 （1）该图是强连通的吗？若不是，给出强连通分量。 （2）请给出图的邻接矩阵和邻接表表示。

答案：(1) 是强连通图 (2) 邻接矩阵和邻接表为：

0010100001011000v1v2v3v4v2v3v1v3v4v4v3

??112610??1?89????9、已知图G的邻接矩阵A=?128??2?， 试画出它所表示的图G，并根据Prim算法求出

???69??4???10?24???图的的最小生成树（给出生成过程）。 答案：

(1)图形态： (2)prim算法求最小生成树：

v112102v54v3189v4v118v3v5v22v5v324v4v2v11v2v118v3v2v118v2

10、如下图所示的AOV网，写出其中三种拓扑排序序列。

v0v2v1

v3v4v5

11、已知图G如下，根据克鲁斯卡尔算法求图G的一棵最小生成树。（要求给出构造过程）

v6v7答案：kruskal算法的最小生成树

21

B2B2D3B2D3B2A4D3FFKF3KF3CKHHB2A4D3B25A4D3B25A45D3F3C4KF3C4KF3C4KHEHEHE

第九章 查找

一、选择题

1、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（ A ）次。

A. 1 B. 2 C. 3 D. 4

4、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）。

A. n B. log2n C. (h+1)/2 D. h

5、已知表长为25的哈希表，用除留取余法，按公式H(key)=key MOD p 建立哈希表，则p应取（ ）为宜。

A. 23 B. 24 C. 25 D. 26 6、设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4个结点：

addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（ D ）。

A.8 B. 3 C. 5 D. 9 7、在散列查找中，平均查找长度主要与（ C ）有关。

A. 散列表长度 B. 散列元素个数 C. 装填因子 D. 处理冲突方法 10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=k MOD 9，与18发生冲突的元素有（ B ）个。

A. 1 B. 2 C. 3 D. 4 11、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（ B ）。 A. 静态查找表 B. 动态查找表 C. 静态查找表和动态查找表 D. 两种表都不适合 13、在各种查找方法中，平均查找次数与结点个数n无关的查找方法是（ C ）。

A. 顺序查找 B. 折半查找 C. 哈希查找 D. 分块查找 14、下列二叉树中，不平衡的二叉树是（ C ）。 ．

22

15、对一棵二叉排序树按（ B ）遍历，可得到结点值从小到大的排列序列。

A. 先序 B. 中序 C. 后序 D. 层次 16、解决散列法中出现的冲突问题常采用的方法是（ D ）。

A. 数字分析法、除余法、平方取中法 B. 数字分析法、除余法、线性探测法 C. 数字分析法、线性探测法、多重散列法 D. 线性探测法、多重散列法、链地址法

17、对线性表进行折半查找时，要求线性表必须（ C ）。

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

C. 以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序

二、填空题

2、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行 2 次查找可确定成功。

3、具有相同函数值的关键字对哈希函数来说称为 同义词 。

4、在一棵二叉排序树上实施 中序 遍历后，其关键字序列是一个有序表。

三、判断题

（ ×）1、折半查找只适用于有序表，包括有序的顺序表和链表。

（√ ）2、二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。

（√ ）4、平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。 （√ ）5、AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。

四、综合题

1、选取哈希函数H（k）=（k）MOD 11。用二次探测再散列处理冲突，试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。

答案：(1)表形态：

022110112461313245673038411953110(2)ASL：ASL(7)=(1*5+2*1+3*1)/7=(5+2+3)/7=10/7

2、设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求

23

出在等概率的情况下查找成功的平均查找长度ASL。 答案：(1)表形态：

0114122723681455256191720188439102311110212112 (2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6

3、设散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H（K）=K mod 6，采用线性探测法解决冲突，要求： （1）构造散列表；

（2）求查找数34需要比较的次数。 答案：(1)表形态：

0301126223452154716343(2)查找34 的比较次数：3

4、已知下面二叉排序树的各结点的值依次为1－9，请标出各结点的值。

答案：（说明，图中61结点的值应该为 4）

51961627

5、若依次输入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉排序树。画出生成后的二叉排序树（不需画出生成过程）。

8、根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树（画出生成过程）。

6、设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77},采用哈希函数H(key)=key MOD 13,采用开放地址法的二次探测再散列方法解决冲突，试在0－18的散列空间中对关键字序列构造哈希表，画出哈希表，并求其查找成功时的平均查找长度。

7、已知关键字序列{11,2,13,26,5,18,4,9}，设哈希表表长为16，哈希函数H(key)=key MOD 13，处理冲突的方法为线性探测法，请给出哈希表，并计算在等概率的条件下的平均查找长度。

8、设散列表的长度为m=13，散列函数为H(k)=k MOD m，给定的关键码序列为19，14，23，

24

38