数据结构（C语⾔）第⼆版第七章课后答案
数据结构(C语⾔)第⼆版第七章课后答案
1．选择题
1~5 C D C A B
6~10 C C C D C
11~15 B C A D A
（1）对n 个元素的表做顺序查时， 若查每个元素的概率相同， 则平均查长度为（C）。
A． (n-1)/2 B ． n/2 C． (n+1)/2 D ． n
总查次数N=1+2+3+…+n=n(n+1)/2 ，则平均查长度为 N/n=(n+1)/2 。
（2）适⽤于折半查的表的存储⽅式及元素排列要求为（D） 。
A．链接⽅式存储，元素⽆序B．链接⽅式存储，元素有序
C．顺序⽅式存储，元素⽆序D ．顺序⽅式存储，元素有序
折半查要求线性表必须采⽤顺序存储结构， 且表中元素按关键字有序排列。
（3）如果要求⼀个线性表既能较快的查，⼜能适应动态变化的要求，最好采⽤(C )查法。
A ．顺序查B．折半查
C．分块查D．哈希查
分块查的优点是： 在表中插⼊和删除数据元素时， 只要到该元素对应的块，就可以在该块内进⾏插⼊和删除运算。由于块内是⽆序的，故插⼊和删除⽐较容易，⽆需进⾏⼤量移动。如果线性表既要快速查⼜经常动态变化，则可采⽤分块查。
（4）折半查有序表（ 4 ， 6， 10， 12， 20 ， 30 ， 50 ， 70 ， 88 ， 100 ）。若查表中元素58，则它将依次与表中（A）⽐较⼤⼩，查结果是失败。
A． 20 ， 70， 30， 50 B ． 30， 88， 70 ， 50
C． 20 ， 50 D． 30 ， 88， 50
表中共10 个元素， 第⼀次取(1+10)/2 =5 ，与第五个元素20 ⽐较， 58 ⼤于20，再取(6+10)/2 =8 ，与第⼋个元素70 ⽐较，依次类推再与30 、50 ⽐较，最终查失败。
（5）对22 个记录的有序表作折半查，当查失败时，⾄少需要⽐较（B）次关键字。
A． 3 B． 4 C ． 5 D． 6
22 个记录的有序表，其折半查的判定树深度为log2 22 + 1=5 ，且该判定树不是满⼆叉树，即查失败时⾄多⽐较5 次，⾄少⽐
较4 次。
（6）折半搜索与⼆叉排序树的时间性能（C） 。
A．相同B．完全不同
C．有时不相同D．数量级都是O(log 2n)
⼆叉排序树不⼀定是平衡树，它是只要求了左右⼦树与根结点存在⼤⼩关系，但是对左右⼦树之间没有层次差异的约束，因此通过⼆叉排序树进⾏查不⼀定能够满⾜logn的。
只有是⼀棵平衡的⼆叉排序树时，其查时间性能才和折半查类似。
（7）分别以下列序列构造⼆叉排序树，与⽤其它三个序列所构造的结果不同的是（C） 。
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)
A 、B、C、D 四个选项构造⼆叉排序树都以100 为根，易知A 、B、D 三个序列中100 的左孩⼦为80，如图1 ，⽽C 选项中100 的
左孩⼦为60，如图2
（8）在平衡⼆叉树中插⼊⼀个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩⼦的平衡因⼦为0 右孩⼦的平衡因⼦为1，则应作（C）型调整以使其平衡。
A ． LL
B ． LR C． RL D ．RR
由题意可知，A的平衡因⼦为1，⼜由于A的右孩⼦的平衡因⼦为1，左孩⼦的平衡因⼦为0，由此可知，A的右孩⼦上仅有右孩⼦，A 的左孩⼦上⽆左右孩⼦，在平衡⼆叉树中插⼊⼀个结点后造成不平衡，说明插⼊结点只能插在A的右孩⼦的左孩⼦上，这种情形属于在右⼦树的左⼦树上插⼊结点的情形，即RL型。
（9）下列关于m 阶B- 树的说法错误的是（D） 。
A ．根结点⾄多有m 棵⼦树
B ．所有叶⼦都在同⼀层次上
C．⾮叶结点⾄少有m/2 (m 为偶数)或m/2+1 （ m 为奇数）棵⼦树
D ．根结点中的数据是有序的
⼀个M阶的B-树有以下基本性质：
根结点的⼦⼥数为[2, M]；
每个⾮根节点所包含的关键字个数 j 满⾜：m/2 - 1 <= j <= m - 1；
除根结点以外的所有结点（不包括叶⼦结点）的度数正好是关键字总数加1，故内部⼦树个数 k 满⾜：m/2<= k <= m ；
所有的叶⼦结点都位于同⼀层。
（10）下⾯关于B- 和B+ 树的叙述中，不正确的是（C） 。
A． B- 树和B+ 树都是平衡的多叉树
B． B- 树和B+ 树都可⽤于⽂件的索引结构
C． B- 树和B+ 树都能有效地⽀持顺序检索
D． B- 树和B+ 树都能有效地⽀持随机检索
B树只能⽀持随机检索，⽽B+树是有序的树，既能⽀持随机检索，⼜能⽀持顺序检索。
（11） m 阶B- 树是⼀棵（B） 。
A． m 叉排序树B ． m 叉平衡排序树
C． m-1 叉平衡排序树D． m+1 叉平衡排序树
树叶中的关键字是有序的。c语言listinsert函数
（12）下⾯关于哈希查的说法，正确的是（C） 。
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突⼩
B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况⽽定
D．哈希表的平均查长度有时也和记录总数有关
哈希函数都要视情况⽽选择
（13）下⾯关于哈希查的说法，不正确的是（A） 。
A ．采⽤链地址法处理冲突时，查⼀个元素的时间是相同的
B ．采⽤链地址法处理冲突时，若插⼊规定总是在链⾸，则插⼊任⼀个元素的时间是相同
的
C．⽤链地址法处理冲突，不会引起⼆次聚集现象
D ．⽤链地址法处理冲突，适合表长不确定的情况
在同义词构成的单链表中，查该单链表表中不同元素，所消耗的时间不同。
（14）设哈希表长为14，哈希函数是H(key)=key%11 ，表中已有数据的关键字为15，38，61， 84 共四个，现要将关键字为49 的元素加到表中，⽤⼆次探测法解决冲突，则放⼊的位置是（D） 。
A ．3
B ． 5 C．8D． 9
关键字15 放⼊位置4，关键字38 放⼊位置5，关键字61 放⼊位置6，关键字84
放⼊位置7 ，再添加关键字49，计算得到地址为5，冲突，⽤⼆次探测法解决冲突得到新地址为6 ，仍冲突，再⽤⽤⼆次探测法解决冲突，得到新地址为4，仍冲突，再⽤⽤⼆次探测法解决冲突，得到新地址为9，不冲突，即将关键字49 放⼊位置9。
（15）采⽤线性探测法处理冲突，可能要探测多个位置，在查成功的情况下，所探测的这些位置上的关键字(A )。
A．不⼀定都是同义词B．⼀定都是同义词
C．⼀定都不是同义词D ．都相同
所探测的这些关键字可能是在处理其它关键字冲突过程中放⼊该位置的。
2．应⽤题
（1）假定对有序表： （ 3， 4， 5， 7， 24 ， 30， 42， 54 ， 63， 72， 87， 95）进⾏折半查，试回答下列问题：
①画出描述折半查过程的判定树；
②若查元素54，需依次与哪些元素⽐较？
③若查元素90，需依次与哪些元素⽐较？
④假定每个元素的查概率相等，求查成功时的平均查长度。
① 先画出判定树;
② 查元素54，需依次与30, 63, 42, 54 元素⽐较；
③ 查元素90，需依次与30, 63,87, 95 元素⽐较；
④ 求ASL 之前，需要统计每个元素的查次数。判定树的前3 层共查1＋ 2 × 2＋ 4×3=17 次；最后⼀层只有5个元素，5×
4=20 次，
所以ASL ＝ （ 17＋ 20 ）/12＝ 37/12
（2）在⼀棵空的⼆叉排序树中依次插⼊关键字序列为12， 7， 17， 11， 16， 2， 13， 9，21， 4，请画出所得到的⼆叉排序树。
（3）已知如下所⽰长度为12 的表：（ Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct,Nov, Dec ）
①试按表中元素的顺序依次插⼊⼀棵初始为空的⼆叉排序树，画出插⼊完成之后的⼆叉排序树，并求其在等概率的情况下查成功的平均查长度。
②若对表中元素先进⾏排序构成有序表，求在等概率的情况下对此有序表进⾏折半查时查成功的平均查长度。
③按表中元素顺序构造⼀棵平衡⼆叉排序树，并求其在等概率的情况下查成功的平均查长度。
答案：
（4）对图7.31 所⽰的3 阶B- 树，依次执⾏下列操作，画出各步操作的结果。
①插⼊90
② 插⼊25
③ 插⼊45
④删除60

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。