2019年武漢工程大學835《數據結構》考研大綱

友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。下載流程：考研真題點擊“考研試卷””下載; 考博真題點擊“考博試卷庫” 下載

武漢工程大學
《數據結構》研究生入學考試大綱
一、“數據結構”課程的目的和要求
《數據結構》在計算機科學中是一門綜合性的核心專業基礎課，而且正逐漸發展成為眾
多理工專業的熱門選修課。數據結構課程在整個課程體系中處于承上啟下的核心地位，它
一方面擴展和深化在離散數學、程序設計語言等課程學到的基本技術和方法，一方面為進
一步學習其它專業課奠定堅實的理論與實踐基礎。課程的主要任務是學習數據的邏輯結構，
存儲結構以及相關的算法設計。本課程的目的是使學生學會分析待加工處理數據的特性，
以便選擇適當的邏輯結構、存儲結構以及進行相應的算法設計。在教給學生數據結構選擇
和算法設計的同時，培養學生的抽象思維能力、邏輯推理能力和形式化思維方法，增強分
析問題和解決問題的能力，更重要的是培養專業興趣、樹立創新意識。
二、基本內容
第一章數據結構基礎知識
（一）基本內容：
1.1 數據結構的興起和發展。
1.2 數據結構的研究對象。
1.3 數據結構的基本概念。
1.4 算法以及算法分析。
（二）基本要求：
（1）了解數據結構的興起和發展。
（2）掌握數據結構的基本概念。
（3）掌握數據的邏輯結構，存儲結構和算法的相互聯系和實質。
（4）掌握算法以及算法分析。
（5）了解數據結構的主要應用領域及發展方向。
（三）重點及難點：
重點：數據結構的定義，數據的邏輯結構、存儲結構的類型，算法的分析方法。
難點：算法的概念、特性和算法的分析。
第二章線性表
（一）基本內容：
2.1 線性表的邏輯結構。
2.2 線性表的順序存儲結構及實現。
2.3 線性表的鏈接存儲結構及實現。
2.4 線性表的其他存儲方法。
2.4.1 循環鏈表。
2.4.2 雙鏈表。
2.4.3 靜態鏈表。
2.5 線性表的應用舉例。
（二）基本要求：
（1）理解線性表的邏輯結構。
（2）掌握線性表的順序和鏈接存儲結構及各自的特征。
（3）熟練掌握在順序和鏈接存儲結構上的典型算法實現，并能夠盡量提高算法性能。
（4）合理運用線性表來解決實際問題。
（三）重點及難點：
重點：數據結構的定義，數據的邏輯結構、存儲結構的類型，算法的分析方法。
難點：算法的概念、特性和算法的分析。
第三章棧和隊列
（一）基本內容：
3.1 棧的特征、順序棧和鏈棧的實現。
3.2 棧的基本應用。
3.3 隊列的特征、順序隊和鏈隊列的實現。
3.4 隊列的基本應用。
3.5 遞歸算法的運行過程，遞歸算法的特征與設計。
（二）基本要求：
（1）掌握棧和隊列與線性表的關系。
（2）深入理解棧和隊列的結構特性和典型操作。
（3）掌握棧和隊列在編程中的應用。
（4）掌握遞歸算法的特征與設計方法。
（三）重點及難點：
重點：棧和隊列的結構特性和典型操作。
難點：循環隊列的設置和操作的實現，棧與隊列的編程應用。
第四章字符串
（一）基本內容：
4.1 字符串的概念與特征；與線性表的區別和聯系；字符串的基本操作。
4.2 字符串的存儲結構以及基本操作的實現。
4.3 模式匹配算法及改進。
（二）基本要求：
（1）了解字符串的概念與特征；與線性表的區別和聯系；字符串的基本操作。
（2）掌握字符串的存儲結構以及基本操作的實現。
（3）掌握模式匹配算法及改進。
（三）重點及難點：
重點：字符串的基本操作在存儲結構上的實現。
難點：模式匹配的 KMP 算法。
第五章數組和廣義表
（一）基本內容：
5.1 多維數組的邏輯結構和存儲方法。
5.2 特殊矩陣的邏輯結構，特殊矩陣的邏輯結構到存儲結構的映射函數。
5.3 稀疏矩陣的特點，利用三元組對及特殊矩陣的壓縮及典型操作算法設計。
5.4 廣義表的基本操作、廣義表的存儲結構。
（二）基本要求：
（1）掌握多維數組的行序優先與列序優先存儲方法。
（2）掌握特殊矩陣的特點和壓縮存儲。
（3）掌握稀疏矩陣的特點和壓縮存儲。
（4）掌握廣義表的基本操作、廣義表的存儲結構。
（5）了解廣義表的基本操作實現。
（三）重點及難點：
重點：多維數組的邏輯結構和存儲結構，特殊矩陣的結構特性和壓縮存儲方法，稀疏矩
陣的壓縮存儲，廣義表的概念與存儲。
難點：矩陣的壓縮存儲以及地址變換，廣義表的基本操作實現。
第六章樹和二叉樹
（一）基本內容：
6.1 樹的基本概念和特征。
6.2 二叉樹的概念和性質、二叉樹的順序存儲結構和鏈式存儲結構、二叉樹的遍歷及應用、
線索二叉樹基本概念和構造。
6.3 樹的存儲結構、森林與二叉樹的相互轉換、樹和森林的遍歷。
6.4 Huffman 樹和 Huffman 編碼。
（二）基本要求：
（1）掌握樹的邏輯結構與存儲結構。
（2）熟練掌握二叉樹的基本性質、特征和存儲結構、二叉樹的遍歷及應用。
（3）掌握線索二叉樹的基本概念和構造。
（4）掌握樹的存儲結構、森林與二叉樹的相互轉換、樹和森林的遍歷。
（5）掌握 Huffman 樹和 Huffman 編碼。
（三）重點及難點：
重點：二叉樹的概念和性質、二叉樹存儲結構、二叉樹的遍歷及應用、線索二叉樹及應
用、樹、森林和二叉樹的關系以及相互轉換。
難點：樹和二叉樹的相關算法實現。
第七章圖
（一）基本內容：
7.1 圖的概念與特征、圖的鄰接矩陣、鄰接表、鄰接多重表、十字鏈表的存儲。
7.2 圖的深度優先和廣度優先遍歷。
7.3 最小生成樹的算法與實現。
7.4 最短路徑的算法與實現。
7.5 拓撲排序的算法與實現。
7.6 關鍵路徑的算法與實現。
（二）基本要求：
（1）理解圖的邏輯結構與其特征。
（2）掌握圖的基本存儲結構。
（3）掌握圖的兩種遍歷方法及其應用。
（4）掌握圖的多種經典算法及其編碼實現。
（三）重點及難點：
重點：圖的基本存儲結構；深度優先遍歷和廣度優先遍歷；圖的基本應用：最小生成樹、
最短路徑、拓撲排序與關鍵路徑。
難點：圖的多種經典算法及其編碼實現。
第八章查找技術
（一）基本內容：
8.1 查找的概念，查找算法的性能標準。
8.2 順序查找、折半查找和分塊查找。
8.3 二叉排序樹的概念和查找與操作、平衡二叉樹的概念與操作。
8.4 B 樹及其基本操作、B+樹的基本概念。
8.5 散列表的概念與構造方法，查找性能。
8.6 查找算法的分析及應用
（二）基本要求：
（1）了解查找的概念，查找算法的性能標準。
（2）掌握順序查找、折半查找和索引順序表的查找。
（3）掌握二叉排序樹的概念與操作；平衡二叉樹的概念與操作。
（4）掌握 B 樹及其基本操作；B+樹的基本概念。
（5）掌握散列表的概念與構造方法，查找性能。
（三）重點及難點：
重點：各種查找算法及其性能分析。
難點：查找算法的時間性能；折半查找的判定樹；平衡二叉樹的操作；B-樹的操作；散
列表的構造與性能計算。
第九章排序
（一）基本內容：
9.1 排序算法的概念與性能評估標準。
9.2 插入排序及經典算法。
9.3 交換排序及經典算法。
9.4 選擇排序及經典算法。
9.5 歸并排序及算法。
9.6 基數排序及算法。
9.7 外部排序。
9.8 各種內部排序算法的比較。
9.9 排序算法的應用。
（二）基本要求：
（1）了解排序算法的概念與性能評估標準。
（2）掌握插入排序及經典算法；交換排序及經典算法。
（3）掌握選擇排序及經典算法；歸并排序及算法。
（4）掌握基數排序及算法。
（5）理解外部排序的基本方法。
（三）重點及難點：
重點：五大類內排序算法的思路，并對其各自的經典算法的算法步驟和算法性能進行較
為詳盡的分析。
難點：Shell 排序；快速排序；堆排序；排序算法的適用場合和選擇。
第十章文件
（一）基本內容：
10.1 文件的有關概念。文件的邏輯結構及其操作。文件的存儲結構（組織方式）分類。
評價文件組織效率的標準。
10.2 順序文件的特點及外存種類的適應性。順序文件上各種查找方法的基本思想及對外
存種類的要求。
10.3 索引文件的組織方式和特點。索引文件的查詢和更新操作的基本思想。
10.4 索引順序文件是最常用的一種文件組織方式的原因。兩種最常用的索引順序文件
（ISAM 文件和 VSAM 文件）的組織方式和特點。在 ISAM 文件和 VSAM 文件上查詢和更新操作
的基本思想。
10.5 散列文件的組織方式和特點。散列文件的查詢和更新操作的基本思想。
10.6 多關鍵字文件與其它文件的區別。多重表文件和倒排文件的組織方式和特點。多重
表文件和倒排文件上查詢及更新操作的基本思想。
（二）基本要求：
（1）了解文件的基本概念。
（2）了解順序文件、索引文件和散列文件的組織方式和特點。
（三）重點及難點：
重點：順序文件、索引文件和散列文件的組織方式和特點。
難點：ISAM 文件和 VSAM 文件。
三、關于考試命題的若干規定
1、考試方式為筆試閉卷，考試時間為 180 分鐘，滿分為 150 分。
2、對不同能力層次要求在試卷中所占比例大致如下： “識記”占 20﹪，“領會”占 30﹪，
“簡單應用”占 30﹪，“綜合應用”占 20﹪。
3、試卷中難易程度比例大約為：易:較易:較難:難=2:3:3:2。
4、題型有：判斷題、單項選擇題、問答題、應用題、算法設計題。
四、主要參考書
1、李春葆．數據結構教程（第 4 版）．北京：清華大學出版社，2013
2、嚴蔚敏，吳偉民．數據結構（C 語言版）．北京：清華大學出版社，2011
3、齊德昱．數據結構與算法．北京：清華大學出版社，2010
4、王紅梅、胡明等．數據結構（C++版）．北京：清華大學出版社，2005
5、Donald Knuth．The Art of Computer Programming．Vol.1: Fundamental Algorithms,
Vol.3: Sorting and Searching．Addison-westey Publishing Company,Inc. ,1973
6、William Ford, William Topp．Data Structure with C++．Prentice Hall,Inc. ,1996

免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。

上一篇文章： 2019年武漢工程大學834《信號與系統》考研大綱

下一篇文章： 2019年武漢工程大學836《計算機網絡》考研大綱