8、查找(search)

　　先弄清楚以下幾個概念：關鍵字、主關鍵字、次關鍵字的含義;靜態查找與動態查找的含義及區別;平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。

　　一般將search分為三類：在順序表上的查找;在樹表上的查找;在哈希表上的查找。

　　(1) 線性表上的查找：

　　主要分為三種線性結構：

　　順序表——傳統查找方法：逐個比較;

　　有序順序表——二分查找法(注意適用條件以及其遞歸實現方法);

　　索引順序表——對索引結構，采用索引查找算法。注意這三種表下的ASL值以及三種算法的實現。

　　(2) 樹表上的查找：

　　樹表主要分為以下幾種：二叉排序樹(即二叉查找樹)，平衡二叉查找樹(AVL樹)，B樹，鍵樹。其中，尤以前兩種結構為重，也有部分名校偏愛考B樹的。由于二叉排序樹與平衡二叉樹是一種特殊的二叉樹。

　　二叉排序樹，簡言之，就是“左小右大”，它的中序遍歷結果是一個遞增的有序序列。平衡二叉排序樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡排序二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。對于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個常考點，但該知識點歸根結底還是關注的平衡二叉樹的四種調整算法，調整的一個參照是：調整前后的中序遍歷結果相同。

　　B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找算法外，應該特別注意一下B樹的插入和刪除算法，因為這兩種算法涉及到B樹結點的分裂和合并，是一個難點。 鍵樹(keywordtree)，又稱數字搜索樹(digitalsearch tree)或字符樹。trie樹也可說等同于鍵樹或屬于鍵樹的一種。鍵樹特別適用于查找英文單詞的場合。一般不要求能完整描述算法源碼，多是根據算法思想建立鍵樹及描述其大致查找過程。

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

　　哈希譯自“hash”一詞，意為“散列”或“雜湊”。哈希表查找的基本思想是：根據當前待查找數據的特征，以記錄關鍵字為自變量，設計一個function，該函數對關鍵字進行轉換后，其解釋結果為待查的地址。基于哈希表的考查點有：哈希函數的設計，沖突解決方法的選擇及沖突處理過程的描述。

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)