严蔚敏++数据结构习题集答案(8)

(1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。

(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。

(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。

前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。

8-3 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。 【解答】 current 10 20 30 40 50 60 head

相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。

template

ListNode * Search ( ListNode * head, ListNode *& current, Type key ) { ListNode * p, * q;

if ( key < current ) { p = head; q = current; } else { p = current; q = head; }

while ( p != q && p->data < key ) p = p->link; if ( p->data == key ) { current = p; return p; } else { current = head; return NULL; } }

//循链搜索其值等于key的结点 //找到, 返回结点地址 //未找到, 返回空指针

//确定检测范围, 用p, q指示

8-4 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head, p, key)，检索具有关键码key的结点，并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。 【解答】

p

∧ 10 head 20 30 40 50 60 70 ∧

template

DblListNode * Search ( DblListNode * head, DblListNode *& p, Type key ) { //在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点

类的友元

//函数。若给定值key大于结点p中的数据, 从p向右正向搜索, 否则, 从p向左反向搜索。 DblListNode * 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; }

?i?1n??1??(i?k?1)??(k?i?1)??n???n*(n?3)?i2?i?i*n??n?n?3?i2?i?i*nk?1k?i?1??2?2n 如果指针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个结点时的搜索

成功的平均数据比较次数为

2ASL?1n?n??n?3i?i?i*n?succ?n2?3n?1i?1??2?n???3n一般地，搜索成功的平均数据比较次数为

?i?1n???(i?k)?k?0?(k?i?1)??(n?1)???n*(n?3)?i2?i?i*n?1??(n?1)k?i??2?如果指针p处于第i个结点(i = 1, 2, ?, n)，它左边有i个不成功的位置，右边有n-i+1个不

成功的位置。

ASL?1(n?1)2?n??n*(n?3)22?1??2nunsucci?0?2?i?i?i*n???7n?6n?1一般地，搜索不成功的平均数据比较次数为

8-5 在一棵表示有序集S的二叉搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S = S1 ? S2 ? S3。若对于任意的a ? S1, b ? S2, c ? S3， 是否总有a ? b ? c？为什么？ 【解答】

答案是否定的。举个反例：看下图粗线所示的路径 45 15

25

65

35 50 70 S1 = { 15 }, S2 = { 25, 30, 35, 45 }, S3 = { 40, 50, 65, 70 }

40 30 c = 40 ? S3，b = 45 ? S2，b ? c 不成立。

8-6 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。

【解答】

46 46 46 46 46 46 25 25 78 25 78 25 78 25 78 空树 加46

加78 加25

62 12 62 12 37 62 加62 46 46 加12 加37

25 78 25 78 12 37 62 12 37 62 70 29 70

加29 加70

8-7 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：

(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。

(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。

(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。

试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。 【解答】

① 在被删结点有两个子女时用左子树TL中具最大关键码的结点顶替的算法：

template BstNode * BST :: leftReplace ( BstNode * ptr ) {

BstNode * temp = ptr->leftChild; ptr->data = temp->data; return temp; }

template BstNode * BST :: rightReplace ( BstNode * ptr ) {

//进到ptr的右子树 //搜寻中序下最后一个结点 //用该结点数据代替根结点数据

//进到ptr的左子树

//用该结点数据代替根结点数据

while ( temp->rightChild != NULL ) temp = temp->rightChild; //搜寻中序下最后一个结点

② 在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法：

BstNode * temp = ptr->rightChild; ptr->data = temp->data; return temp; }

while ( temp->leftChild != NULL ) temp = temp->leftChild;

(1) 用左子树TL上具有最大关键码 …… 此处隐藏：4499字，全部文档内容请下载后查看。喜欢就下载吧 ……