《數(shù)據(jù)結(jié)構(gòu)》考研必須掌握的知識點與算法(總6頁)

《《數(shù)據(jù)結(jié)構(gòu)》考研必須掌握的知識點與算法(總6頁)》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)》考研必須掌握的知識點與算法(總6頁)（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 《數(shù)據(jù)結(jié)構(gòu)》必須掌握的知識點與算法 第一章 緒論 1、算法的五個重要特性（有窮性、確定性、可行性、輸入、輸出） 2、算法設計的要求（正確性、可讀性、健壯性、效率與低存儲量需求） 3、算法與程序的關(guān)系： （1）一個程序不一定滿足有窮性。例操作系統(tǒng)，只要整個系統(tǒng)不遭破壞，它將永遠不會停止，即使沒有作業(yè)需要處理，它仍處于動態(tài)等待中。因此，操作系統(tǒng)不是一個算法。 （2）程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在計算機上的特定的實現(xiàn)。 （3）一個算法若用程序設計語言來描述，則它就是一個程序。 4、算法的時間復雜度的表示與計算（這個

2、比較復雜，具體看算法本身，一般關(guān)心其循環(huán)的次數(shù)與N的關(guān)系、函數(shù)遞歸的計算） 第二章 線性表 1、線性表的特點： （1）存在唯一的第一個元素；（這一點決定了圖不是線性表） （2）存在唯一的最后一個元素； （3）除第一個元素外，其它均只有一個前驅(qū)（這一點決定了樹不是線性表） （4）除最后一個元素外，其它均只有一個后繼。 2、線性表有兩種表示：順序表示（數(shù)組）、鏈式表示（鏈表），棧、隊列都是線性表，他們都可以用數(shù)組、鏈表來實現(xiàn)。 3、順序表示的線性表（數(shù)組）地址計算方法： （1）一維數(shù)組，設DataType a[N]的首地址為A0，每一個數(shù)據(jù)（DataType類型）占m

