? 线性表查找的方法：顺序查找：逐个查找，ASL=？;二分查找：取中点int比较，若小就比左区间，大就比右区间。用二叉判定树
表示。ASL=？;分块查找：要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表。
? 二叉排序树定义是二叉排序树是空树或者满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的
值;若它的右子树非空，则右子树上所有结点的值均大于根结点的值;左、右子树本身又是一棵二叉排序树。
?
? 二叉排序树的插入、建立、删除的算法平均时间性能是O？。 二叉排序树的删除操作可分三种情况进行处理：*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。
*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p。*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。
?
? 关于B-树。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。 散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。常见的散列
函数构的造方法：平方取中法,除余法,相乘取整法,随机数法。
? 处理冲突的方法：开放定址法：一般形式为?，开放定址法要求散列表的装填因子α≤1。开放定址法类型：线性探查法，二次探查
法，双重散列法。拉链法：是将所有关键字为同义词的结点在同一个单链表中。
? 拉链法的优点：拉链法处理冲突简单，且无堆积现象;链表上的结点空间是动态申请的适于无法确定表长的情况;拉链法中α可以大
于1，结点较大时其指针域可忽略，因此节省空间;拉链法构造的散列表删除结点易实现。
? 拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。