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