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