算法与数据结构C语言版课后习题答案第9.10章

第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个关键字，可能构造出的二叉排序树具有多少种不同形态? 【解答】 1n n?12n9.5 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，中序前驱结点没有右孩子。

【证明】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点，即右子树上值最小的结点：叶子结点或仅有右子树的结点，没有左孩子；而其中序前驱是其左子树上按中序遍历的最后个结点，即左子树上值最大的结点：叶子结点或仅有左子树的结点，没有右孩子。命题得证。

9.6 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树， 其最大高度是多少? 最小高度是多少?

【解答】设以Nh表示深度为h的AVL树中含有的最少结点数。显然，N0=0，N1 =1，N2 =2，且Nh = Nh-1 + Nh-2 +1(h≥2)。这个关系与斐波那契序列类似，用归纳法可以证明：当h≥0时，Nh = Fh+2 -1，而Fh约等于

CФ/5。其中Ф=(1+5)/2，则Nh约等于Ф

hh+2

/(5-1) (即深度为h的AVL树具有的最少结点数)。

(

有n个结点的平衡二叉树的最大高度是logФ5(n+1))-2，最小高度是?log2n?。

9.7 试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。 【解答】根据9.6的结论可知，深度为n的AVL树中的最少结点数为Nn?Fn?2?1

所以12=Fn?2?1，有Fn?2=13，求得n+2=7(Fibonacci数列第一项的值假设为1，对应于二叉树表

示有一个结点的二叉树的深度为1)，所以n=5。

可表示为如下图所示的AVL树：

9.8 假定有n个关键字，它们具有相同的哈希函数值，用线性探测方法把这n个关键字存入到哈希表中要做多少次探测？

【解答】n个关键字都是同义词，因此用线性探测法第一个关键字存入时不会发生冲突，所以探测的次数应为1?2???n?n(n?1)2次。

9.9 建立一棵具有13个结点的判定树，并求其成功和不成功的平均查找长度值各为多少。 【解答】 7 查找成功时的平均查找长度为：

3 1

2 5 4 8 6 9 10 12 ASLsucc?(1?1?2?2?3?4?4?6)/13?41/13

查找不成功时的平均查找长度为：

ASLun?(2?3?12?4)/14?54/14?27/7

11 13 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 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

b．di =12，-12，22，-22，? ，?k2(k≤m/2) 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3(j为整数)的素数时才有可能。 c．di =伪随机数序列，称为随机探测再散列。

② 再散列法 Hi=RHi(key) i=1，2，?，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i(0≤i≤m-1)的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。

④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0..m-1]。 （3）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。

9.12 如何衡量哈希函数的优劣？简要叙述哈希表技术中的冲突概念，并指出三种解决冲突的方法。 【解答】评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面9.11题。

9.13 设有一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=key % 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) % 10(di=12，22，32，?，)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 【解答】

散列地址 关键字 比较次数 0 14 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8

以关键字27为例：H(27)=27%7=6(冲突) H1=(6+1)=7(冲突) H2=(6+22)=0(冲突) H3=(6+33)=5 所以比较了4次。

9.14 对下面的关键字集合{30，15，21，40，25，26，36，37}，若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突。要求：

（1）设计哈希函数； （2）画出哈希表；

（3）计算查找成功和查找失败的平均查找长度。

【解答】由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。

（1）用除留余数法，哈希函数为H(key)=key % 7 （2）

散列地址 关键字 比较次数 0 21 1 1 15 1 2 30 1 3 36 3 4 25 1 5 40 1 6 26 2 7 37 6 8 9 （3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i(0≤i≤m-1)时的查找次数。本例中m=10。故查找失败和查找成功时的平均查找长度分别为：

ASLunsucc=(9+8+7+6+5+4+3+2+1+1)/10=4.6 ASLsucc =16/8=2

9.15 设哈希函数H（k）=3k % 11，散列地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12）按下述两种解决冲突的方法构造哈希表：

（1）线性探测再散列

（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度。

【解答】（1）

散列地址 关键字 比较次数 0 1 4 1 2 3 12 1 4 49 1 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 查找成功时的平均查找长度为 ASLsucc?(1?1?1?2?1?2?1?2)/8?11/8

查找不成功时的平均查找长度为 ASLun?(1?2??1?8?7?6?5?4?3?2?1)/11 4（2）

0 1 2 3 4 5 6 7 8 9 10 ∧ ∧ ∧ 32 21∧ ∧ 13 24∧ ∧ 4 ∧ ∧ 12 49 ∧ 38 ∧ 查找成功时的平均查找长度为 ASLsucc?(1*5?2*3)/8?11/8

查找不成功时的平均查找长度为 ASLun?(1?2??1?2?3?1?3?1??31?1)/11 19.16 已知长度为l2的表{Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}

（1）试按表中元素的次序依次插入一棵初始为空的二叉排序树，并求在等概率情况下查找成功的平均查找长度。

（2）用表中元素构造一棵最佳二叉排序树，求在等概率的情况下查找成功的平均查找长度。 （3）按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。 【解答】 （1） Jan

Feb Mar Apr June May

Aug July Sep

Dec Oct

Nov ASLsuss =(1*1+2*2+3*3+4*3+5*2+6*1)/12=42/12=3.5

（2）最佳二叉排序树的形状和12个结点的折半查找判定树相同，见题目9.17。 ASLsuss =(1*1+2*2+4*3+5*4)/12=37/12 （3） Mar

Jan Oct Aug June May Sep

Feb July Apr Nov

Dec

ASLsuss =(1*1+2*2+3*4+4*4+5*1)/12=38/12

9.17 假定对有序表：(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找，试回答下列问题：(1) 画出描述折半查找过程的判定树；(2) 若查找元素54，需依次与哪些元素比较?(3) 若查找元素90，需依次与哪些元素比较?(4) 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 【解答】

（1） 判定树：（注：结点内的数字为数据元素，旁边的数字是该元素在有序表中的位置） 6 30

3 9

63 5

1 4 7 11

7 42 87 3 24 54 95 4 72

10 12 2 5 8

（2）若查找元素54，需依次与元素30、63、42、54比较，查找成功。 （3）若查找元素90，需依次与元素30、63、87、95比较，查找失败。

（4）等概率下，查找成功时的平均查找长度：ASL=(1*1+2*2+4*3+5*4) /12=37/12

9.18 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？

【解答】在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K，时间复杂度是O(n)。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是(n+1)/2，时间复杂度也是O(n)。

9.19 设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。

（1）51，250，501，390，320，340，382，363

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法与数据结构C语言版课后习题答案第9.10章在线全文阅读。