数据结构题目及答案(5)

11136(a)115346(b)34111346(c)1153354642242242(d)(e)

图 7-11 普里姆算法构造最小生成树的过程

4．使用克鲁斯卡尔算法构造出如图 7-7 所示的图 G 的一棵最小生成树。

16776425202351541812810253

图7-7 无向图G

解：使用克鲁斯卡尔算法构造棵最小生成树的过程如图 7-12所示。

21

1256374125346(a)(b)6(c)16742583764112525836(d)464(e)16181245825376(f)4

图 7-12 克鲁斯卡尔算法构造最小生成树的过程

第8章 查找

单项选择题

1.顺序查找法适合于存储结构为 B 的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 C. 索引存储

2.对线性表进行折半查找时，要求线性表的存储方式是 C 。 A. 顺序存储 B. 链接存储

C. 以关键字有序排序的顺序存储 D. 以关键字有序排序的链接存储

3.对有 18 个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为 D 。 A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3

4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 A 查找方法。

22

A. 分块 B. 顺序 C. 二分 D. 散列

5.有一个有序表为{2，5，7，11，22，45，49，62，71，77，90，93，120}，当折半查找值为 90 的结点时，经过 C 次比较后查找成功。 A. 1 B. 2 C. 4 D. 8

6.设哈希表长 m=14，哈希函数 H(key)=key % 11。表中已有 4 个结点：addr(14)=3， addr(38)=5，addr(61)=6，addr(85)=8，其余地址为空，如用线性探测再散列处理冲突，关键字为 49 的结点的地址是 A 。

A. 7 B. 3 C. 5 D. 4

7.在采用链接法处理冲突的开散列表上，假定装填因子a 的值为 4，则查找任一元素的平均查找长度为 A 。

A. 3 B.3.5 C.4 D.2.5 填空题

1.在各种查找方法中，平均查找长度与结点个数 n 无关的查法方法是 散列表查找 。

2.二分查找的存储结构仅限于 有序的顺序存储结构 。

3.在散列存储中，装填因子α的值越大，则 ① ；α的值越小，则 ② 。 ① 存取元素时发生冲突的可能性就越大 ② 存取元素时发生冲突的可能性就越小 4.对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该在二叉树的______左子树_____上继续查找。

5.高度为8的平衡二叉树至少有___54____个结点。

6. 在散列函数 H(key)=key % p 中，p 应取 素数 。

例题解析

【例8-1】设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key % 13 ,采用开放地址法的二次探测再散列方法解决冲突，试在 0～18 的散列地址空间中对该关键字序列构造哈希表。

解：依题意，m=19，二次探测再散列的下一地址计算公式为：

d1=H(key)

d2j=( d1+j*j) % m

d2j?1=( d1-j*j) % m； j=1，2，... 其计算函数如下：

H(19)=19 % 13=6 H(01)=01 % 13=1

23

H(23)=23 % 13=10 H(14)=14 % 13=1 (冲突) H(14)=(1+1*1) % 19=2 H(55)=55 % 13=3 H(20)=20 % 13=7 H(84)=84 % 13=6 (冲突) H(84)=(6+1*1) % 19=7 (仍冲突) H(84)=(6-1*1) % 19=5 H(27)=27 % 13=1 (冲突)

H(27)=(1+1*1) % 19=2 (冲突) H(27)=(1-1) % 19=0 H(68)=68 % 13=3 (冲突) H(68)=(3+1*1) % 19=4 H(11)=11 % 13=11 H(10)=10 % 13=10 (冲突) H(10)=(10+1*1) % 19=11 (仍冲突) H(10)=(10-1*1) % 19=9 H(77)=77 % 13=12

因此：各关键字的记录对应的地址分配如下： addr(27)=0

addr(01)=1 addr(14)=2 addr(55)=3 addr(68)=4 addr(84)=5 addr(19)=6 addr(20)=7 addr(10)=9 addr(23)=10 addr(11)=11 addr(77)=12

其他地址为空。 综合题

1.设散列表为 T［0..12］，散列函数为 H（key）= key，给定键值序列是｛39，36，28，38，44，15，42，12，06，25｝，请画出分别用拉链法和线性探查法处理冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和查找失败时的平均查找长度。

24

解 用散列函数 H（key）= key% 13计算出键值序列的散列地址。并用探查次数表示待查键值需对散列表中键值比较次数。

键值序列：｛39，36，28，38，44，15，42，12，06，25｝ 散列地址： 0，10，2，12，5，2，3，12，6，12 （1）线性探查法处理冲突

用线性探查法处理冲突构造的散列表见表8-1所示。

表8-1 用线性探查法处理冲突构造的散列表

下标 T［0..12］ 查找成功探查次数 查找失败探查次数

0 1 9

1 3 8

2 1 7

3 2 6

4 2 5

5 1 4

6 1 3

7 9 2

8 1

9 1

10 11 12 36 1 2

1

38 1 10

39 12 28 15 42 44 06 25

在等概率的情况下，查找成功的平均查找长度 ASL=（1×6+2×2+3×1+9×1）/10=2.2

设待查键值 k不在散列表中：若 H（k）= k% 13= d，则从 i=d开始顺次与 T［i］位置的键值进行比较，直到遇到空位，才确定其查找失败，同时累计 k键值的比较次数，例如若 k% 13= 0，则必须将 k与 T［0］、T［1］、?、T［8］中的键值进行比较之后，发现 T［8］为空，比较次数为 9、类似地可对 k% 13=1，2，3，?，12进行分析可得查找失败的平均查找长度。

ASL =（9+8+7+6+5+4+3+2+1+1+10）/13 = 59/13 = 4.54 （2）拉链法处理冲突

用拉链法处理冲突构造的散列表见图8-2所示。

图8-2 拉链法处理冲突构造的散列表

在等概率的情况下查找成功的平均查找长度：

25

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构题目及答案(5)在线全文阅读。