《算法與數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)要點

第一章緒論數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)（線性表、棧、隊列、串）和非線性結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)：順序存儲、鏈式存儲、索引存儲、散列存儲；常用的數(shù)據(jù)結(jié)構(gòu)的運算：插入、刪除、查找、修改、排序；時間復(fù)雜度的計算；第二章線性表1、順序存儲和鏈式存儲的定義，優(yōu)缺點，及其適用場景；2、單鏈表和雙向鏈表的基本操作如何實現(xiàn)，諸如插入、刪除等；3帶頭結(jié)點和無頭結(jié)點的單鏈表L4、鄰接表是一種結(jié)合了順序存儲與鏈式存儲的存儲格式，在那些結(jié)構(gòu)中被使用第三章棧和隊列棧：1、棧的相關(guān)操作：入棧和出棧；2、給定入棧序列，寫出所有可能的出棧序列；3、共享棧的基本概念和操作；隊列：1、順序隊列的“假溢出”是怎樣產(chǎn)生的？2、循環(huán)隊列：長度的計算；隊滿的表達式；隊空的表達式；1、串的存儲方式

第四章串2、樸素匹配算法和KMP算法的核心思想：兩種算法比較次數(shù)的計算第五章多維數(shù)組和廣義表多維數(shù)組：1、二維數(shù)組存儲地址的計算（行優(yōu)先存儲和列優(yōu)先存儲）第一個元素的下標；第一個元素的存儲地址；每個元素占幾個單元；2、特殊矩陣的壓縮存儲（對稱矩陣、三角矩陣、對角矩陣）如何進行壓縮存儲；壓縮存儲后，a （二維數(shù)組）和sa[k]（順序表）之間ij的對應(yīng)關(guān)系；也就是說如何通過i和j算出k。稀疏矩陣的兩種存儲方式：三元組表、十字鏈表；在轉(zhuǎn)置矩陣中的下標廣義表：1、廣義表的定義2、廣義表的取表頭和取表尾運算L(a,b)head(L)atail(L)(b)第六章樹5條性質(zhì)：1（所有二叉樹2（所有二叉樹3（所有二叉樹4（完全二叉樹5（完全二叉樹二叉樹的遍歷：1、先序遍歷、中序遍歷、后序遍歷；2二叉樹的還原：二叉樹中結(jié)點和深度的計算（遞歸實現(xiàn)：1、葉子結(jié)點的計算；2、總結(jié)點的計算；3線索二叉樹：1、結(jié)點的結(jié)構(gòu)體定義；2結(jié)構(gòu)體的五個成員變量（尤其是線索標志域、箭頭的起始和終止位置；3（程序找錯題二叉樹和樹的轉(zhuǎn)換、二叉樹和森林的轉(zhuǎn)換：弟節(jié)點。哈夫曼樹1、哈夫曼樹的定義2、依據(jù)數(shù)據(jù)序列構(gòu)造哈夫曼樹、各個數(shù)據(jù)的對應(yīng)碼值、帶權(quán)路徑長度。第七章圖圖的相關(guān)定義：1、有向圖和無向圖；2、N個節(jié)點的有向圖和無向圖最多有多少條邊、最少有多少條邊；3、極大連通分量和極小連通分量；圖的存儲：1、鄰接表：結(jié)構(gòu)體定義；2、鄰接矩陣：結(jié)構(gòu)體定義；3圖的遍歷：1、廣度優(yōu)先遍歷（隊列）2（棧最小生成樹：1、普里姆算法2、克魯斯卡爾算法AOE網(wǎng)關(guān)鍵路徑的計算（頂點表示事件、邊表示活動）1、事件的最早發(fā)生時間（有多條入邊時怎樣計算、最遲發(fā)生時間（條出邊時怎樣計算；2（該條邊的始點事件的最早發(fā)生時間（條邊的終點時間的最遲發(fā)生時間—邊的權(quán)重；3、活動的時間余量（余量為0的活動即為關(guān)鍵活動）最短路徑的計算（迪杰斯特拉算法）第八章排序各種排序算法的具體實現(xiàn)過程，如何統(tǒng)計比較次數(shù)：插入排序：直接插入排序（傳統(tǒng)的插入排序交換排序：冒泡排序、快速排序；選擇排序：直接選擇排序、堆排序（初始堆如何建立、應(yīng)從下標為/2處開始的性質(zhì)；歸并排序：建議：對比學(xué)習(xí)：比如直接插入和直接選擇、希爾排序和歸并排序，相同點在哪里，不同點在哪里？第九章查找順序查找：折半查找（二分查找分塊查找：樹表的查找二叉排序樹的查找：平衡二叉排序樹L樹散列表的查找常見的哈希函數(shù)沖突處理方法：開放地址法（線性探測法、二次探測法、隨機探