B2B2D3B2D3B2A4D3FFKF3KF3CKHHB2A4D3B25A4D3B25A45D3F3C4KF3C4KF3C4KHEHEHE

5 d 3 2 5 3 f

12、已知图G如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）

b 6 a 3 c 4 2 e 答案： 终点 最短路径求解过程 b 6 5 (a,c,b) (a,b) c 3 (a,c) d 6 (a,c,d) 6 ? (a,c,d) e 7 (a,c,e) 7 7 (a,c,e) ? (a,c,e) f 9 9 ? ? ? (a,c,d,f) (a,c,d,f) vj c b d e f S {a,c} {a,c,b} {a,c,d} {a,c,e} {a,c,d,f} 第九章 查找

一、选择题

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

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

2、有一组关键字序列{13,16,6,34,32,98,73,1,27}，哈希表的表长为13，哈希函数

为H(key)=key MOD 13,冲突解决的办法为链地址法，请构造哈希表（用图表示）。 3、解决哈希冲突的主要方法有（ ）。

A. 数字分析法、除余法、平方取中法 B. 数字分析法、除余法、线性探测法

C. 数字分析法、线性探测法、再哈希法 D. 线性探测法、再哈希法、链地址法

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的地址为（ A ）。

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

A. 散列表长度 B. 散列元素个数 C. 装填因子 D. 处理冲突方法

8、根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树，当插入到值为 的结点时需要进行旋转调整。 9、m阶B-树中的m是指（ ）。

A. 每个结点至少具有m棵子树 B. 每个结点最多具有m棵子树

C. 分支结点中包含的关键字的个数 D. m阶B-树的深度 10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=k MOD 9，与18发生冲突的元素有（ ）个。

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

11、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（ ）。

A. 静态查找表 B. 动态查找表 C. 静态查找表和动态查找表 D. 两种表都不适合

12、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时，（ B ）次比较后查找成功。

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

13、在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（ C ）。

A. 顺序查找 B. 折半查找 C. 哈希查找 D. 分块查找

14、下列二叉树中，不平衡的二叉树是（ C ）。 ．

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

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

A. 数字分析法、除余法、平方取中法 B. 数字分析法、除余法、线性探测法

C. 数字分析法、线性探测法、多重散列法 D. 线性探测法、多重散列法、链地址法

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

A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 二、填空题

1、在散列函数H(key)=key％p中，p应取 。 2、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行 2 次查找可确定成功。

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

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

5、在散列存储中，装填因子α的值越大，则存取元素时发生冲突的可能性就越 大 ；α值越小，则存取元素发生冲突的可能性就越 小 。 三、判断题

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

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

（ ）3、哈希表的查找效率主要取决于哈希表造表时所选取的哈希函数和处理冲突的方法。

（ ）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}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度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，请标出各结点的值。

答案：

51961627

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

6、设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77},采用哈希函数

H(key)=key MOD 13,采用开放地址法的二次探测再散列方法解决冲突，试在0－18的散列空间中对关键字序列构造哈希表，画出哈希表，并求其查找成功时的平均查找长

38