8-1 设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908。试画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
【解答】
8-2 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?
(1) 搜索失败;
(2) 搜索成功,且表中只有一个关键码等于给定值k的对象;
(3) 搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象。
【解答】
(1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。
(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。
(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。
前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。
8-3 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head,current,key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。
【解答】
相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。
template<class Type>
ListNode <Type> * Search ( ListNode<Type> * head,ListNode<Type> *& current,Type key ) {
ListNode <Type> * p,* q;
if ( key < current ) { p = head; q = current; } //确定检测范围,用p,q指示
else { p = current; q = head; }
while ( p != q && p->data < key ) p = p->link; //循链搜索其值等于key的结点
if ( p->data == key ) { current = p; return p; } //找到,返回结点地址
else { current = head; return NULL; } //未找到,返回空指针
}
8-4 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head,p,key)，检索具有关键码key的结点，并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。
【解答】
template <class Type>
DblListNode<Type> * Search ( DblListNode<Type> * head,DblListNode<Type> *& p,Type key ) {
//在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点类的友元
//函数。若给定值key大于结点p中的数据,从p向右正向搜索,否则,从p向左反向搜索。
DblListNode<Type> * q = p;
if ( key < p->data ) { while ( q != NULL && q->data > key ) q = q-> lLink; } //反向搜索
else { while ( q != NULL && q->data < key ) q = q-> rLink; } //正向搜索
if ( q != NULL && q->data == key ) { p = q; return p; } //搜索成功
else return NULL;
}
如果指针p处于第i个结点(i = 1,2,…,n)，它左边有i-1个结点，右边有n-i个结点。找到左边第i-1号结点比较2次，找到第i-2号结点比较3次，…，找到第1号结点比较i次，一般地，找到左边第k个结点比较i-k+1次(k = 1,2,…,i-1)。找到右边第i+1号结点比较2次，找到第i+2号结点比较3次，…，找到第n号结点比较n-i+1次，一般地，找到右边第k个结点比较k-i+1次(k = i+1,i+2,…,n)。因此，当指针处于第i个结点时的搜索成功的平均数据比较次数为
一般地，搜索成功的平均数据比较次数为
如果指针p处于第i个结点(i = 1,2,…,n)，它左边有i个不成功的位置，右边有n-i+1个不成功的位置。
一般地，搜索不成功的平均数据比较次数为
8-5 在一棵表示有序集S的二叉搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S = S1 ( S2 ( S3。若对于任意的a ( S1,b ( S2,c ( S3,是否总有a ( b ( c？为什么？
【解答】
答案是否定的。举个反例：看下图粗线所示的路径
S1 = { 15 },S2 = { 25,30,35,45 },S3 = { 40,50,65,70 }
c = 40 ( S3，b = 45 ( S2，b ( c 不成立。
8-6 设有一个输入数据的序列是 { 46,25,78,62,12,37,70,29 },试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
【解答】
8-7 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：
(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。
(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。
(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。
【解答】
在被删结点有两个子女时用左子树TL中具最大关键码的结点顶替的算法：
template<class Type> BstNode<Type> * BST<Type>,,leftReplace ( BstNode<Type> * ptr ) {
BstNode<Type> * temp = ptr->leftChild; //进到ptr的左子树
while ( temp->rightChild != NULL ) temp = temp->rightChild; //搜寻中序下最后一个结点
ptr->data = temp->data; //用该结点数据代替根结点数据
return temp;
}
② 在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法：
template<class Type> BstNode<Type> * BST<Type>,,rightReplace ( BstNode<Type> * ptr ) {
BstNode<Type> * temp = ptr->rightChild; //进到ptr的右子树
while ( temp->leftChild != NULL ) temp = temp->leftChild; //搜寻中序下最后一个结点
ptr->data = temp->data; //用该结点数据代替根结点数据
return temp;
}
(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
temp = leftReplace ( ptr ); //在ptr的左子树中搜寻中序下最后一个结点顶替x
Remove ( ptr->data,temp ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr,int& dir ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在参数表中有一个
//引用变量dir,作为调整方向的标记。若dir = 0,用左子树上具有最大关键码的结点顶替被删关键码; 若dir = 1,
//用右子树上具有最小关键码的结点顶替被删关键码结点,在调用它的程序中设定它的初始值为0。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild,dir ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild,dir ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
if ( dir == 0 ) {
temp = leftReplace ( ptr ); dir = 1; //在ptr的左子树中搜寻中序下最后一个结点顶替x
} else {
temp = rightReplace ( ptr ); dir = 0; //在ptr的右子树中搜寻中序下第一个结点顶替x
}
Remove ( ptr->data,temp,dir ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
#include <stdlib.h>
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在程序中用到一个
//随机数发生器rand( ),产生0(32767之间的随机数,将它除以16384,得到0(2之间的浮点数。若其大于1,用左
//子树上具有最大关键码的结点顶替被删关键码; 若其小于或等于1,用右子树上具有最小关键码的结点顶替被删
//关键码结点,在调用它的程序中设定它的初始值为0。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
if ( (float) ( rand ( ) / 16384 ) > 1 ) {
temp = leftReplace ( ptr ); dir = 1; //在ptr的左子树中搜寻中序下最后一个结点顶替x
} else {
temp = rightReplace ( ptr ); dir = 0; //在ptr的右子树中搜寻中序下第一个结点顶替x
}
Remove ( ptr->data,temp ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
8-8将关键码DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN 依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。
【解答】
8-9 将关键码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个结点，达到该层最多结点个数，因此，满足完全平衡要求。
8-10设散列表为HT[13],散列函数为 H (key) = key %13。用闭散列法解决冲突,对下列关键码序列 12,23,45,57,20,03,78,31,15,36 造表。采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
(2) 采用双散列法寻找下一个空位,再散列函数为 RH (key) = (7*key) % 10 + 1,寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13,H1 = H (key)。画出相应的散列表,并计算等概率下搜索成功的平均搜索长度。
【解答】
使用散列函数 H(key) = key mod 13，有
H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5,
H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5,
H(15) = 2, H(36) = 10.
(1) 利用线性探查法造表：
0
1
2
3
4
5
6
7
8
9
10
11
12
78
15
03
57
45
20
31
23
36
12
(1)
(1)
(1)
(1)
(1)
(1)
(4)
(1)
(2)
(1)
搜索成功的平均搜索长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) =
搜索不成功的平均搜索长度为
ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) =
(2) 利用双散列法造表：
Hi = (Hi-1 + RH (key)) % 13,H1 = H (key)
0
1
2
3
4
5
6
7
8
9
10
11
12
78
15
03
57
45
20
31
36
23
12
(1)
(1)
(1)
(1)
(1)
(1)
(3)
(5)
(1)
(1)
搜索成功的平均搜索长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) =
