NOV FEB +2 NOV 加AUG 左单旋 OCT OCT DEC NOV FEB FEB SEP JUL DEC JUL SEP JUL OCT DEC AUG SEP 加SEP
NOV NOV NOV 加APR 加MAR OCT 右单旋 OCT FEB OCT FEB FEB
-2 DEC JUL SEP SEP AUG JUL SEP JUL AUG AUG DEC APR APR DEC MAR APR NOV NOV 加MAY OCT OCT FEB FEB 左单旋 MAR JUL +2 SEP SEP AUG AUG
JUL MAY APR MAR APR DEC DEC
MAY
NOV -2 MAR 加JUN OCT FEB FEB NOV
左右双旋
MAY OCT SEP AUG MAR AUG JUL APR JUL MAY APR DEC DEC JUN SEP
JUN MAR 加JAN NOV FEB
AUG JUL MAY OCT
APR DEC JAN JUN SEP
7-21 从第7-20题所建立的AVL树中删除关键码MAY，为保持AVL树的特性，应如何进行删除和调整? 若接着删除关键码FEB，又应如何删除与调整? 【解答】
删除关键码MAY， MAR 调整 MAR
NOV OCT FEB FEB
AUG AUG JUL MAY OCT JUL NOV SEP
APR APR DEC JAN JUN SEP DEC JAN JUN
删除关键码FEB， MAR 不用调整
OCT JAN
AUG JUL NOV SEP
APR DEC JUN
146
7-22 将关键码1, 2, 3, ?, 2k-1依次插入到一棵初始为空的AVL树中。试证明结果树是完全平衡的。 【解答】
所谓“完全平衡”是指所有叶结点处于树的同一层次上，并在该层是满的。此题可用数学归纳法证明。 当k = 1时，21-1 = 1，AVL树只有一个结点，它既是根又是叶并处在第0层，根据二叉树性质，应具有20 = 1个结点。因此，满足完全平衡的要求。 设k = n时，插入关键码1, 2, 3, ?, 2n-1到AVL树中，恰好每一层(层次号码i = 0, 1, ?, n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k = n+1时，插入关键码为1, 2, 3, ?, 2n-1, 2n, ?, 2n+1-1，总共增加了从2n到2n+1-1的2n+1-1-2n +1 = 2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因此，满足完全平衡要求。
7-23 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树, 其最大高度是多少? 最小高度是多少? 【解答】
设高度为h（空树的高度为 -1）的AVL树的最少结点数为Nh，则Nh = Fh+3 – 1。Fh是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3 / 2 * log2 (n + 1)，最小高度为 ?log2 ( n+1)? -1。
12 个结点的最小高度 12 个结点的最大高度
四、其他练习题
7-24 供选择的答案中选择与下面有关搜索算法的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 (1) 对线性表进行折半搜索时，要求线性表必须（ A ）。 (2) 采用顺序搜索算法搜索长度为n的线性表时，元素的平均搜索长度为（ B ）。 (3) 采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ）。
(4) 采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度应（ D ）对应判定树的最大层次数。
(5) 折半搜索与二叉搜索树（即二叉排序树）的时间性能（ E ）。 (6) 顺序搜索算法适合于存储结构为（ F ）的线性表。 供选择的答案
A：① 以数组方式存储 ② 以数组方式存储且结点按关键码有序排列 ③ 以链接方式存储 ④ 以链接方式存储且结点按关键码有序排列 B：① n/2 ② n ③ (n+1)/2 ④ (n-1)/2 C：① O(n2) ② O(nlog2n) ③ O(log2n) ④ O(n) D：① 小于 ② 大于 ③ 等于 ④ 大于等于 E：① 相同 ② 完全不同 ③ 有时不相同
147
F：① 散列存储 ② 顺序存储或链接存储 ③ 压缩存储 ④ 索引存储
【解答】 A．② B．③ C．③ D．④ E．③ F. ②
7-25 填空题
(1) 以折半搜索方法从长度为12的有序表中搜索一个元素时，平均搜索长度为________。
(2) 以折半搜索方法搜索一个线性表时，此线性表必须是_______存储的_______表。 (3) 从有序表（12, 18, 30, 43, 56, 78, 82, 95）中依次折半搜索43和56元素时，其搜索长度分别为_______和________。
(4) 对于折半搜索所对应的判定树，它既是一棵________，又是一棵_______。
(5) 假定对长度n = 50的有序表进行折半搜索，则对应的判定树高度为_______，判定树中前5层的结点数为_______，最后一层的结点数为________。 【解答】 (1) 37/12 (2) 顺序，有序 (3) 1，3
(4) 二叉搜索树，理想平衡树 (5) 5，31，19
7-26 判断题 (1) 任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。 (2) 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。 (3) 对于两棵具有相同关键码集合而形状不同的二叉搜索树，按中序遍历它们得到的序列的各元素的顺序是一样的。 (4) 在二叉搜索树上插入新的结点时，不必移动其他结点，仅需改动某个结点的指针，使它由空变为非空即可。 (5) 在二叉搜索树上删除一个结点时，不必移动其他结点，只要将该结点的双亲结点的相应的指针域置为空即可。 (6) 最优二叉搜索树的任何子树都是最优二叉搜索树。 (7) 在所有结点的权值都相等的情况下，只有最下面两层结点的度数可以小于2，其他结点的度数必须等于2的二叉搜索树才是最优二叉搜索树。 (8) 在所有结点的权值都相等的情况下，具有平衡特性的二叉搜索树一定是最优二叉搜索树。 (9) 最优二叉搜索树一定是平衡的二叉搜索树。 【解答】 (1) ? (2) ? (3) ? (4) ? (5) ? (6) ? (7) ? (8) ? (9) ?
7-27设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行顺序搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 【解答】
148
017 094 154 170 275 503 509 512 553 612 113151677 (i?1)??7 ASLsucc?14i?022765 131?14?119 897 ASLunsucc??n?(i?1)???715?15 i?0?15908
7-28 试仿照折半搜索方法编写一个Fibonacci搜索算法，并针对n = 12情况，画出Fibonacci算法的判定树。 【解答】
Fibonacci数列为F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, ?。Fibonacci搜索就是利用Fibonacci数列来划分搜索区间的搜索方法。下图是一个 n = 12 的Fibnacci数列的树形结构，Fibonacci搜索就是利用Fibonacci树进行搜索的。 8
5 11
3 7 10 12
2 4 6 9
1
设有n个已经排序好的数据，每次搜索必须先找出Fibonacci树的根root和距离值。其原则如下：
第1步，计算满足Fib(a) <= n+1的Fibonacci数Fib(a)。在上例中，n = 12，由于Fib(7) <= 12+1 = 13，所以，a = 7。
第2步，求得树的根root = Fib(a-1) = Fib(6) = 8。与左子树根的距离dictance_1 = Fib(a-2) = Fib(5) = 5，与右子树根的距离distance_2 = Fib(a-3) = Fib(4) = 3。
第3步，进行迭代，直到找到满足给定值x的数据或距离等于0为止： (1) 若根结点的数据值等于给定值x，搜索成功，返回root所指位置，算法结束。
(2) 若根结点的数据值小于给定值x，则必须搜索第Fib(a-1)个数据之后的数据，新的Fibonacci树是原树的右子树。root = root + distance_2，修改distance_1和distance_2：
distance_1 = distance_1 – distance_2，distance_2 = distance_2 – distance_1。
?? 149
(3) 若根结点的数据值大于给定值x，则必须搜索第Fib(a-1)个数据之前的数据，新的Fibonacci树是原树的左子树。root = root – distance_1，修改distance_1和distance_2：
temp = distance_1，distance_1 = distance_2，distance_2 = temp – distance_2。 下面给出非递归的Fibonacci搜索算法：
#include \
template
while ( Fib ( i ) < CurrentSize ) i++; while ( dis2 != 0 ) {
switch ( compare ( Element[root].key, value ) ) {
case '=' : return root;
//搜索成功, 返回满足要求的位置 //左缩搜索区间
case '>' : root = root - dis1;
break;
case ‘<’ : root = root + dst2;
break;
template
else return ‘>’; } return –1; }
}
//右缩搜索区间
dis1 = dis1 – dis2; dis2 = dis2 – dis1;
//确定Fibnacci数的阶数
root = Fib ( i-1 ); dis1 = Fib ( i-2 ); dis2 = Fib ( i-3 );
temp = dis1; dis1 = dis2; dis2 = temp – dis2;
7-29 假设二叉树存放于二叉链表中，树中结点的关键码互不相同。试编写一个算法，判别给定的二叉树是否二叉搜索树。 【解答】 判断给定二叉树是否二叉搜索树，可以采用递归算法。对于树中所有结点，检查是否左子树上结点的关键码都小于它的关键码，右子树上结点的关键码都大于它的关键码。相应算法如下：
template
void BinaryTree
//在以t为根的子树中递归判断该子树是否二叉搜索树。是，bs返回1，否则bs返回0 if ( t != NULL ) {
if ( ( t->leftChild == NULL || t->data > t->leftChild->data ) &&
( t->rightChild == NULL || t->data < t->rightChild->data ) ) {
bs = 1;
//递归到左子树判断 //递归到右子树判断
binSearchTree ( t->leftChild, bs ); }
else bs = 0;
150
if ( bs ) binSearchTree ( t->rightChild, bs );
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第7章(3)在线全文阅读。
相关推荐：