算法与数据结构课后答案9-11章
第9章 集合
一、基础知识题
9.1 若对长度均为n 的有序的顺序表和无序的顺序表分别进行顺序查，试在下列三种情况下分别讨论二者在等概率情况下平均查长度是否相同？
（1）查不成功，即表中没有和关键字K 相等的记录； （2）查成功，且表中只有一个和关键字K 相等的记录；
（3）查成功，且表中有多个和关键字K 相等的记录，要求计算有多少个和关键字K 相等的记录。 【解答】
（1）平均查长度不相同。前者在n+1个位置均可能失败，后者失败时的查长度都是n+1。 （2）平均查长度相同。在n 个位置上均可能成功。 （3）平均查长度不相同。前者在某个位置上(1<=i<=n)查成功时，和关键字K 相等的记录是连续的，而后者要查完顺序表的全部记录。
9.2 在查和排序算法中，监视哨的作用是什么？
【解答】监视哨的作用是免去查过程中每次都要检测整个表是否查完毕，提高了查效率。
9.3 用分块查法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查长度是多少？
【解答】分成45块，每块的理想长度为45(最后一块长20)。若每块长25，则平均查长度为ASL=(80+1)/2+(25+1)/2=53.5(顺序查确定块)，或ASL=19(折半查确定块)。
9.4 用不同的输入顺序输入n 个关键字，可能构造出的二叉排序树具有多少种不同形态? 【解答】 9.5 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，中序前驱结点没有右孩子。
【证明】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点，即右子树上值最小的结点：叶子结点或仅有右子树的结点，没有左孩子；而其中序前驱是其左子树上按中序遍历的最后个结点，即左子树上值最大的结点：叶子结点或仅有左子树的结
点，没有右孩子。命题得证。
9.6 对于一个高度为h 的A VL 树，其最少结点数是多少？反之，对于一个有n 个结点的A VL 树， 其最大高度是多少? 最小高度是多少?
【解答】设以N h 表示深度为h 的A VL 树中含有的最少结点数。显然，N 0=0，N 1 =1，N 2 =2，且N h = N h-1 + N h-2 +1(h ≥2)。这个关系与斐波那契序列类似，用归纳法可以证明：当h ≥0时，N h = F h+2 -1，而F h 约等于
Фh /5。其中Ф=(1+5)/2，则N h 约等于Ф
h+2
/(5-1) (即深度为h 的A VL 树具有的最少结点数)。
有n 个结点的平衡二叉树的最大高度是log Ф(
5(n+1))-2，最小高度是?log 2n ?。
9.7 试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。 【解答】根据9.6的结论可知，深度为n 的A VL 树中的最少结点数为12-=+n n F N
所以12=12-+n F ，有2+n F =13，求得n+2=7(Fibonacci 数列第一项的值假设为1，对应于二叉树表
示有一个结点的二叉树的深度为1)，所以n=5。
1C
+21n n
n
可表示为如下图所示的A VL 树：
9.8 假定有n 个关键字，它们具有相同的哈希函数值，用线性探测方法把这n 个关键字存入到哈希表中要做多少次探测？
【解答】n 个关键字都是同义词，因此用线性探测法第一个关键字存入时不会发生冲突，所以探测的次数应为2)1(21+=+++n n n 次。
9.9 建立一棵具有13个结点的判定树，并求其成功和不成功的平均查长度值各为多少。 【解答】 查成功时的平均查长度为：
13/4113/)64432211(=?+?+?+?=succ ASL
查不成功时的平均查长度为：
7/2714/5414/)41232(==?+?=un ASL
9.10 二叉排序树中关键字互不相同，则其中关键字最小值结点无左孩子，关键字最大值结点无右孩子，此命题是否正确？最小值结点和最大值结点一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？ 【解答】
（1）此命题正确。
（2）最小值结点和最大值结点不一定是叶子结点。
（3）一个新结点不一定总是插在二叉排序树的某叶子上。 9.11 回答问题并填空：
（1）散列表存储的基本思想是什么？
（2）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？ （3）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？ 【解答】
（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址 （2）散列表存储中解决碰撞的基本方法：
① 开放定址法 形成地址序列的公式是：Hi=(H(key)+di)% m ，其中m 是表长，di 是增量。根据di 取法不同，又分为三种：
a ．di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。
3 10
1
5 12
4
2
6
8 11 9 13
7
b．di =12，-12，22，-22，…， k2(k≤m/2) 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3(j为整数)的素数时才有可能。
数据结构与算法题库c．di =伪随机数序列，称为随机探测再散列。
②再散列法Hi=RHi(key) i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另
一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。
③链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用-1]表示，分量初始值为空指针。凡散列地址为i(0≤i≤m-1)的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。
④建立公共溢出区设-1]为基本表，凡关键字为同义词的记录，都填入溢出区-1]。（3）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查通路。

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