在這個系列的一和二中，我們分別從題型結構，統(tǒng)考預測，考查范圍等宏觀上給大家解析了統(tǒng)考大綱，接下來我們會從各科的知識點著手來解析一下統(tǒng)考大綱。09年的統(tǒng)考大綱對數(shù)據(jù)結構的考查目標定位為理解數(shù)據(jù)結構的基本概念，掌握數(shù)據(jù)的邏輯結構、存儲結構及其差異，以及各種基本操作的實現(xiàn)；掌握基本的數(shù)據(jù)處理原理和方法的基礎上，能夠對算法進行設計與分析；能夠選擇合適的數(shù)據(jù)結構和方法進行問題求解。這個考查目標跟以往各個學校的考研大綱的考查目標并沒有什么實質性的區(qū)別，這說明數(shù)據(jù)結構科目考查的指導思想并沒有發(fā)生變化，同學們可以在不影響已有復習成果的基礎上繼續(xù)進行復習計劃，只是在數(shù)據(jù)結構的考點有了些調整。但是數(shù)據(jù)結構的考試內容只是羅列出來，并沒有詳細的解析，在這里就數(shù)據(jù)結構的考點來進行解析一下。
緒論一章沒有出現(xiàn)在大綱的考察范圍，但是把握了這章有助于對整個課程知識的理解。因此建議大家還是要把這一章復習一下。這一章中的考點及對其掌握程度如下：
數(shù)據(jù)結構的基本概念
識記
數(shù)據(jù)的邏輯結構和存儲結構，對后面的名詞要能區(qū)分哪些是屬于邏輯結構哪些屬于物理結構
掌握
時間和空間復雜度的概念及度量方法
理解
算法設計時的注意事項
了解
線性表一章在線性結構的學習乃至整個數(shù)據(jù)結構學科的學習中其作用都是非常重要的。在這一章，第系統(tǒng)性地引入鏈式存儲的概念，鏈式存儲概念將是整個數(shù)據(jù)結構學科的重中之重，無論哪一章都涉及到了這個概念，所以一定搞透徹了。
線性表相關的基本概念，如：前驅、后繼、表長、空表、首元結點，頭結點，頭指針等概念
識記
線性表的結構特點
識記
線性表的順序存儲方式以及兩種不同的實現(xiàn)方法：表空間的靜態(tài)分配和動態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處
掌握
線性表的鏈式存儲方式的實現(xiàn)，幾種常用鏈表的特點和運算：單鏈表、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表
掌握
線性表的順序存儲及鏈式存儲情況下，其不同的優(yōu)缺點比較，即其各自適用的場合
理解
單鏈表中設置頭指針、循環(huán)鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處
理解
對于線性表的各種實現(xiàn)方式能夠實現(xiàn)指定的操作，尤其是各種線性鏈表的插入，刪除（刪除自己，還是刪除后繼結點），判表空等
掌握
棧，隊列和數(shù)組都屬于線性結構的拓展，棧和隊列是操作受限的線性表，數(shù)組是數(shù)據(jù)元素是非原子類型的線性表。大家在復習這一章的時候一定要注意對棧和隊列的靈活運用，數(shù)組這一張要注意特殊矩陣壓縮方面的題目。
棧、隊列的定義及其相關數(shù)據(jù)結構的概念，包括：順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊等
識記
棧與隊列插入刪除操作的特點，棧和隊列的特點
理解
遞歸算法，棧和遞歸的關系，把遞歸算法轉換為用棧來實現(xiàn)的非遞歸算法
掌握
棧的應用
了解
棧和隊列各種實現(xiàn)方式的運算
理解
循環(huán)隊列中判隊空、隊滿條件，循環(huán)隊列中入隊與出隊算法
掌握
判循環(huán)隊列是空還是滿的兩種處理方法
理解
數(shù)組的定義以及如何理解它們是線性表的擴展
識記
數(shù)組除了初始化和銷毀之外只能進行存取和修改操作
識記
多維數(shù)組中某數(shù)組元素的position求解（不管是按行存儲和按列存儲）：一般是給出數(shù)組元素的首元素地址和每個元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置
掌握
特殊矩陣和稀疏矩陣的定義
了解
特殊矩陣的壓縮，包括對稱矩陣，上（下）三角矩陣，對角矩陣，具有某種特點的稀疏矩陣等
掌握
稀疏矩陣的三種不同實現(xiàn)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲
理解
對稀疏矩陣各種實現(xiàn)方式的轉置和相乘運算的操作及復雜性分析
理解
樹和二叉樹歷來都是考試的重難點章節(jié)，從這章開始就從對線性結構的研究過渡到對樹形結構的研究，這一章學習的好壞直接關系到在數(shù)據(jù)結構這門考試中能否能得高分。因此這一章大家對每個知識點都要吃透過關。要注意這章的算法設計類題目。
二叉樹的概念，二叉樹的五種基本形態(tài)。比如可以考這么個題目判斷二叉樹就是度為２的有序樹對否。
理解
二叉樹的五個性質，尤其是性質３和性質４
掌握
二叉樹的存儲結構：順序存儲和二叉鏈表存儲的各自優(yōu)缺點及適用場合，二叉樹的三叉鏈表表示方法
掌握
二叉樹的三種遍歷方法：先序，中序和后序。其劃分的依據(jù)是視其每個算法中對根結點數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實際步驟，并且應該熟練掌握三種遍歷的非遞歸算法。
熟練掌握
在三種遍歷算法的基礎上改造完成的其它二叉樹算法，比如求葉子個數(shù)，求二叉樹結點總數(shù)，求度為1或度為2的結點總數(shù)，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。
熟練掌握
線索二叉樹：線索化的實質，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結點的前驅或后繼結點就是一類常考題），會計算針對某個二叉樹在采用不同的線索化方法后剩余空鏈域的個數(shù)
掌握
哈夫曼樹，也叫優(yōu)二叉樹。什么樣的編碼是哈夫曼編碼。一般很少考哈夫曼編碼的算法，能夠利用算法構造哈夫曼樹并求出小帶權路徑長度即可。還有一個樹的應用：等價類問題。
掌握
樹的存儲表示方法，樹與森林轉化為二叉樹，樹和森林的遍歷問題，樹的計數(shù)，二叉樹的相似與等價
掌握
回溯法
理解
圖這一章是每年考試必考的章節(jié)，這一張里面處處都是重點。
圖的基本概念：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，（強）連通圖，（強）連通分量等概念。與這些概念相聯(lián)系的相關計算題也應該掌握
識記
掌握
圖的幾種存儲形式，尤其是鄰接矩陣和鄰接表
掌握
圖的兩種遍歷算法：深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹一章的重要性。在考查時，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的，比如：“求長的短路徑問題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。
熟練掌握
生成樹、小生成樹的概念以及小生成樹的構造：PRIM算法和KRUSKAL算法，要掌握這兩個算法的基本思想?？疾闀r，一般不要求寫出算法源碼，而是要求根據(jù)這兩種小生成樹的算法思想寫出其構造過程及終生成的小生成樹
掌握
拓撲排序問題：拓撲排序有兩種方法，一是無前趨的頂點優(yōu)先算法，二是無后繼的頂點優(yōu)先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。當然，后一種排序出來的結果是“逆拓撲有序”的。
掌握
關鍵路徑問題：這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：一是何謂關鍵路徑，二是早時間是什么意思、如何求，三是晚時間是什么意思、如何求。簡單地說，早時間是通過“從前向后”的方法求的，而晚時間是通過“從后向前”的方法求解的，并且，要想求晚時間必須是在所有的早時間都已經(jīng)求出來之后才能進行。這個問題拿來直接考算法源碼的不多，一般是要求按照書上的算法描述求解的過程和步驟
掌握
短路徑問題：與關鍵路徑問題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是算法的理解。短路徑問題分為兩種：一是求從某一點出發(fā)到其余各點的短路徑；二是求圖中每一對頂點之間的短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是旅游景點及旅游路線的選擇問題。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法。這個算法的要求就是要會用算法求解短路徑
掌握
查找一章是考試的重點難點章節(jié)，概念較多，聯(lián)系較為緊密，容易混淆。大家在復習這一章要學會分類和對比相結合來進行復習。
關鍵字、主關鍵字、次關鍵字的含義；靜態(tài)查找與動態(tài)查找的含義及區(qū)別；平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。要會計算各種查找方法在查找成功和查找不成功時平均查找長度的計算
識記
掌握
線性表上的查找：主要分為三種線性結構：順序表，有序順序表，索引順序表。對于第一種，我們采用傳統(tǒng)查找方法，逐個比較。對于及有序順序表我們采用二分查找法。對于第三種索引結構，我們采用索引查找算法?？忌枰⒁膺@三種表下的ASL值以及三種算法的實現(xiàn)。其中，二分查找還要特別注意適用條件以及其遞歸實現(xiàn)方法
掌握
樹表上的查找：這是本章的重點和難點。由于這一節(jié)介紹的內容是使用樹表進行的查找，所以很容易與樹一間的某些概念相混淆。本節(jié)內容與樹一章的內容有聯(lián)系，但也有很多不同，應注意規(guī)納。樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。其中，尤以前兩種結構為重，有時候也會考查Ｂ樹，但是以選擇為主，很少會考大題。由于二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯(lián)系就更為緊密，二叉樹一章學好了，這里也就不難了。
二叉排序樹，簡言之，就是“左小右大”，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優(yōu)化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。對于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個?？键c，但該知識點歸根結底還是關注的平衡二叉樹的四種調整算法，所以應該掌握平衡二叉樹的四種調整算法，調整的一個參照是：調整前后的中序遍歷結果相同。
B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找算法外，應該特別注意一下B樹的插入和刪除算法。因為這兩種算法涉及到B樹結點的分裂和合并，是一個難點（沒有時間可以不看）。
鍵樹也稱字符樹，特別適用于查找英文單詞的場合。一般不要求能完整描述算法源碼，多是根據(jù)算法思想建立鍵樹及描述其大致查找過程。
熟練掌握
基本哈希表的查找算法：哈希一詞，是外來詞，譯自“hash”一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據(jù)當前待查找數(shù)據(jù)的特征，以記錄關鍵字為自變量，設計一個function，該函數(shù)對關鍵字進行轉換后，其解釋結果為待查的地址。基于哈希表的考查點有：哈希函數(shù)的設計，沖突解決方法的選擇及沖突處理過程的描述。
熟練掌握
與查找一章類似，內部排序也屬于重點難點章節(jié)，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序算法的優(yōu)劣比較此類的題。算法設計大題中，如果作為出題，那么常與數(shù)組結合來考查。其實這一章主要是考查你對書本上的各種排序算法及其思想以及其優(yōu)缺點和性能指標(時間復雜度)能否了如指掌。從排序算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計數(shù)等五種排序方法。
在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的根本的不同點，說到底就是根據(jù)什么規(guī)則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實現(xiàn)排序效率提高的目的。
掌握
交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序?？焖倥判虻乃枷?，一語以敝之：用中間數(shù)將待排數(shù)據(jù)組一分為二?？焖倥判?，在處理的“問題規(guī)?！边@個概念上，與希爾有點相反，快速排序，是先處理一個較大規(guī)模，然后逐漸把處理的規(guī)模降低，終達到排序的目的。
掌握
選擇排序，相對于前面幾種排序算法來說，難度大一點。具體來說，它可以分為：簡單選擇、樹選擇、堆排。這三種方法的不同點是，根據(jù)什么規(guī)則選取小的數(shù)。簡單選擇，是通過簡單的數(shù)組遍歷方案確定小數(shù)；樹選擇，是通過“錦標賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大（小）者，終選出?。ù螅?shù)；而堆排序，是利用堆這種數(shù)據(jù)結構的性質，通過堆元素的刪除、調整等一系列操作將小數(shù)選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。
熟練掌握
歸并排序，故名思義，是通過“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實現(xiàn)歸并。所以，在歸并排序中，關注多的就是2路歸并。算法思想比較簡單，有一點，要銘記在心：歸并排序是穩(wěn)定排序。
熟練掌握
基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場合，比如撲克牌排序問題等?；鶖?shù)排序，又分為兩種：多關鍵字的排序（撲克牌排序），鏈式排序（整數(shù)排序）?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進行關鍵字比較的，這樣得出的終序列就是一個有序序列
掌握
緒論一章沒有出現(xiàn)在大綱的考察范圍，但是把握了這章有助于對整個課程知識的理解。因此建議大家還是要把這一章復習一下。這一章中的考點及對其掌握程度如下：
數(shù)據(jù)結構的基本概念
識記
數(shù)據(jù)的邏輯結構和存儲結構，對后面的名詞要能區(qū)分哪些是屬于邏輯結構哪些屬于物理結構
掌握
時間和空間復雜度的概念及度量方法
理解
算法設計時的注意事項
了解
線性表一章在線性結構的學習乃至整個數(shù)據(jù)結構學科的學習中其作用都是非常重要的。在這一章，第系統(tǒng)性地引入鏈式存儲的概念，鏈式存儲概念將是整個數(shù)據(jù)結構學科的重中之重，無論哪一章都涉及到了這個概念，所以一定搞透徹了。
線性表相關的基本概念，如：前驅、后繼、表長、空表、首元結點，頭結點，頭指針等概念
識記
線性表的結構特點
識記
線性表的順序存儲方式以及兩種不同的實現(xiàn)方法：表空間的靜態(tài)分配和動態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處
掌握
線性表的鏈式存儲方式的實現(xiàn)，幾種常用鏈表的特點和運算：單鏈表、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表
掌握
線性表的順序存儲及鏈式存儲情況下，其不同的優(yōu)缺點比較，即其各自適用的場合
理解
單鏈表中設置頭指針、循環(huán)鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處
理解
對于線性表的各種實現(xiàn)方式能夠實現(xiàn)指定的操作，尤其是各種線性鏈表的插入，刪除（刪除自己，還是刪除后繼結點），判表空等
掌握
棧，隊列和數(shù)組都屬于線性結構的拓展，棧和隊列是操作受限的線性表，數(shù)組是數(shù)據(jù)元素是非原子類型的線性表。大家在復習這一章的時候一定要注意對棧和隊列的靈活運用，數(shù)組這一張要注意特殊矩陣壓縮方面的題目。
棧、隊列的定義及其相關數(shù)據(jù)結構的概念，包括：順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊等
識記
棧與隊列插入刪除操作的特點，棧和隊列的特點
理解
遞歸算法，棧和遞歸的關系，把遞歸算法轉換為用棧來實現(xiàn)的非遞歸算法
掌握
棧的應用
了解
棧和隊列各種實現(xiàn)方式的運算
理解
循環(huán)隊列中判隊空、隊滿條件，循環(huán)隊列中入隊與出隊算法
掌握
判循環(huán)隊列是空還是滿的兩種處理方法
理解
數(shù)組的定義以及如何理解它們是線性表的擴展
識記
數(shù)組除了初始化和銷毀之外只能進行存取和修改操作
識記
多維數(shù)組中某數(shù)組元素的position求解（不管是按行存儲和按列存儲）：一般是給出數(shù)組元素的首元素地址和每個元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置
掌握
特殊矩陣和稀疏矩陣的定義
了解
特殊矩陣的壓縮，包括對稱矩陣，上（下）三角矩陣，對角矩陣，具有某種特點的稀疏矩陣等
掌握
稀疏矩陣的三種不同實現(xiàn)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲
理解
對稀疏矩陣各種實現(xiàn)方式的轉置和相乘運算的操作及復雜性分析
理解
樹和二叉樹歷來都是考試的重難點章節(jié)，從這章開始就從對線性結構的研究過渡到對樹形結構的研究，這一章學習的好壞直接關系到在數(shù)據(jù)結構這門考試中能否能得高分。因此這一章大家對每個知識點都要吃透過關。要注意這章的算法設計類題目。
二叉樹的概念，二叉樹的五種基本形態(tài)。比如可以考這么個題目判斷二叉樹就是度為２的有序樹對否。
理解
二叉樹的五個性質，尤其是性質３和性質４
掌握
二叉樹的存儲結構：順序存儲和二叉鏈表存儲的各自優(yōu)缺點及適用場合，二叉樹的三叉鏈表表示方法
掌握
二叉樹的三種遍歷方法：先序，中序和后序。其劃分的依據(jù)是視其每個算法中對根結點數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實際步驟，并且應該熟練掌握三種遍歷的非遞歸算法。
熟練掌握
在三種遍歷算法的基礎上改造完成的其它二叉樹算法，比如求葉子個數(shù)，求二叉樹結點總數(shù)，求度為1或度為2的結點總數(shù)，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。
熟練掌握
線索二叉樹：線索化的實質，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結點的前驅或后繼結點就是一類常考題），會計算針對某個二叉樹在采用不同的線索化方法后剩余空鏈域的個數(shù)
掌握
哈夫曼樹，也叫優(yōu)二叉樹。什么樣的編碼是哈夫曼編碼。一般很少考哈夫曼編碼的算法，能夠利用算法構造哈夫曼樹并求出小帶權路徑長度即可。還有一個樹的應用：等價類問題。
掌握
樹的存儲表示方法，樹與森林轉化為二叉樹，樹和森林的遍歷問題，樹的計數(shù)，二叉樹的相似與等價
掌握
回溯法
理解
圖這一章是每年考試必考的章節(jié)，這一張里面處處都是重點。
圖的基本概念：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，（強）連通圖，（強）連通分量等概念。與這些概念相聯(lián)系的相關計算題也應該掌握
識記
掌握
圖的幾種存儲形式，尤其是鄰接矩陣和鄰接表
掌握
圖的兩種遍歷算法：深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹一章的重要性。在考查時，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的，比如：“求長的短路徑問題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。
熟練掌握
生成樹、小生成樹的概念以及小生成樹的構造：PRIM算法和KRUSKAL算法，要掌握這兩個算法的基本思想?？疾闀r，一般不要求寫出算法源碼，而是要求根據(jù)這兩種小生成樹的算法思想寫出其構造過程及終生成的小生成樹
掌握
拓撲排序問題：拓撲排序有兩種方法，一是無前趨的頂點優(yōu)先算法，二是無后繼的頂點優(yōu)先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。當然，后一種排序出來的結果是“逆拓撲有序”的。
掌握
關鍵路徑問題：這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：一是何謂關鍵路徑，二是早時間是什么意思、如何求，三是晚時間是什么意思、如何求。簡單地說，早時間是通過“從前向后”的方法求的，而晚時間是通過“從后向前”的方法求解的，并且，要想求晚時間必須是在所有的早時間都已經(jīng)求出來之后才能進行。這個問題拿來直接考算法源碼的不多，一般是要求按照書上的算法描述求解的過程和步驟
掌握
短路徑問題：與關鍵路徑問題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是算法的理解。短路徑問題分為兩種：一是求從某一點出發(fā)到其余各點的短路徑；二是求圖中每一對頂點之間的短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是旅游景點及旅游路線的選擇問題。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法。這個算法的要求就是要會用算法求解短路徑
掌握
查找一章是考試的重點難點章節(jié)，概念較多，聯(lián)系較為緊密，容易混淆。大家在復習這一章要學會分類和對比相結合來進行復習。
關鍵字、主關鍵字、次關鍵字的含義；靜態(tài)查找與動態(tài)查找的含義及區(qū)別；平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。要會計算各種查找方法在查找成功和查找不成功時平均查找長度的計算
識記
掌握
線性表上的查找：主要分為三種線性結構：順序表，有序順序表，索引順序表。對于第一種，我們采用傳統(tǒng)查找方法，逐個比較。對于及有序順序表我們采用二分查找法。對于第三種索引結構，我們采用索引查找算法?？忌枰⒁膺@三種表下的ASL值以及三種算法的實現(xiàn)。其中，二分查找還要特別注意適用條件以及其遞歸實現(xiàn)方法
掌握
樹表上的查找：這是本章的重點和難點。由于這一節(jié)介紹的內容是使用樹表進行的查找，所以很容易與樹一間的某些概念相混淆。本節(jié)內容與樹一章的內容有聯(lián)系，但也有很多不同，應注意規(guī)納。樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。其中，尤以前兩種結構為重，有時候也會考查Ｂ樹，但是以選擇為主，很少會考大題。由于二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯(lián)系就更為緊密，二叉樹一章學好了，這里也就不難了。
二叉排序樹，簡言之，就是“左小右大”，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優(yōu)化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。對于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個?？键c，但該知識點歸根結底還是關注的平衡二叉樹的四種調整算法，所以應該掌握平衡二叉樹的四種調整算法，調整的一個參照是：調整前后的中序遍歷結果相同。
B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找算法外，應該特別注意一下B樹的插入和刪除算法。因為這兩種算法涉及到B樹結點的分裂和合并，是一個難點（沒有時間可以不看）。
鍵樹也稱字符樹，特別適用于查找英文單詞的場合。一般不要求能完整描述算法源碼，多是根據(jù)算法思想建立鍵樹及描述其大致查找過程。
熟練掌握
基本哈希表的查找算法：哈希一詞，是外來詞，譯自“hash”一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據(jù)當前待查找數(shù)據(jù)的特征，以記錄關鍵字為自變量，設計一個function，該函數(shù)對關鍵字進行轉換后，其解釋結果為待查的地址。基于哈希表的考查點有：哈希函數(shù)的設計，沖突解決方法的選擇及沖突處理過程的描述。
熟練掌握
與查找一章類似，內部排序也屬于重點難點章節(jié)，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序算法的優(yōu)劣比較此類的題。算法設計大題中，如果作為出題，那么常與數(shù)組結合來考查。其實這一章主要是考查你對書本上的各種排序算法及其思想以及其優(yōu)缺點和性能指標(時間復雜度)能否了如指掌。從排序算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計數(shù)等五種排序方法。
在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的根本的不同點，說到底就是根據(jù)什么規(guī)則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實現(xiàn)排序效率提高的目的。
掌握
交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序?？焖倥判虻乃枷?，一語以敝之：用中間數(shù)將待排數(shù)據(jù)組一分為二?？焖倥判?，在處理的“問題規(guī)?！边@個概念上，與希爾有點相反，快速排序，是先處理一個較大規(guī)模，然后逐漸把處理的規(guī)模降低，終達到排序的目的。
掌握
選擇排序，相對于前面幾種排序算法來說，難度大一點。具體來說，它可以分為：簡單選擇、樹選擇、堆排。這三種方法的不同點是，根據(jù)什么規(guī)則選取小的數(shù)。簡單選擇，是通過簡單的數(shù)組遍歷方案確定小數(shù)；樹選擇，是通過“錦標賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大（小）者，終選出?。ù螅?shù)；而堆排序，是利用堆這種數(shù)據(jù)結構的性質，通過堆元素的刪除、調整等一系列操作將小數(shù)選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。
熟練掌握
歸并排序，故名思義，是通過“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實現(xiàn)歸并。所以，在歸并排序中，關注多的就是2路歸并。算法思想比較簡單，有一點，要銘記在心：歸并排序是穩(wěn)定排序。
熟練掌握
基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場合，比如撲克牌排序問題等?；鶖?shù)排序，又分為兩種：多關鍵字的排序（撲克牌排序），鏈式排序（整數(shù)排序）?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進行關鍵字比較的，這樣得出的終序列就是一個有序序列
掌握