|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
2014 年碩士研究生入學考試大綱
考試科目名稱：數據結構 考試時間：180 分鐘，滿分：150 分
一、考試要求：
1．理解數據結構、算法、抽象數據類型(ADT)的基本概念。
2．掌握線性表、樹、圖等基本數據結構的 ADT 定義以及在順序存儲和鏈式存儲下
相關算法的實現，并能對算法的時間復雜度進行分析。
3．掌握 “查找”和“排序”中主要算法的基本思想和特點。
4．能夠運用學習的數據結構知識和技能進行問題的分析與求解，具備采用 C 或 C++
或 JAVA 語言設計與實現算法（編程）的能力。
二、考試內容：
1．一般線性表
（1）基于順序存儲的定義和實現（方式、特點）
（2）基于鏈式存儲的定義和實現（方式、特點）
（3）線性表的應用
2．特殊線性表（棧、隊列、字符串、數組）
（1）棧、隊列、字符串、數組的基本概念、特點
（2）棧和隊列基于順序存儲的定義與實現（方式、特點）
（3）棧和隊列基于鏈式存儲的定義與實現（方式、特點）
（4）字符串基于順序存儲的定義與實現（能夠求模式的失敗函數）
（5）數組的邏輯定義和順序存儲
（6）特殊數組的存儲（存儲方式、占用空間情況、數組操作的實現、在一維存儲空間
中下標的計算）
（7）稀疏矩陣的壓縮存儲及轉置算法實現
4．樹與二叉樹
（1）二叉樹
①二叉樹的定義、主要特征及相關特征的證明
②二叉樹基于順序存儲和鏈式存儲的實現（方式、特點）
③二叉樹重要操作的實現（建立、遍歷、計算葉子結點、結點、深度等算法實現）
④線索二叉樹的基本概念和構造（為什么加線索？如何記錄線索？如何使用線
索？）
（2）樹、森林
①樹的存儲結構（重點掌握子女-兄弟表示）
②森林與二叉樹的相互轉換
③樹和森林的遍歷
（3）特殊二叉樹及應用
①哈夫曼（Huffman）樹和哈夫曼編碼的構造過程
②二叉排序樹（重點掌握結點的插入和刪除的思想和過程）
③平衡二叉樹（平衡的目的？如何達到平衡？）
④堆（堆的構造和調整過程）
5．圖
（1）圖的基本概念
（2）圖的存儲及基本操作
①鄰接矩陣存儲（無向圖、有向圖、無向帶權圖、有向帶權圖）
②鄰接表存儲（無向圖、有向圖、無向帶權圖、有向帶權圖）
③各種存儲方式下操作的算法實現（圖的建立、遍歷、插入邊、刪除邊等）
（3）圖的遍歷
①深度優先遍歷（思想、過程及算法實現）
②廣度優先遍歷（思想、過程及算法實現）
（4）圖的基本應用（掌握算法的思想、過程）
①最小生成樹問題
②最短路徑問題
③有向圖與工程（AOV 網與拓撲排序，AOE 網與關鍵路徑）
6．查找
（1）查找的基本概念
（2）順序查找法（監視哨法的思想和算法）
（3）折半查找法（思想和算法）
（4）B 樹及其基本操作、B+樹的基本概念（思想和過程）
（5）散列（Hash）表（Hash 函數和解決沖突的方法的思想和過程）
（6）查找算法的時間復雜度、平均查找長度的分析
7．排序
（1）排序的基本概念
（2）基于“插入”思想的排序方法
①直接插入排序
②折半插入排序（思想和過程）
③希爾排序（思想和過程）
（3）基于“交換”思想的排序方法
①冒泡排序（思想、過程和算法）
②快速排序（思想、過程和算法）
（4）基于“選擇”思想的排序方法
①簡單選擇排序（思想、過程和算法）
②堆排序（思想和過程）
（5）基于“歸并”思想的排序方法
二路歸并排序（思想、過程）
（6）各種常用內部排序算法的特點及應用
三、考試形式和試卷結構
1.考試時間：180 分鐘，滿分：150 分
2.題型結構
a:選擇題(50 分)
b:應用題(50 分)
c:算法分析與設計(50 分)
3.答題方式：閉卷、筆試
四、參考書目
1. 數據結構（用面向對象方法與 C++語言描述）（第 2 版）.殷人昆主編. 北京：清華大
學出版社.2007.6
2. 數據結構（C 語言版）.嚴蔚敏、吳偉民編著. 北京：清華大學出版社. 2007
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
