u 散列表的查找

　　散列表又稱雜湊表，是一種非常實用的查找技術。它的原理是在結點的存儲位置和它的關鍵碼間建立一個確定的關系，從而讓查找碼直接利用這個關系確定結點的位置。其技術的關鍵在于解決兩個問題。

　　I. 找一個好的散列函數

　　II. 設計有效解決沖突的方法

　　常見的散列函數有：

　　I. 質數除取余法

　　II. 基數轉換法

　　III. 平方取中法

　　IV. 折疊法

　　V. 移位法

　　常見的解決沖突的方法有：

　　I. 線性探查法

　　II. 雙散列函數法

　　III. 拉鏈法

　　假設HASH表的地址集為0-n-1，沖突是指由關鍵字得到的HASH地址的位置上已經存在記錄，則處理沖突就是為該關鍵字的記錄找到另一個空的HASH地址用于存放。

　　處理沖突的方法：

　　開放地址法(線性探查法)：二次地址=(一次地址+增量序列) MOD 散列表長度M

　　再HASH法(雙散列函數法)：使用不同的散列函數計算，互相作為補償;

　　二次地址=RH(key) R和H都是散列函數

　　拉鏈法(鏈地址法)：設立一個指針數組，初始狀態是空指針，HASH地址為i的記錄都插入到指針數組中第i項所指向的鏈表中，保持關鍵字有序。

　　建立一個公共的溢出區：將所有沖突的關鍵字和記錄都添入到溢出區。

　　HASH查找分析： HASH的查找長度與查找表的長度無關，只與裝添因子有關

　　裝添因子=表中添入的記錄數/HASH的長度

　　4. 重點、難點解析

　　數據結構的相關知識點在軟考中是經常出現的，無論是上午的客觀題，還是下午的程序填空，都會涉及，而且考試的題型除了一般的概念和常識以外，還涉及各種算法，出題十分靈活。因此對這部分的復習一定要非常重視。這里我們總結了數據結構部分的一些比較重要的要點。

　　n 鏈式存儲結構

　　不管是線性表、棧，還是隊列，都會使用鏈式存儲結構。對于鏈式存儲結構的操作與順序存儲結構不一樣，因此我們需要熟悉它們的相關算法。如：

　　u 對于鏈式存儲的線性表，它的插入、刪除和查找算法。

　　u 對于鏈接存儲棧，它的進棧、出棧算法

　　u 對于鏈接存儲隊列，它的進隊、出隊算法

　　另外，對于棧和隊列的一些實際應用的算法也需要關心，特別在下午的程序填空的考試中，經常會碰到類似的算法。

　　關于圖的概念和相關算法很多，這對高程軟考來說，也是一個重點。

　　除了我們前面羅列的一些關于的圖的基本概念以外，首先我們必須對圖的幾種存儲結構要十分的清楚，因為這實際上是研究圖的相關問題和算法的基礎。包括：

　　u 鄰接矩陣

　　u 鄰接表

　　u 十字鏈表

　　u 鄰接多重表

　　對于圖的兩種遍歷算法(深度優先和廣度優先)實際可以參考樹的有關遍歷算法，這樣理解起來相對簡單。

　　而對于圖的有關算法，如求最小代價生成樹、求最短路徑、拓撲排序和求關鍵路徑等，這是數據結構中的難點。不過一般來說，軟考中很難直接考到。因此，大家在復習的時候主要抓住涉及算法的相關概念、算法的基本原理以及算法的復雜度這幾個方面。當然，有時間最好參看一下相關資料，對它的具體實現仔細看看，這對理解其算法的核心思想當然會事半功倍。

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總