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