8-1 若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索 , 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同 ?

(1) 搜索失败 ;

(2) 搜索成功 , 且表中只有一个关键码等于给定值 k 的对象 ;

(3) 搜索成功 , 且表中有若干个关键码等于给定值 k 的对象 , 要求一次搜索找出所有对象。

【解答】

(1)

(2)

(3)

8-2 假定用一个循环链表来实现一个有序表，并让指针 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 ;

}

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

【解答】

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

【解答】

8 -5 设散列表为 HT[13], 散列函数为 H ( key ) = key %13 。用闭散列法解决冲突 , 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位 , 画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。

(2) 采用双散列法寻找下一个空位 , 再散列函数为 RH ( key ) = (7* key ) % 10 + 1, 寻找下一个空位的公式为 H i = (H i-1 + RH ( key )) % 13, H 1 = H ( key ) 。画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度。

【解答】

答案

>>返回