經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請聯(lián)系刪除，謝謝！繼續(xù)教育學(xué)院本科學(xué)位考試課程《數(shù)據(jù)結(jié)構(gòu)》知識點一、必須掌握的基本概念（可能的題型為名詞解釋）算法、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)組、串、模式匹配、順序表、鏈表、棧、隊列、樹、二叉樹、滿二叉樹、完全二叉樹、線索二叉樹、圖、網(wǎng)、有向圖、無向圖、檢索、哈希函數(shù)、哈希表、順序檢索、二分法檢索、排序、堆二、一般掌握的知識點（可能的題型為填空、單選、多選、判斷等客觀題）1、算法的5個重要特性。2、評價算法優(yōu)劣的5條標準。3、算法的時間復(fù)雜度分析。4、算法與程序的聯(lián)系和區(qū)別。5、數(shù)據(jù)的邏輯結(jié)構(gòu)的基本概念和分類。什么是線性結(jié)構(gòu)？什么是非線性結(jié)構(gòu)？6、數(shù)組的順序存儲結(jié)構(gòu)，數(shù)組元素的地址計算。7、空串與空格串的區(qū)別。8、簡單模式匹配算法。9、線性表的順序存儲和鏈式存儲的特點。10、棧和隊列的特性。、循環(huán)隊列為空的條件和為滿的條件。12、循環(huán)鏈表和雙向鏈表的特點。13、二叉樹的特點和性質(zhì)。14、二叉樹的存儲結(jié)構(gòu)。15、二叉樹的316、滿二叉樹與完全二叉樹的異同。17、完全二叉樹的相關(guān)計算。18、計算二叉樹的節(jié)點數(shù)和葉子數(shù)。19、圖的存儲結(jié)構(gòu)。20n個頂點的無向完全圖有n(n-1)/2條邊，n個頂點的有向完全圖有n(n-1)條弧。有向圖中所有結(jié)點的入度之和、出度之和均等于邊數(shù)。21nn個結(jié)點和n-1條邊。22、對有序表進行順序檢索，求其檢索成功和不成功的平均檢索長度。23、對有序表進行二分法檢索，求其檢索成功和不成功的平均檢索長度。24、用線性探查法消除地址沖突構(gòu)造哈希表。25、直接插入排序、希爾排序、冒泡排序、快速排序、堆排序、基數(shù)排序的時間復(fù)雜度、空間復(fù)雜度以及穩(wěn)定性。三、重點掌握的知識點（可能的題型為簡答、論述等主觀題）1、線性表的順序存儲和鏈式存儲的具體實現(xiàn)。2、棧和隊列的順序存儲和鏈式存儲的具體實現(xiàn)。3、已知一棵二叉樹的中序遍歷和先序（或后序、層序）遍歷畫出該二叉樹。4、畫前序、中序和后序線索化二叉樹。5、樹與二叉樹的相互轉(zhuǎn)換。6、森林與二叉樹的相互轉(zhuǎn)換。7、哈夫曼樹的構(gòu)造。8、給出有向圖和無向圖的鄰接矩陣、鄰接表和逆鄰接表，并計算每個頂點的度。9、給出無向網(wǎng)的深度優(yōu)先搜索遍歷序列和深度優(yōu)先生成樹。10、給出無向網(wǎng)的廣度優(yōu)先搜索遍歷序列和廣度優(yōu)先生成樹。、用Prim算法求得無向連通網(wǎng)的最小生成樹過程。12、用Kruskal算法求得無向連通網(wǎng)的最小生成樹過程。13Dijkstra14、用Floyd算法求有向網(wǎng)中每對頂點間最短路徑。15概率情況下檢索成功和不成功時的平均檢索長度。16除算法，畫出刪除給定結(jié)點后的二叉檢索樹。17、給出用線性探查法和鏈地址法消除地址沖突時所構(gòu)造的哈希表。18、寫出直接插入排序、希爾排序、選擇排序、冒泡排序、快速排序的排序過程。19、構(gòu)建最大值根堆和最小值根堆。20、寫出堆排序的過程。四、必須掌握的應(yīng)用知識點（可能的題型為計算題、算法設(shè)計題等）1、單鏈表插入結(jié)點和刪除結(jié)點算法的實現(xiàn)。2、雙鏈表插入結(jié)點和刪除結(jié)點算法的實現(xiàn)。3、入棧和出棧算法的實現(xiàn)。4、入隊和出隊算法的實現(xiàn)。5、二叉樹先序、中序和后序遍歷算法的實現(xiàn)。6、求二叉樹葉子結(jié)點數(shù)目算法的實現(xiàn)。7、求二叉樹深度算法的實現(xiàn)。8、二分檢索算法的實現(xiàn)。9、選擇排序和冒泡排序算法的實現(xiàn)。10、快速排序算法的實現(xiàn)。教材版本：[1]寧