2021武漢輕工大學計算機專業基礎綜合（數據結構、算法基礎）專業研究生考試大綱 正文

考試目標：
考察學生對數據結構和算法基礎知識和基本技術的理解、掌握情況及運用相關知識和技
術解決實際問題的能力。
考試內容
1. 數據結構基礎知識
理解數據、數據元素、數據對象、數據結構和數據類型的定義。掌握數據的邏輯結構和
存儲結構及其種類以及算法的重要特征。掌握算法的時間復雜度和空間復雜度的計算方法。
2. 線性表
了解線性表的定義和線性結構的特點。理解線性表的順序存儲和鏈式存儲，理解數組與
單鏈表表示表的優缺點。掌握順序表中數據元素的存儲位置的計算。掌握順序表、單鏈表、
循環鏈表和雙向鏈表的插入、刪除等有關操作。
3. 棧和隊列
了解棧和隊列的定義和特點。理解線性表、棧和隊列特點及區別，棧對實現遞歸過程的
作用。掌握順序棧、鏈棧的入棧和出棧操作，順序隊列、鏈隊列的入隊和出隊操作，循環隊
列的隊空和隊滿的判斷。
4. 串
了解串的有關定義。理解串的邏輯結構和存儲結構。
5. 數組和廣義表
了解數組、特殊矩陣和稀疏矩陣的定義。理解矩陣的壓縮存儲的概念。掌握矩陣的壓縮
存儲的有關計算方法。了解廣義表的概念和存儲結構，掌握廣義表表頭和表尾操作。 6. 樹和二叉樹
了解樹的定義和二叉樹的定義。理解二叉樹的性質、二叉樹的存儲結構。掌握遍歷二叉
樹的方法、線索二叉樹的構造，森林與二叉樹的轉換，最優二叉樹和哈夫曼編碼。
7. 圖
了解圖的定義和術語，以及生成樹和最小生成樹的概念。理解并掌握圖的鄰接矩陣和鄰
接表表示。掌握深度優先搜索和廣度優先搜索算法。會用 Prim 算法和 Kruskal 算法構造最小
生成樹，會求拓撲序列、關鍵路徑和最短路徑。
8. 查找
了解查找及相關概念。掌握順序查找、二分查找，了解分塊查找。了解二叉排序樹和平
衡二叉樹、哈希查找相關概念。理解二叉排序樹的性質，掌握二叉排序樹的查找、插入和刪
除操作算法。掌握維護平衡二叉樹平衡的方法。掌握相關查找方法的平均查找長度。掌握哈
希函數的構造方法和處理沖突的方法，會用哈希函數、開放地址法或鏈地址法建立哈希表。 9. 排序
了解排序及相關概念。理解直接插入排序、希爾排序、起泡排序、快速排序、簡單選擇
排序、堆排序、歸并排序和基數排序的基本思想。掌握直接插入排序、希爾排序、起泡排序、
快速排序、簡單選擇排序、堆排序、歸并排序的算法實現和時間復雜度分析。
10. 算法基礎知識
理解算法的概念和性質、算法的復雜性概念和分析方法、計算時間的漸近表示及其相關
性質。
11. 遞歸和分治
理解遞歸的概念和遞歸算法的實現機制，掌握設計和分析遞歸算法的一般方法。理解分
治法的基本思想和適用條件，掌握分治法的效率分析。理解并掌握分治法應用的經典實例。
12. 動態規劃
理解動態規劃的基本原理和應用條件，理解動態規劃的效率分析，理解并掌握動態規劃
應用的經典實例。
13. 貪心算法
理解貪心法的基本原理和基本要素，理解貪心算法的效率分析和正確性分析，理解并掌
握貪心法應用的經典實例。
14. 回溯法
理解回溯法的基本思想和剪枝函數的設計，理解回溯法的效率分析，理解并掌握回溯法
應用的經典實例。
15. 分支限界法
理解分支限界法的基本思想，理解隊列式分支限界法和優先隊列式分支限界法，理解并
掌握分支限界法應用的經典實例。
總分值：150 分
試題形式與結構：1. 名詞解釋；2. 填空題；3. 選擇題；4. 判斷題；5. 問答題；6. 應
用題；7. 算法設計題
參考教材： 1、 嚴蔚敏，吳偉民編著. 數據結構（C 語言版）. 北京: 清華大學出版社，1997.4
2、 嚴蔚敏等編著. 數據結構題集（C 語言版）. 北京: 清華大學出版社，1999.2 3、 王曉東編著. 計算機算法設計與分析（第 5 版）. 北京：電子工業出版社，2018.8
4、 王曉東編著. 計算機算法設計與分析習題解答（第 5 版）. 北京：電子工業出版社，
2018.10

武漢輕工大學

本文來源：http://www.sacvlig.cn/wuhanqinggongdaxue/cankaoshumu_384715.html