七、查找
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)
{
}