作业-查找

第七节 查找

一、选择题

1．顺序查找法适合于( )存储结构的查找表。

A．压缩 B．散列 C．索引 *D．顺序或链式

2．对采用折半查找法进行查找操作的查找表，要求按( )方式进行存储。

A．顺序存储 B．链式存储 *C．顺序存储且结点按关键字有序 D．链式存储且结点按关键字有序

3．设顺序表的长为n，用顺序查找法,则其每个元素的平均查找长度是( )。

*A．(n+1)／2 B．(n-1)／2 C．n／2 D．n 4．设有序表的关键字序列为

(1，4，6，10，18，35，42，53，67，71，78，84，92，99)， 当用折半查找法查找键值为35 67的结点时，经( )次比较后查找成功。

A．2 B．3 *C．4 D．6

5．在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为( )。

*A．n+l B．1 C．n D．n-1

6．用顺序查找法对具有n个结点的线性表查找的时间复杂度量级为( )。

A．O(n2) B．O (nlog2n) *C．O(n) D．O (log2n)

7．用折半查找法对具有n个结点的线性表查找的时间复杂度量级为( )。

A．O(n2) B．O(nlog2n) C．O(n) *D．O(log 2n)

8．设哈希函数为H(key)=key％7，一组关键字为(37，21，9，20，30，19，46)，哈希表T的地址空间为0..6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为( )。 A． 0 1 2 3 4 5 6 21 20 37 9 46 30 19 *B． 0 1 2 3 4 5 6 21 46 37 9 30 19 20 C． 0 1 2 3 4 5 6 21 19 9 37 30 46 20 D．0 1 2 3 4 5 6 20 37 30 21 46 19 9

9．设有一个用线性探测法解决冲突得到的哈希表：

0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14

哈希函数为H(key)=key％11，若要查找元素14，探测的次数是( )。 A．3 *B．6 C．7 D．9

10．在哈希函数H(key)=key％m中，一般来讲，m应取( )。 A．奇数 B．偶数 *C．素数 D．充分大的数

11．在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为( )。

*A．O(n) B．O(1) C．O(log2n) D．O(n2)

12．有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列( )输入序列。

A．45，12，49，6，40，56，32 *B．40，12，6，32，49，45，56 C．6，12，32，13，45，49，56 D．32，12，6，40，45，56，49

14．在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为( )。

A．n B．log2n C．(h+1)／2 *D．h

二、判断题

√1．分块查找方法的平均查找长度低于顺序查找，高于折半查找。 ╳2．前序遍历二叉排序树的结点就可以得到排好序的结点序列。 ╳3．虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。

√4．对两棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。

√5．在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。

╳6．在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。 三、填空题

1．二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值__大_于其左孩子(及其子孙)的键值且__小__于其右孩子(及其子孙)的键值。

2．在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值__大__的结点，只需通过结点x的右指针到它的右子树中去找。 3．中序遍历一棵二叉排序树所得到的结点访问序列是键值的___递增__序列。

4．二叉排序树上的查找长度不仅与__元素个数_有关，也与二叉排序树的__输入序列__有关。

5．二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵单支树时，查找算法退化为__顺序___查找，平均查找长度上升为__（n+1）/2__。

6．__散列__查找法的平均查找长度与元素个数n无关。

7．折半查找方法仅适用于这样的表：表中的记录必须__有序__，其存储结构必须是__顺序存储___。

8．考虑具有如下性质的二叉树：除叶结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9-1所示的二叉树中，并使之满足上述性质(圆圈旁边的数字表示插入结点的序号)。

四、应用题

1．已知有长度为9的表(16,29,32,5,89,41,14,65,34)，它们存储在一个0-11的哈希表中，哈希函H(key)=key，利用线性探测再散列法 (1)将数据填入到哈希表中。 (2)计算查找成功时的平均查找长度。 答： (1) 0 1

(4)ASL=(1+2+1+1+2+1+1+1+2)/9=12/9=4/3

2．设有一组关键字(19，05，21，24，45，20，68，27，70，11，10)，用哈希函数H(key)=key％13，采用线性探测再散列方法解决冲突，试在0—14的散列地址空间中对该关键字序列构造哈希函数，并求查找成功的平均查找长度。 答： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 89 1 2 34 2 3 14 1 4 5 16 1 6 5 2 7 29 1 8 41 1 9 10 32 1 11 65 2 27 68 05 19 45 21 20 70 24 11 10 1 1 1 1 2 1 3 6 1 2 4 查找成功ASL=（1+1+1+1+2+1+3+6+1+2+4）/11=23/11

3．线性表的关键字集合(47，26，120，08，39，68，96，23，70，63，57)，已知散列函数为H(key)=key％13，采用链地址法处理冲突。设计出这种链表结构，并计算该表的查找成功平均查找长度。 答：图略。

查找成功ASL=(1*6+2*4+3*1)/11=17/11

本文来源：https://www.bwwdw.com/article/qnnv.html