发布时间 : 星期四 文章《数据结构与算法》课后习题答案更新完毕开始阅读3a7202dbd15abe23482f4df3
12．在采用线性探测法处理冲突所构成的哈希表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值（B）
A．一定是同义词 B．一定不是同义词 C．都相同 D．不一定都是同义词
13．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（B）个结点最佳。
A．10 B．25 C．6 D．625 14．下列关于m阶B树的说法错误的是（D）。 A．根结点至多有m棵子树 B．所有叶子都在同一层次上
C．非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D．根结点中的数据是有序的 15．m阶B树是一棵（B）。
A．m叉排序树 B．m叉平衡排序树 C．m-1叉平衡排序树 D．m+1叉平衡排序树
7.3.2 判断题
1．顺序查找可以在顺序表上进行，不能在单链表上进行。（×） 2．折半查找只能在有序的顺序表上进行。（√）
3．对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉排序树是相同的。（×）
4．若二叉排序树中关键字互不相同，那么，最小值结点必定无左孩子，最大值结点必定无右孩子。（√）
5．在二叉排序树中，最大值结点和最小值结点一定是叶子结点。（√）
6．将二叉排序树T1的先序遍历序列依次插入初始为空的树中，所得到的二叉排序树T2和T1的形态完全相同。（√）
7．对二叉排序树进行中序遍历得到的序列是由小到大有序的。（√）
8．二叉树为二叉排序树的充分必要条件是任一非终端结点的值大于其左孩子的值、小于右孩子的值。（×）
9．二叉排序树的查找和折半查找的时间复杂度都是O(log2n)，时间性能相同。（×） 10．采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（×） 11．采用线性探测法处理冲突时，当从哈希表中删除一个记录时，不应将这个记录的所在位置置为空，因为这将会影响以后的查找。（√）
12．m阶B树每一个结点的子树个数都小于或等于m。（√）
13．哈希表的查找效率主要取决于构造哈希表时选取的哈希函数和处理冲突的方法。（√）
14．哈希法存储的基本思想是由关键码的值决定数据的存储地址。（√） 15．当负载因子α小于1时，则向哈希表中插入元素时不会引起冲突。（×） 16．查找表中数据元素的任何数据项都可以作为关键字。（×） 17．m阶B树的任何一个结点的所有子树的高度都相等。（√）
18．在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（×）
19．在哈希存储方式中，负载因子的值越大，存取元素时发生冲突的可能性就越大。（√） 20．对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。（√）
7.3.3 简答题
1．画出对长度为18的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 【解答】
（1）判定树为： 9
4 14
11 2 16 6 17 1 3 15 7 10 12 5
188 13
（2）平均查找长度为1/18(1+2*2+3*4+4*8+5*3)=32/9
查找最多比较5次。
2．已知如下所示长度为12的关键字有序的表：
{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec}
（1）试按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 （2）若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。 （3）按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 【解答】
（1）按关键字的顺序构造的二叉排序树： Jan Mar Feb
Jun May Apr
July Sep Aug
Dec Oct
Nov
（2）根据构造的二叉排序树，求查找成功时的平均查找长度：
ASLSUCC=(1*1+2*2+3*3+4*3+5*2+6*1)/12=3.5
（3）若对表中元素先进行排序构成有序表再构造二叉排序树，则构造的二叉排序树是一棵单支树，在等概率的情况下查找成功的平均查找长度则为：
ASLSUCC=(1+2+…+12)/12=6.5 这种情况就退化成为顺序查找。
3．试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。
令Fk表示含有最少结点的深度为k的平衡二叉树的结点数目。那么,可知道F1=1,F2=2,.....Fn=Fn-2+Fn-1+1.
含有12个结点的平衡二叉树的最大深度为５．例如：
A B D E F C G 4．含有9个叶子结点的3阶B树中至少有多少个非叶子结点？含有10个叶子结点的3
H I J 阶B树中至少有多少个非叶子结点？ K 4个、7个。 L 5．试从空树开始，画出按以下次序向3阶B树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后3阶B树的状态。 52 30 68 52 68 52 20 30 60 70 60 70 20 30 70 20 50 60 6．在地址空间为0～16的散列区中，对以下关键字序列构造两个哈希表： {Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec} （1）用线性探测开放定址法处理冲突； （2）用链地址法处理冲突。
并分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为H(key)=i/2,其中i为关键字中第一个字母在字母表中的序号。 【解答】 （1） 0 1 2 3 4 5 Jan 6 7 8 9 10 11 Oct 12 Nov 13 14 15 16 Apr Aug Dec Feb Mar May June July Sep 平均查找长度为:31/12 （2） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ Sep ^ Jan Mar Oct June May ^ Nov ^ July ^ Dec ^ Feb ^ Apr Aug ^ 平均查找长度为:3/2
7．哈希函数H(key)=(3*key) % 11。用开放定址法处理冲突。试在0～10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功时的平均查找长度。
0 22 1 67 2 41 3 30 4 5 53 6 46 7 8 13 9 10 01 平均查找长度为:17/8
8．画出依次插入z，v，o，q，w，y到下图所示的5阶B树的过程。
j c f m r
d e a b g h i k l n p s t x z
【解答】 j
c f m r u d e a b g h i k l n p s t x z j
c f m r u
d e a b g h i k l n p s t u x z j
c f m r u d e a b g h i k l n o p s t u x z j
c f m r u d e a b g h i k l n o p q s t u x z j
c f m r u d e a b g h i k l n o p q s t u w x z j c f m r u x
k l d e a b g h i n o p q s t u w y z