3、個字節(jié)，則a[k]的地址為：Aa[k]＝A0+m*k（其直接意義就是求在數(shù)據(jù)a[k]的前面有多少個元素，每個元素占m個字節(jié)） （2）多維數(shù)組，以三維數(shù)組為例，設DataType a[M][N][P]的首地址為A000，每一個數(shù)據(jù)（DataType類型）占m個字節(jié)，則在元素a[i][j][k]的前面共有元素個數(shù)為：M*N*i+N*j+k，其其地址為： Aa[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、線性表的歸并排序： 設兩個線性表均已經(jīng)按非遞減順序排好序，現(xiàn)要將兩者合并為一個線性表，并仍然接非遞減順序?？梢娝惴?.2 5、掌握線性表的順序表示法定義代碼，各

4、元素的含義； 6、順序線性表的初始化過程，可見算法2.3 7、順序線性表的元素的查找。 8、順序線性表的元素的插入算法，注意其對于當原來的存儲空間滿了后，追加存儲空間（就是每次增加若干個空間，一般為10個）的處理過程，可見算法2.4 9、順序線性表的刪除元素過程，可見算法2.5 10、順序線性表的歸并算法，可見算法2.7 11、鏈表的定義代碼，各元素的含義，并能用圖形象地表示出來，以利分析； 12、鏈表中元素的查找 13、鏈表的元素插入，算法與圖解，可見算法2.9 14、鏈表的元素的刪除，算法與圖解，可見算法2.10 15、鏈表的創(chuàng)建過程，算法與圖解，注意，鏈表有兩種（

5、向表頭生長、向表尾生長，分別用在棧、隊列中），但他們的區(qū)別就是在創(chuàng)建時就產(chǎn)生了，可見算法2.11 16、鏈表的歸并算法，可見算法2.12 17、建議了解所謂的靜態(tài)單鏈表（即用數(shù)組的形式來實現(xiàn)鏈表的操作），可見算法2.13 18、循環(huán)鏈表的定義，意義 19、循環(huán)鏈表的構(gòu)造算法（其與單鏈表的區(qū)別是在創(chuàng)建時確定的）、圖解 20、循環(huán)鏈表的插入、刪除算法、圖解 21、雙向鏈表的定義，意義 22、雙向鏈表的構(gòu)造算法（其與單鏈表的區(qū)別是在創(chuàng)建時確定的）、圖解 23、雙向鏈表的插入、刪除算法、圖解，可見算法2.18、2.19 24、補充：在循環(huán)鏈表中，只設立一個表尾指針比只設立一個表頭

6、指針更方便些，為什么？ 第三章 棧和隊列 1、棧的順序表示與實現(xiàn) 2、棧的鏈表表示與實現(xiàn) 3、棧的入棧、出棧操作算法 4、棧的幾個經(jīng)典應用（迷宮、表達式求值） 5、棧與遞歸的實現(xiàn)，如Hanoi塔問題 6、隊列鏈式表示與實現(xiàn) 7、鏈式隊列的入隊、出隊操作算法 8、循環(huán)隊列的表示（順序表示）和實現(xiàn)，特別注意其判滿、判空方法、入隊操作、出隊操作的實現(xiàn)（特別重要，考得頻率很大） 9、補充：共享棧的方法與實現(xiàn)（即兩個棧共享一個空間，他們采用棧頂相向，迎面增長的存儲方式） 10、補充：用兩個棧來模擬一個隊列的思路、算法 11、補充：表達式（前綴、后綴、中綴）的表達互換，這個操作要求

7、對棧在表達式求值中的應用相當熟練，并要求對后面的二叉樹相當熟練 12、補充：了解雙端隊列（只需了解） 13、補充：鏈棧比順序棧的優(yōu)點與缺點 14、補充：一系列元素依次入棧再出棧的順序，經(jīng)典題目為：有5個元素，其入棧次序為A、B、C、D、E，以下哪種出棧的順序是不可能的？ 15、補充：了解用循環(huán)鏈表實現(xiàn)隊列，注意在該循環(huán)鏈表中只有一個頭指針或一個表尾指針（只需了解） 16、補充：根據(jù)給出的數(shù)學公式，寫出對應的遞歸算法，最經(jīng)典的就是用遞歸求階乘。 第六章 樹和二叉樹 1、幾個重要的概念：樹、森林、子樹、根、終端結(jié)點（葉子）、非終端結(jié)點、雙親、孩子、兄弟、堂兄弟、度、深度、有序樹、無序

8、樹、二叉樹、k叉樹、完全二叉樹、滿二叉樹、線索二叉樹； 2、二叉樹的5種基本形態(tài)； 3、二叉樹的5個重要性質(zhì)： （1）在二叉樹的第i層上至多有2i－1個結(jié)點（i≥1）； （2）深度為k的二叉樹至多有2k－1個結(jié)點，（k≥1） （3）對任何一棵二叉樹T，如果其終端結(jié)點（葉子）數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1； （4）具有n個結(jié)點的完全二叉樹的深度為； （5）如果對一棵有n個結(jié)點的完全二叉樹（其深度為）的結(jié)點按性層序編號（從第1層到第層，每層從左到右），則對任一結(jié)點i（1≤i≤n），有： （i）如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i>1,則其

9、雙親Parent（i）是結(jié)點 （ii）如果2i>n，則結(jié)點i無左孩子（結(jié)點i為葉子結(jié)點）；否則其左孩子LChild（i）是結(jié)點2i； （iii）如果2i+1>n，則結(jié)點i無右孩子；否則其右孩子RChild（i）是結(jié)點2i+1 利用完全二叉樹的上述性質(zhì)，能處理大多數(shù)完全二叉樹的計算題； 4、二叉樹的存儲結(jié)構(gòu)： （1）了解順序存儲結(jié)構(gòu)，只做了解； （2）鏈式存儲結(jié)構(gòu)，重要，需要掌握，后面的算法都是基于此結(jié)構(gòu)； 5、二叉樹的遍歷： （1）能對任意一棵二叉樹進行手動前序、中序、后序遍歷； （2）能將由前序+中序、后序+中序給出的序列還原成一棵二叉樹； （3）能將一

10、個數(shù)學表達式用中序方法將其用二叉樹畫出來，并能寫出其前綴（波蘭式）、中綴、后綴（逆波蘭式）表達出來； 6、二叉樹的遍歷遞歸算法（注意前、中、后序三個算法只有細微的差別），可見算法6.1，而他們的非遞歸算法不作要求； 7、建立二叉樹鏈表的遞歸算法，可見算法6.4； 8、線索二叉樹的存儲結(jié)構(gòu)圖； 9、能用手畫出任意二叉樹對應的線索二叉樹（中序、后序線索）； 10、線索二叉樹的非遞歸遍歷算法，可見算法6.5； 11、理解線索二叉樹的中序線索化過程算法，可見算法6.6； 12、手動寫出任意森林、樹的深度優(yōu)先、廣度優(yōu)先遍歷順序； 13、森林、二叉樹的轉(zhuǎn)換過程，能用手畫出即可； 14、哈

11、夫曼樹的相關(guān)概念：路徑長度、帶權(quán)路徑長度WPL、權(quán)值； 15、二叉哈夫曼樹的構(gòu)造過程，能用手動構(gòu)造，并能將構(gòu)造好的樹用編碼表示出來； 16、了解哈夫曼樹的構(gòu)造算法，可見算法6.12，只需要了解，無需掌握； 17、記住樹的記數(shù)公式：對一棵有n個結(jié)點的有棵不同的二叉樹 18、補充：二叉排序樹、插入、刪除結(jié)點的操作（在查找一章中有詳述）； 19、補充：滿二叉樹、完全二叉樹用數(shù)組存儲方式，其元素、結(jié)點對應關(guān)系； 20、補充：求二叉樹的高度（深度）算法； 21、補充：將二叉樹中左、右孩子交換的算法； 22、補充：將用數(shù)組存儲的完全二叉樹轉(zhuǎn)換成鏈式結(jié)構(gòu)的算法； 23、補充：對用數(shù)組存儲的

12、完全二叉樹進行非遞歸的前序、中序、后序遍歷算法； 24、補充：求二叉樹中葉子數(shù)、度為1的、度為2的結(jié)點數(shù)算法； 25、補充：對于K叉樹，其結(jié)點總數(shù)為N，求出該樹的最大高度、高小高度； 26、補充：構(gòu)造結(jié)點數(shù)為n的k叉哈夫曼樹（其所有的結(jié)點要么度為0，要么度為k），注意一般都需要增加m個權(quán)為0的結(jié)點（稱為虛結(jié)點），其中如果葉子結(jié)點數(shù)目不足以構(gòu)成正則的k叉樹（樹中只有度為k或0的結(jié)點），即不滿足(n-1)MOD(k-1)=0（其中MOD是取余運算），需要添加權(quán)為0的結(jié)點，添加的個數(shù)為m=k-(n-1)MOD(k-1)-1。添加的位置應該是距離根結(jié)點的最遠處。假設n=10，k=3，則需要添加1

13、個權(quán)為0的虛結(jié)點（其字母可以為空）。 第七章 圖 1、圖的幾個重要概念：頂點、弧、弧尾、弧頭、邊、有向圖、無向圖、完全圖、鄰接點、入度、出度、度、路徑、回路（環(huán)）、連通圖、連通分量、強連通圖、強連通分量、生成森林、關(guān)節(jié)點、重連通圖、AOV-網(wǎng)、AOE-網(wǎng)； 2、圖的幾種存儲、表示方法：數(shù)組表示法（重要）、鄰接表（最重要，應用最廣）、逆鄰接表（掌握）、十字鏈表（理解）、鄰接多重表（了解），并能大致掌握他們各種方法表示的優(yōu)缺點； 3、圖的兩種遍歷順序：深度、廣度優(yōu)先，建議同時掌握其算法； 4、圖的生成樹和生成森林（只需掌握手畫方法）； 5、圖的最小生成樹的兩種算法：普里姆（Prim）算

14、法（實質(zhì)是頂點優(yōu)先）、克魯斯卡爾（Kruskal）算法（實質(zhì)是邊優(yōu)先），掌握他們的手動構(gòu)造過程，了解算法； 6、理解求關(guān)節(jié)點算法，可見算法7.10、7.11； 7、了解拓撲排序； 8、掌握由AOE-網(wǎng)得到關(guān)鍵路徑的方法（手動），了解算法（7.13、7.14）； 9、掌握最短路徑的手動求解過程、方法（兩種：迪杰斯特拉Dijkstra、弗洛伊德Floyd），了解算法； 10、補充：Prim算法、Kruskal算法、Dijkstra算法、Floyd算法的時間復雜度； 11、補充：了解拓撲排序算法； 12、補充：能將圖的抽象定義，如有向圖G＝（V，{A}），V＝{v1，v2，v3，v4}

15、，A＝{，，，}畫成圖，也能將圖用抽象定義寫出； 13、補充：能根據(jù)圖的鄰接表、逆鄰接表、數(shù)組表示法表示出來的圖畫出，亦能根據(jù)圖寫出其鄰接表、逆鄰接表、數(shù)組表示法； 14、補充：了解四色定理(Four color theorem)：最先是由一位叫古德里（Francis Guthrie）的大學生提出來的。德摩爾根（Augustus De Morgan，1806～1871）1852年10月23日致的一封信提供了有關(guān)四色定理來源的最原始的記載。他在信中簡述了自己證明四色定理的設想與感受。四色問題的內(nèi)容是：“任何一張只用四種顏色就能使具有共同

16、邊界的國家染上不同的顏色?！庇脭?shù)學語言表示，即“將平面任意地細分為不相重疊的區(qū)域，每一個區(qū)域總可以用1，2，3，4這四個數(shù)字之一來標記，而不會使相鄰的兩個區(qū)域得到相同的數(shù)字?！? 15、補充：了解離散數(shù)學中的歐拉圖、哥尼斯堡七橋問題； 16、補充：了解漢密爾頓圖； 第九章 查找 1、掌握幾個重要的概念：靜態(tài)查找表、動態(tài)查找表、平均查找長度、二叉排序樹、平衡二叉樹、平衡因子、B－樹、B＋樹、哈希表； 2、順序表的查找算法（9.1）及其時間復雜度的性能分析； 3、折半查找（二分查找）算法（9.2）及其性能分析； 4、能畫出任意個數(shù)元素的二分查找過程形成的判定樹； 5、掌握次優(yōu)二叉查找

