第9章查找 西南交通大学,数据机构,课件

第九章查找
一、单选题
1.顺序查找法适合于存储结构为【】的查找表。

A.散列存储
B.顺序存储或链式存储
C.压缩存储
D.索引存储
2.对查找表进行折半查找时，要求查找表必须【】。

A.以顺序方式存储
B.以顺序方式存储，且结点按关键字有序排列
C.以链式方式存储
D.以链式方式存储，且结点按关键字有序排列
3.采用顺序查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【】。

A.n
B.n/2
C.(n+1)/2
D.(n-1)/2
4.采用折半查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【】。

A.O(n2)
B.O(nlog2n)
C.O(n)
D.O(log2n)
5.采用分块查找时，若查找表中有625个元素，查找每个元素的概率相同，假设对索引表和块都采用顺序查找，每块应分【】个结点最佳。

A.10
B.25
C.6
D.625
6.查找n个元素的有序表时，最有效的查找方法是【】。

A.顺序查找
B.分块查找
C.折半查找
D.二叉排序树
7.如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用【】查找方法。

A.分块
B.顺序
C.折半
D.散列
8.在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【】量级相当。

A.顺序查找
B.折半查找
C.分块查找
D.前三个都不正确
9.查找效率最高的二叉排序树是【】。

A.所有结点的左子树都为空的二叉排序树
B.所有结点的右子树都为空的二叉排序树
C.平衡二叉树
D.没有左子树的二叉排序树
10.假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字的记录插入到散列表中，至少要进行【】次探测。

A.k-1
B.k
C.k=1
D.k(k+1)/2
11.以下说法错误的是【】。

A.散列法存储的基本思想是由记录关键字决定数据存储地址
B.散列法的结点中只包含数据元素自身的信息，不包含任何指针
C.装填因子是散列法的一个重要参数，它反映了散列表的装填程度
D.散列表的查找效率取决于散列造表的散列函数和冲突处理的方法
12.散列表的平均查找长度【】。

A.与冲突处理方法有关而与表的长度无关
B.与冲突处理方法无关而与表的长度有关
C.与冲突处理方法有关且与表的长度有关
D.与冲突处理方法无关且与表的长度无关
二、判断题
【】1.顺序查找法适合于顺序或链式存储结构的查找表。

【】2.顺序查找法只能在顺序存储结构上进行。

【】3.二分查找可以在有序的双向链表上进行。

【】4.在二叉排序树中，每个结点的关键字比左孩子的关键字大，比右孩子的关键字小。

【】5.每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都是二叉排序树。

【】6.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。

【】7.哈希冲突是指同一个关键字对应多个不同的哈希地址。

三、填空题
1.顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为次；若查找不成功，则比较关键字的次数为次。

2.在含有n个元素的有序顺序表中进行二分查找，最多的比较次数是。

3.用二分查找一个查找表，该查找表必须具有的特点是。

4.分块查找法将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间。

5.在分块查找方法中，首先查找，然后再查找相应的。

6.用二叉排序树在n个元素中进行查找，最坏情况下查找时间复杂度为，最好情况的查找时间复杂度为。

7.折半查找的存储结构仅限于，且是。

8.一个无序序列可以通过构造一棵树而变成有序序列，构造树的过程即是对无序序列进行排序的过程。

9.用二叉排序树查找，在最坏的情况下，平均查找长度为，最好的情况下，平均查找长度为。

10.在哈希函数H(key)=key%p中，p最好取。

11.哈希表是通过将关键字按选定的和，把记录按关键字转换为地址进行存储的存储表，哈希方法的关键是和。

一个好的哈希函数其转换地址应尽可能，而且函数运算应尽可能。

四、解答题
1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

2、设有数据集合d={1，12，5，8，3，10，7，13，9}，回答下列问题：
①依次取d中各数据，构造一棵二叉排序树bt；
②如何依据此二叉排序树得到d的一个有序序列。

3.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列两种情况下分别讨论两者在等概率时的平均查找长度：
①查找不成功，即表中无关键字等于给定值k的记录。

②查找成功，即表中有关键字等于给定值k的记录。