第八章习题
8.1 若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分
别讨论两者在等概率时的平均查找长度是否相同？
（1）查找不成功，即表中没有关键字等于给定值K的记录。 （2）查找成功且表中只有一个关键字等于给定值K的记录。
（3）查找成功且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记
录。
8.2 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查
找长度。
8.3 试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。
8.4 试从空树开始，画出按以下次序向2-3树(即3阶B-树)中插入关键码的建树过程：20，
30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。 8.5 选取哈希函数H(k)=(3k)，用线性探测再散列法处理冲突。试在0～10的散列地址空
间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。
8.6 试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的
平均查找长度。 （ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）
8.7 试编写利用折半查找确定记录所在块的分块查找算法。 8.8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，
且树中结点的关键字均不同。
8.9 编写算法，求出指定结点在给定的二叉排序树中所在的层数。
8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结
点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。 8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。 8.12 已知长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。
（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉
排序树并求其等概率的情况下查找成功的平均查找长度。 （2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查
找时查找成功的平均查找长度。 （3）按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功
的平均查找长度。
8.13 含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3
阶B-树中至少有多少个非叶子结点？ 8.14 写一时间复杂度为O(log2n+m)的算法，删除二叉排序树中所有关键字不小于x的结点，
并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 8.15 在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。
编写一时间复杂度为O(log n)的算法，确定数中第k个结点的位置。
实习题
一、哈希表设计。
为30个人的姓名设计一个哈希表，假设姓名用汉语拼音表示。要求用除留余数法构造哈希函数，用线性探测再散列法处理冲突，平均查找长度的上限为2。 二、简单的员工管理系统。
每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统的功能包括：
（1） 查询：按特定条件查找员工。
（2） 修改：按编号对某个员工的某项信息进行修改。
（3） 插入：加入新员工的信息。
（4） 删除：按编号删除已离职的员工的信息。 (5) 排序：按特定条件对所有员工的信息进行排序。
第八章答案
8．2 【解答】 5
ASLsucc=（1+2X2+3X4+4X3）/10=2.9
8.5 【解答】
ASLSUCC=(1 X4+2 X3+6)/8=2
ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/11=40/11
8.12 【解答】
(1) ASLSUCC=(1+2 X2+3 X3+4X3+5X2+6)/12=3.5
(2) 排序为：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep
折半查找ASLSUCC=(1+2 X2+3 X4+4X5)/12=37/12