17、樹的構(gòu)造過程，能用手畫出，其算法只做了解要求； 6、掌握索引順序表的查找（又稱分塊查找）基本原理，并能分析其性能； 7、能手動根據(jù)元素的順序，構(gòu)造出一棵二叉排序樹； 8、掌握二叉排序樹的幾種算法：查找算法（9.5a、9.5b）、二叉排序樹的插入算法（9.6），而插入過程就是構(gòu)造二叉排序樹的過程； 9、掌握二叉排序樹的刪除結(jié)點的手動過程及算法（9.7、9.8）； 10、掌握二叉排序樹的查找性能分析過程； 11、平衡二叉樹的構(gòu)造過程，重點在于平衡被破壞后的調(diào)整，LL型、LR型、RR型、RL型的平衡旋轉(zhuǎn)處理； 12、平衡樹查找的性能分析； 13、B－樹的查找操作，了解其算法； 14

18、、B－樹的查找性能分析； 15、B＋樹的查找操作； 16、引入哈希表的目的、優(yōu)點、基本原理； 17、了解幾種常用的哈希函數(shù)：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機數(shù)法； 18、掌握幾種常用的處理沖突的方法：開放定址法（線性探測法、偽隨機數(shù)序列法）、再哈希法、鏈地址法、公共溢出區(qū)法； 19、哈希表的查找性能分析； 第十章 內(nèi)部排序 1、掌握幾個重要的概念：排序、排序方法的穩(wěn)定性（即關(guān)鍵字相同的經(jīng)排序后原順序會不會變化）、排序算法效率的穩(wěn)定性（即排序算法效率會不會受待排序數(shù)據(jù)序列的影響而出現(xiàn)較大的變化）、內(nèi)部排序、外部排序、堆 2、直接插入排序的過程（手動分析

