2011年软考程序员考试复习笔试知识点整理(4)3

 　　8、查找(search)

　　先弄清楚以下几个概念：关键字、主关键字、次关键字的含义;静态查找与动态查找的含义及区别;平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，应该记住。

　　一般将search分为三类：在顺序表上的查找;在树表上的查找;在哈希表上的查找。

　　(1) 线性表上的查找：

　　主要分为三种线性结构：

　　顺序表--传统查找方法：逐个比较;

　　有序顺序表--二分查找法(注意适用条件以及其递归实现方法);

　　索引顺序表--对索引结构，采用索引查找算法。注意这三种表下的ASL值以及三种算法的实现。

　　(2) 树表上的查找：

　　树表主要分为以下几种：二叉排序树(即二叉查找树)，平衡二叉查找树(AVL树)，B树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树。

　　二叉排序树，简言之，就是"左小右大"，它的中序遍历结果是一个递增的有序序列。平衡二叉排序树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡排序二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，"判断某棵二叉树是否二叉排序树"这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。

　　B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。除B树的查找算法外，应该特别注意一下B树的插入和删除算法，因为这两种算法涉及到B树结点的分裂和合并，是一个难点。 键树(keywordtree)，又称数字搜索树(digitalsearch tree)或字符树。trie树也可说等同于键树或属于键树的一种。键树特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。

　　(3) 基于哈希表的查找算法：

　　哈希译自"hash"一词，意为"散列"或"杂凑"。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。