数据结构与算法（test3）

七、查找

1. 看图填空

查找表是由同一类型的数据元素（或记录）构成的集合。例如上图就是一个查找表。

期中（1）是______________. (2)是______________(3)是_____关键字_______。

2. 查找(Searching) 就是根据给定的某个值,  在查找表中确定一个其____________等于给定值的_______________。

3. 列出常见的三种查找算法:______________、______________、______________。

4. ___________又叫线性查找, 是最基本的查找技术，它的查找过程是: 从表中第一个(或最后1个)记录开始，

逐个进行记录的_________与给定值比较，一直到找到相等的记录，它的时间复杂度是_____________。

它对表中记录是否有序___________（有 / 没有）要求。

5. ___________又称为二分查找，它的前提是线性表中的记录必须是________________, 线性表必须采用__________存储。它的时间复杂度是_____________。

6. ___________查找，是把数据集的记录分成若干块，并且这些块需要满足两个条件:

(1). 块内的记录特点:____________________________________。

(2). 块间的记录特点:____________________________________。

7. 二叉排序树，又称为二叉查找树，它或者是一棵空树，或者是具有下列性质:

(1). 若它的左子树不空, 则左子树上所有结点的值均小于它的_____结点的值。

(2). 若它的右子树不空, 则右子树上所有结点的值均大于它的_____结点的值。

(3). 它的左、右子树也分别为_________树。

它的时间复杂度是________________.

8. 二叉排序树是以____________方式存储，这种存储结构在执行插入、删除时不用移动元素的优点。找到合适的插入、删除位置后，仅需要修改__________即可。

9. 散列技术是在记录的_________和它的__________之间建立一个确定的对应关系f, 使得每个_________对应一个存储位置f(key)。

查找时，根据这个确定的对应关系找到给定值key的映射 f(key), 若查找集合中存在这个记录，则必定在f(key)的位置上。

这里我们把对应关系f 称为_________函数，又称为______函数。

采用散列技术将记录存储在一块地址___________的存储空间中，这块连续的存储空间称为______表或_____表。关键字对应的记录位置我们称为_______地址。

10. 散列技术即是一种存储方法，也是一种查找方法，它的时间复杂度是________________。

11. 散列表查找，如果没有冲突，它的效率很高，它的时间复杂度是________。可惜，没有冲突的散列只是一种理想，在实际的应用中，冲突是不可避免的，他的平均查找性能，取决于以下3个因素。

(1) 散列函数的好坏直接影响着出现冲突的频繁程度，它的主要指标是_______________。

(2）处理冲突的方法____________________。

(3) 散列表的装填因子。请解释装填因子是什么_____________________________________。

12. 给定一个长度为n的整形数组 int data[n],  它的数据以按从小到大排序。请用折半查找法，

完成以下函数，要求： 如果查找到目标数据target，则返回所在位置的数组下标，否则返回-1.

int findIndex(int data[], int size, int target)

{

}