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