admin 管理员组文章数量: 1087139
2024年3月21日发(作者：python中的键可以是列表吗)
《数据结构（C语言版第2版）》（严蔚敏著）
第七章练习题答案
第7章
1．选择题
（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（
A．(n-1)/2
答案：C
解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。
（2）适用于折半查找的表的存储方式及元素排列要求为（
A．链接方式存储，元素无序
C．顺序方式存储，元素无序
答案：D
解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用(
法。
A．顺序查找
C．分块查找
答案：C
解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就
可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量
移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。
（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，
则它将依次与表中（
C．20，50
答案：A
解释：表中共10个元素，第一次取
(1+10)/2
=5，与第五个元素20比较，58大于20，再
取
(6+10)/2
=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。
（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（
A．3
答案：B
解释：22个记录的有序表，其折半查找的判定树深度为
log
2
22
+1=5，且该判定树不是
满二叉树，即查找失败时至多比较5次，至少比较4次。
（6）折半搜索与二叉排序树的时间性能（
A．相同
C．有时不相同
答案：C
（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。
）。
B．完全不同
D．数量级都是O(log
2
n)
B．4C．5D．6
）次关键字。
）比较大小，查找结果是失败。
B．30，88，70，50
D．30，88，50
A．20，70，30，50
B．折半查找
D．哈希查找
)查找
）。
B．链接方式存储，元素有序
D．顺序方式存储，元素有序
B．n/2C．(n+1)/2D．n
）。
查找
A．（100，80，90，60，120，110，130）
B．（100，120，110，130，80，60，90）
C．（100，60，80，90，120，110，130）
D．(100，80，60，90，120，130，110)
答案：C
解释：A、B、C、D四个选项构造二叉排序树都以100为根，易知A、B、D三个序列中
第一个比100小的关键字为80，即100的左孩子为80，而C选项中100的左孩子为60，故选C。
（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A
的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（
A．LL
答案：C
（9）下列关于m阶B-树的说法错误的是（
A．根结点至多有m棵子树
B．所有叶子都在同一层次上
C．非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树
D．根结点中的数据是有序的
答案：D
（10）下面关于B-和B+树的叙述中，不正确的是（
A．B-树和B+树都是平衡的多叉树
答案：C
（11）m阶B-树是一棵（
A．m叉排序树
C．m-1叉平衡排序树
）。
B．m叉平衡排序树
D．m+1叉平衡排序树
）。
B．B-树和B+树都可用于文件的索引结构
）。
B．LRC．RL
）型调整以使其平衡。
D．RR
C．B-树和B+树都能有效地支持顺序检索D．B-树和B+树都能有效地支持随机检索
答案：B
（12）下面关于哈希查找的说法，正确的是（）。
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况而定
D．哈希表的平均查找长度有时也和记录总数有关
答案：C
（13）下面关于哈希查找的说法，不正确的是（）。
A．采用链地址法处理冲突时，查找一个元素的时间是相同的
B．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
C．用链地址法处理冲突，不会引起二次聚集现象
D．用链地址法处理冲突，适合表长不确定的情况
答案：A
解释：在同义词构成的单链表中，查找该单链表表中不同元素，所消耗的时间不同。
（14）设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，
61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是
（）。
A．8
答案：D
解释：关键字15放入位置4，关键字38放入位置5，关键字61放入位置6，关键字84放
入位置7，再添加关键字49，计算得到地址为5，冲突，用二次探测法解决冲突得到新地址为6，
B．3C．5D．9
仍冲突，再用用二次探测法解决冲突，得到新地址为4，仍冲突，再用用二次探测法解决冲突，
得到新地址为9，不冲突，即将关键字49放入位置9。
（15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这
些位置上的关键字()。
B．一定都是同义词
D．都相同
A．不一定都是同义词
C．一定都不是同义词
答案：A
解释：所探测的这些关键字可能是在处理其它关键字冲突过程中放入该位置的。
2．应用题
（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试
回答下列问题：
①画出描述折半查找过程的判定树；
②若查找元素54，需依次与哪些元素比较？
③若查找元素90，需依次与哪些元素比较？
④假定每个元素的查找概率相等，求查找成功时的平均查找长度。
答案：
①先画出判定树如下（注：mid=
(1+12)/2
=6）：
30
563
3
4
7
24
42
5472
87
95答案有问题
②查找元素54，需依次与30,63,42,54元素比较；
③查找元素90，需依次与30,63,87,95元素比较；
④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17
次；
但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08
（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，
4，请画出所得到的二叉排序树。
答案：
12
7
211
49
验算方法：
17
1621
13
用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17,21
（3）已知如下所示长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,
Dec）
①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉
排序树，并求其在等概率的情况下查找成功的平均查找长度。8-
②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找
时查找成功的平均查找长度。
③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均
查找长度。
答案：
（4）对图7.31所示的3阶B-树，依次执行下列操作，画出各步操作的结果。
①插入90②插入25③插入45④删除60
8 20
50
30
35 40
60
80
100
图7.313阶B-树
（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理
冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试
回答下列问题：
①画出哈希表的示意图；
②若查找关键字63，需要依次与哪些关键字进行比较？
③若查找关键字60，需要依次与哪些关键字比较？
④假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
答案：
①画表如下：
0
32
1
17
2
63
3
49
45678
24
9
40
10
10
11121314
30
15
31
16
46
17
47
②查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较,不匹配;
然后顺移，与46,47,32,17,63相比，一共比较了6次！
③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标
记），所以应当只比较这一次即可。
④对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要
2次，“46”需要3次，“47”需要3次，
所以ASL=1/11（6＋2＋3×3+6）＝23/11
（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key%7，
表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算
查找成功的平均查找长度。
答案：
散列地址
关键字
比较次数
0
14
1
1
1
1
2
9
1
3
23
23
4
84
5
27
4
6
55
1
7
20
2
89
平均查找长度：ASL
succ
=（1+1+1+2+3+4+1+2）/8=15/8
以关键字27为例：H（27）=27%7=6（冲突）
H
2
=（6+2）%10=0（冲突）
2
H
1
=（6+1）%10=7（冲突）
所以比较了4次。H
3
=（6+3）%10=5
3
（7）设哈希函数H（K）=3Kmod11，哈希地址空间为0～10，对关键字序列（32，13，
49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找
成功时和查找失败时的平均查找长度ASL
succ
和ASL
unsucc
。
①线性探测法；
②链地址法。
答案：
①
散列地址
关键字
比较次数
01
4
1
23
12
1
4
49
1
5
38
2
6
13
1
7
24
2
8
32
1
9
21
2
10
ASL
succ
=（1+1+1+2+1+2+1+2）/8=11/8
ASL
unsucc
=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11
②
ASL
succ
=（1*5+2*3）/8=11/8
ASL
unsucc
=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11
版权声明：本文标题：《数据结构(C语言版 第2版)》(严蔚敏 著)第七章练习题答案 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1710988715a582984.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论