|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
初試《數據結構》科目考試大綱
一、考查目標
考查學生對數據結構及算法分析相關基礎知識及技能的掌握水
平，并對學生利用有關基礎知識和技能分析研究計算機加工的數據結
構特性，進一步為實際應用涉及的數據選擇及設計適當的邏輯結構、
存儲結構及其相應的算法能力進行考核。
二、考試形式與試卷結構
（一）試卷滿分及考試時間
滿分為 150 分，考試時間為 3 小時。
（二）答題方式
答題方式為閉卷、筆試。
（三）試卷內容結構
內容結構為各部分知識點在試卷中所占的比例。
（四）試卷題型結構
選擇題 10 分、簡答題 20 分、解答題 80 分、算法設計題 40 分，
合計 150 分。
三、考查內容及要求
（一）數據結構概述
1、基本概念及術語
數據結構、邏輯結構、物理結構、抽象數據類型的概念；數據結
構的分類、兩種物理結構的特點。
2、ADT 的表示與實現
ADT 的定義、作用及類 C 語言實現方法。
3、算法和算法分析
算法的概念、特性和評判標準、算法時間復雜度的概念、簡單的
算法時間復雜度分析。
（二）線性表
1、線性表的類型定義
線性表的抽象數據類型定義、線性結構的特點。
2、線性表的順序表示和實現
順序表的含義、特點和相關算法。
3、線性表的鏈式表示和實現
鏈表的含義、特點和相關算法。
4、一元多項式表示與相加
一元多項式表示與相加的方法、順序結構和鏈式結構的區別和選
擇。
（三）棧與隊列
1、棧
棧結構的抽象數據類型定義、特點、存儲結構和相關算法。
2、棧的應用舉例
棧的應用及相關算法。
3、隊列
隊列結構的抽象數據類型定義、特點、存儲結構和相關算法。
（四）串
1、串類型的定義、表示和實現
串的定義、串的三種主要表示和實現方式。
2、串的模式匹配
串的常見模式匹配算法。
（五）數組與廣義表
1、數組的定義
數組概念、特點。
2、數組的順序表示和實現
數組順序存儲結構表示和實現。
3、數組的壓縮存儲
特殊矩陣的壓縮存儲、稀疏矩陣的壓縮存儲的實現方法。
4、廣義表的定義和實現
廣義表的定義及運算、廣義表的存儲結構。
（六）樹和二叉樹
1、樹的定義和基本術語
樹的定義、常用術語。
2、二叉樹
二叉樹的定義、二叉樹的性質、存儲結構。
3、數組的壓縮存儲
特殊矩陣的壓縮存儲、稀疏矩陣的壓縮存儲的實現方法。
4、遍歷二叉樹和線索二叉樹
二叉樹遍歷及線索化的概念、方法和算法。
5、樹和森林
樹的存儲結構，樹、森林、二叉樹間相互轉換方法、樹和森林遍
歷方法。
6、赫夫曼樹及其應用
赫夫曼樹和赫夫曼編碼構造方法。
（七）圖
1、圖的定義和術語
圖的定義和術語。
2、圖的存儲結構
圖的鄰接矩陣表示法、鄰接表表示法、十字鏈表表示法。
3、圖的遍歷
圖的深度優先及廣度優先遍歷方法和算法。
4、圖的連通性問題
連通子圖、生成樹、最小生成樹的定義和構造方法。
5、拓撲排序
拓撲排序方法、算法及應用。
6、最短路徑
最短路徑問題求解方法、算法及應用。
7、關鍵路徑
關鍵路徑問題求解方法、算法及應用。
（八）查找
1、靜態查找表
查找的概念、順序查找和折半查找的方法和算法。
2、動態查找表
二叉查找樹和二叉平衡概念及作用、二叉查找樹和二叉平衡樹相
關算法。
3、哈希表
哈希表的概念、沖突的概念、常見哈希函數構造方法、哈希表的
處理沖突的常用方法。
（九）排序
1、排序的概念
排序的有關概念、排序的類型。
2、排序方法及算法
掌握插入排序、快速排序、選擇排序、歸并排序、基數排序的方
法、算法及相關算法時間、空間復雜度分析過程。
四、考試用具說明
考試使用黑色筆作答,考試時需要攜帶計算器、直尺、筆。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
