2011年軟考程序員考試復(fù)習(xí)筆試知識點整理(4)

　　8、查找(search)

　　先弄清楚以下幾個概念：關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義;靜態(tài)查找與動態(tài)查找的含義及區(qū)別;平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結(jié)果，特別是一些典型結(jié)構(gòu)的ASL值，應(yīng)該記住。

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

　　(1) 線性表上的查找：

　　主要分為三種線性結(jié)構(gòu)：

　　順序表——傳統(tǒng)查找方法：逐個比較;

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

　　索引順序表——對索引結(jié)構(gòu)，采用索引查找算法。注意這三種表下的ASL值以及三種算法的實現(xiàn)。

　　(2) 樹表上的查找：

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

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

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

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

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

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

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

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