《数据结构习题解答》习题8解答.doc_大学文库

第8章搜索 8-1设有序顺序表中的元素依次为017, 170,275,503,509,512553,612,677,765,897,908。试画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长【解答】 094)(170 =u42C=1(1+2*2+3*4+4*7=45 14 ASL C;=,(3*1+4*14) 5 15 15 8-2若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? (1)搜索失败 (2)搜索成功,且表中只有一个关键码等于给定值k的对象; (3)搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象【解答】 (1)不同。因为有序顺序表搜索到其关键码比要査找值大的对象时就停止搜索,报告失败信息,不必搜索到表尾:而无序顺序表必须搜索到表尾才能断定搜索失败 (2)相同。搜索到表中对象的关键码等于给定值时就停止搜索,报告成功信息 (3)不同。有序顺序表中关键码相等的对象相继排列在一起,只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来, 所需时间就不相同了前两问可做定量分析。第三问推导出的公式比较复杂,不再进一步讨论。 8-3假定用一个循环链表来实现一个有序表,并让指针head指向具有最小关键码的结点。指针 current 初始时等于head,每次搜索后指向当前检索的结点,但如果搜索不成功则 current重置为head。试编写个函数 search(head, current key)实现这种搜索。当搜索成功时函数返回被检索的结点地址,若搜索不成功则函数返回空指针0。请说明如何保持指针 current以减少搜索时的平均搜索长度。【解答】 curven 相应的搜索函数可以定义为链表及链表结点类的友元函数,直接使用链表及链表结点类的私有数据

第 8 章搜索 80 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 以减少搜索时的平均搜索长度。【解答】相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。 509 154 677 017 275 553 897 094 170 503 512 612 765 908 14 45 (1 2*2 3*4 4*7) 14 1 C 14 1 ASL 1 4 i 1 succ =  i = + + + = = 15 59 (3*1 4*14) 15 1 C 15 1 ASL 15 i 0 ' unsucc =  i = + = = head current 10 20 30 40 50 60

第8章搜索 template ListNode * Search( ListNode*head, ListNode*& current, Type key )4 ListNode *p, 'q: if( key data key )p=p->ink; ∥循链搜索其值等于key的结点 if p->data = key)i current=p: return p: ∥找到,返回结点地址 lse current= head; return NULL; ∥未找到,返回空指针 8-4考虑用双向链表来实现一个有序表,使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点,搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数 search(head,p,kesy),检索具有关键码key的结点,并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度【解答】 hd囚卡20-列上4日5上卡日刘 template DblListNode*Search( DblListNode.head, DblListNode*&p, Type key)( ∥在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点类的友元函数。若给定值key大于结点p中的数据,从p向右正向搜索,否则,从p向左反向搜索 DblListNode*q= p if( key data while( q l= nUll & q->data >key )q=q-> ILink: 1 反向搜索 else while(q= NULL&& q->data key )q=q->rLink; j ∥正向搜索 if (ql= null & q->data =key )(p=g: return p; j 搜索成功 else return NULL 如果指针p处于第i个结点(i=1,2,…,n),它左边有i-1个结点,右边有ni个结点。找到左边第 i-1号结点比较2次,找到第i-2号结点比较3次,…,找到第1号结点比较i次,一般地,找到左边第 k个结点比较i-k+1次(k=1,2,…,i-1)。找到右边第计1号结点比较2次,找到第计2号结点比较3次,…, 找到第n号结点比较ni计+1次,一般地,找到右边第k个结点比较k-计+1次(k=计+1,i+2,…;n)。因此, 1+∑(-k+1)+∑(k-i+1) 3) 3 当指针处于第i个结点时的搜索成功的平均数据比较次数为般地,搜索成功的平均数据比较次数为 ASL n+3 i*n)n2+3n-1 succ 如果指针p处于第i个结点(i=1,2,…,n),它左边有i个不成功的位置,右边有ni+1个不成功的位置 ∑-k)+∑(k-i+1)/(mn+1) *(n+y+2-i-i*n+1/(mn+1) k=0

第 8 章搜索 81 template ListNode * Search ( ListNode * head, ListNode *& current, Type key ) { ListNode * p, * q; if ( key data 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 DblListNode * Search ( DblListNode * head, DblListNode *& p, Type key ) { //在以 head 为表头的双向有序链表中搜索具有值 key 的结点。算法可视为双向链表类和双向链表结点类的友元 //函数。若给定值 key 大于结点 p 中的数据, 从 p 向右正向搜索, 否则, 从 p 向左反向搜索。 DblListNode * q = p; if ( key data ){ while ( q != NULL && q->data > key ) q = q-> lLink; } //反向搜索 else { while ( q != NULL && q->data 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 个不成功的位置。 head p ∧ 10 20 30 40 50 60 70 ∧ n i i i*n 2 n 3 i i i*n n 2 n *(n 3) 1 (i k 1) (k i 1) n 2 2 n k i 1 i 1 k 1 − − + +  =      + − − +  =      + − + +  − + = + − = 3n n 3n 1 n i i i*n 2 n 3 n 1 ASL n 2 i 1 2 succ + − =        − − + + = = i i i*n 1 (n 1) 2 n *(n 3) (i k) (k i 1) (n 1) 2 n k i i 1 k 0  +      + − − + +  + =       − + − + = − =

第8章搜索试编写程序实现这三个删除方法,并用实例说明哪一个方法最易于达到平衡化。【解答】 ①在被删结点有两个子女时用左子树T中具最大关键码的结点顶替的算法 template BstNode*BST: leftReplace( BstNode*ptr )i BstNode*temp=ptr->leftChild; ∥进到p的左子树 while(temp-> rightchild=NULL)temp=temp-> rightchild;搜寻中序下最后一个结点 ∥用该结点数据代替根结点数据 ②在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法: template BstNode* BST: rightReplace( BstNode*ptr )t BstNoderigh(Child; /进到p的右子树 while(temp-> leftchild i=NULL)temp=temp-> leftchild;W搜寻中序下最后一个结点 mp->data; ∥用该结点数据代替根结点数据 return temp; (1)用左子树TL上具有最大关键码的结点X顶替,再递归地删除X template void BST: Remove( Type&x, BstNode*& ptr)( ∥私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过pt返回 BstNode *temp: if( ptr I=NULL if (xdata)Remove(x, ptr->leftChild ) ∥在左子树中执行删除 else if(x> ptr->data )Remove(x, ptr->rightChild ) ∥在右子树中执行删除 else if ptr->left Child I= nULL & ptr->right Child 1= NULL)( ∥p指示关键码为x的结点,它有两个子女 mp=leftReplace( ptr ) ∥在ptr的左子树中搜寻中序下最后一个结点顶替x Remove(ptr-> data, temp);在temp为根的子树中删除该结 else t ∥pr指示关键码为x的结点,它只有一个或零个子女 if( ptr->leftChild==nULL ptr= ptr->rightChild; ∥只有右子女 else if( ptr->rightChild ==NULL ptr=ptr->leftChild; ∥只有左子女 delete temp: (2)交替地用左子树上具有最大关键码的结点和右子树IR上具有最小关键码的结点顶替,再递归地删除适当的结点。 template void BST: Remove(Type& x, BstNode*& ptr, int& dir)t ∥私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过pt返回。在参数表中有一个 ∥引用变量dir,作为调整方向的标记。若dir=0,用左子树上具有最大关键码的结点顶替被删关键码;若dir=1 用右子树上具有最小关键码的结点顶替被删关键码结点,在调用它的程序中设定它的初始值为0。 BstNode*temp

第 8 章搜索 83 试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。【解答】 ① 在被删结点有两个子女时用左子树 TL 中具最大关键码的结点顶替的算法： template BstNode * BST :: leftReplace ( BstNode * ptr ) { BstNode * temp = ptr->leftChild; //进到 ptr 的左子树 while ( temp->rightChild != NULL ) temp = temp->rightChild; //搜寻中序下最后一个结点 ptr->data = temp->data; //用该结点数据代替根结点数据 return temp; } ② 在被删结点有两个子女时用右子树 TR中具最小关键码的结点顶替的算法： template BstNode * BST :: rightReplace ( BstNode * ptr ) { BstNode * temp = ptr->rightChild; //进到 ptr 的右子树 while ( temp->leftChild != NULL ) temp = temp->leftChild; //搜寻中序下最后一个结点 ptr->data = temp->data; //用该结点数据代替根结点数据 return temp; } (1) 用左子树 TL 上具有最大关键码的结点 X 顶替，再递归地删除 X。 template void BST :: Remove ( Type& x, BstNode *& ptr ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。 BstNode * temp; if ( ptr != NULL ) if ( x 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 void BST :: Remove ( Type& x, BstNode *& ptr, int& dir ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。在参数表中有一个 //引用变量 dir, 作为调整方向的标记。若 dir = 0, 用左子树上具有最大关键码的结点顶替被删关键码; 若 dir = 1, //用右子树上具有最小关键码的结点顶替被删关键码结点, 在调用它的程序中设定它的初始值为 0。 BstNode * temp;

第8章搜索 if ptr I=NULL ata)Remove(x, ptr->left Child, dir ) ∥在左子树中执行删除 else if(x> ptr->data)Remove(x, ptr->rightChild, dir ) ∥在右子树中执行删除 else if( ptr-> leftChild I= nULL & ptr->rightChild I= NULL)& ∥p指示关键码为x的结有两个子女 mp= leftReplace(p);dr=1;在pt的左子树中搜寻中序下最后一个结点顶替 i else i temp= rightReplace(ptr;dir=0;∥在ptr的右子树中搜寻中序下第一个结点顶替 Remove( ptr->data, temp, dir ) 在temp为根的子树中删除该结点 ∥p指示关键码为x的结点,它只有一个或零个子女 if( ptr->leftChild = NULL )ptr=ptr->rightchild: ∥只有右子女 else if( ptr->rightChild ==nULL ptr= ptr->leftChild ∥只有左子女 delete temp: (3)用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替,再递归地删除适当的结点。可随机选择其中一个方案 #include template void BST: Remove(Type& x, BstNode*& ptr)i 私有函数:在以p为根的二叉搜索树中删除含x的结点。若删除成功则新根通过pr返回。在程序中用到一个随机数发生器rand(),产生0-32767之间的随机数,将它除以16384,得到0-2之间的浮点数。若其大于1,用左 ∥子树上具有最大关键码的结点顶替被删关键码;若其小于或等于1,用右子树上具有最小关键码的结点顶替被删 ∥关键码结点,在调用它的程序中设定它的初始值为0。 BstNode*temp if(xdata)Remove(x, ptr->left Child ) ∥在左子树中执行删除 else if (x> ptr->data )Remove(x, ptr->rightChild ) ∥在右子树中执行删除 else if ptr-> leftChild null & ptr->right Child I=NULL) ∥pr指示关键码为x的结点,它有两个子女 f(noat)(rand()/16384)>1){ temp= left Replace(ptr);dir=1;∥在pt的左子树中搜寻中序下最后一个结点顶替x i else i temp= rightReplace(p);dir=0;在p的右子树中搜寻中序下第一个结点顶替x Remove( ptr->data, temp ) ∥在temp为根的子树中删除该结点 ∥p指示关键码为x的结点,它只有一个或零个子女 mp= pur

第 8 章搜索 84 if ( ptr != NULL ) if ( x 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 template void BST :: Remove ( Type& x, BstNode *& ptr ) { //私有函数：在以 ptr 为根的二叉搜索树中删除含 x 的结点。若删除成功则新根通过 ptr 返回。在程序中用到一个 //随机数发生器 rand( ), 产生 032767 之间的随机数, 将它除以 16384, 得到 02 之间的浮点数。若其大于 1, 用左 //子树上具有最大关键码的结点顶替被删关键码; 若其小于或等于 1, 用右子树上具有最小关键码的结点顶替被删 //关键码结点, 在调用它的程序中设定它的初始值为 0。 BstNode * temp; if ( ptr != NULL ) if ( x 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;

第 8 章搜索 86 8-9 将关键码 1, 2, 3, …, 2 k -1 依次插入到一棵初始为空的 AVL 树中。试证明结果树是完全平衡的。【解答】所谓“完全平衡”是指所有叶结点处于树的同一层次上，并在该层是满的。此题可用数学归纳法证明。当 k = 1 时，2 1-1 = 1，AVL 树只有一个结点，它既是根又是叶并处在第 0 层，根据二叉树性质，应具有 2 0 = 1 个结点。因此，满足完全平衡的要求。设 k = n 时，插入关键码 1, 2, 3, …, 2n-1 到 AVL 树中，恰好每一层(层次号码 i = 0, 1, …, n-1)有 2 i 个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当 k = n+1 时，插入关键码为 1, 2, 3, …, 2n-1, 2n , …, 2n+1-1，总共增加了从 2 n到 2 n+1-1 的 2 n+1-1-2 n +1 = 2 n 个关键码，使得 AVL 树在新增的第 n 层具有 2 n 个结点，达到该层最多结点个数，因此，满足完全平衡要求。 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 10 (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14 10 搜索不成功的平均搜索长度为 ASLunsucc = 1 13 (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 36 13 (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) 搜索成功的平均搜索长度为 APR DEC JAN JUN SEP