| 武漢紡織大學預發布2023年碩士研究生入學考試自命題大綱 | |||
| 考試科目代碼 | 考試科目名稱 | 考試大綱 | 參考書目 |
| 848 | 數據結構 |
一、 考試目標 1、 掌握數據結構的基本概念、基本原理和基本方法。 2、 掌握數據結構的邏輯結構、存儲結構以及各種基本操作的實現，能夠對算法進行基本的時間復雜度與空間復雜度的分析。 3、 能夠運用數據結構基本原理和方法進行問題的分析與求解，能夠對算法進行設計與分析。 二、 考試范圍及考試內容 1、緒論 （1） 什么是數據結構 （2） 基本概念和術語 （3）抽象數據類型的表示與實現 （4） 算法和算法分析 2、線性表 （1）線性表的定義和基本操作 （2）線性表的順序表示和實現 （3）線性表的鏈式表示和實現 （4）線性表的應用 3、棧和隊列 （1） 棧和隊列的基本概念 （2）棧和隊列的順序存儲結構 （3）棧和隊列的鏈式存儲結構 （4）棧的應用：數制轉換、括號匹配的檢驗、行編輯程序、表達式求值 （5） 隊列的應用：楊輝三角 4、樹和二叉樹 （1） 樹的定義和基本術語 （2） 二叉樹：定義、順序存儲結構和鏈式存儲結構、遍歷 （3）線索二叉樹的基本概念和構造 （4） 樹和森林：存儲結構、森林和二叉樹的轉換、樹和森林的遍歷 （5） 樹和二叉樹的應用：赫夫曼樹及赫夫曼編碼 5、圖 （1） 圖的定義和術語 （2） 圖的存儲結構：鄰接矩陣、鄰接表 （3） 圖的遍歷：深度優先搜索、廣度優先搜索 （4）圖的基本應用： 最小生成樹、最短路徑、拓撲排序和關鍵路徑 6、查找 （1） 靜態查找表：順序查找、折半查找、分塊查找 （2） 動態查找表：二叉排序樹、平衡二叉樹 （3） 哈希表 7、內部排序 （1） 基本概念 （2） 插入排序：直接插入排序、折半插入排序、希爾排序 （3） 交換排序：起泡排序、快速排序 （4） 選擇排序 （5） 歸并排序 （6） 基數排序 （7） 各種內部排序方法的比較討論 |
《數據結構（C語言版）》，嚴蔚敏、吳偉民編著，清華大學出版社 |