19、一趟排序的過程、結(jié)果）、算法（10.1）； 3、掌握折半插入排序算法（10.2）、理解2－路插入排序、了解表插入排序； 4、希爾排序過程（手動分析一趟排序的過程、結(jié)果）、算法（10.4、10.5）； 5、冒泡排序過程（手動分析一趟排序的過程、結(jié)果）、算法； 6、快速排序過程（手動分析一趟排序的過程、結(jié)果）、原理、算法（10.6-8） 7、快速排序性能分析； 8、簡單選擇排序過程（手動分析一趟排序的過程、結(jié)果）、算法（10.9）； 9、堆排序過程（手動分析建初始堆過程、一趟排序的過程、結(jié)果）、原理、算法（10.10-11），堆排序原理、過程、算法非常重要，是?？键c； 10、2－路歸并排序過程（手動分析一趟排序的過程、結(jié)果）、算法（10.2-4）； 11、理解基數(shù)排序的原理、過程； 12、掌握各種內(nèi)部排序方法的比較； 13、補充：各種內(nèi)部排序的應用場合（這個比較難做，需要對各種排序算法非常清楚才能做到）； 14、補充：冒泡排序的改進——鯊魚排序過程、原理、算法； 15、補充：插入、選擇、冒泡、快速、堆排序的算法效率穩(wěn)定性分析，能判斷哪種算法不受初始數(shù)據(jù)的影響； 16、補充：用鏈表實現(xiàn)插入排序的過程、算法；