|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
大連海事大學碩士研究生入學考研大綱
考試科目：數據結構
試卷滿分及考試時間：試卷滿分為 100 分，考試時間為 180 分鐘。
一、數據結構基本概念
考試內容
(1) 數據結構的基本概念：數據、數據元素、數據結構、數據的邏輯結構、物理
結構、算法等。
(2) 抽象數據類型的表示和實現。
(3) 算法時間復雜度和空間復雜度的分析。
考試要求
1. 掌握和理解數據結構的概念；
2. 掌握數據結構的相關術語與基本概念；
3. 掌握算法的時間復雜度及判斷算法好壞的方法。
二、線性表
考試內容
(1) 線性表的類型定義。
(2) 線性表的順序存儲方法和實現，相關查找、插入和刪除算法算法實現，應用
舉例；
(3) 線性表的鏈式存儲方法和實現，相關查找、插入和刪除算法算法實現，應用
舉例。
考試要求
1. 掌握線性表的順序存儲結構和鏈式存儲結構的各自特點；
2. 熟練掌握順序表和鏈式表的插入、刪除和查找等基本操作；
3. 能夠編制和實現順序表和鏈式表基本操作的程序；
三、棧和隊列
考試內容
(1) 棧的定義及特點，棧的順序存儲和鏈接存儲的表示和實現，進棧出棧算法。
(2) 棧的應用舉例，如表達式求值、數制轉換等。
(3) 隊列的定義及特點，隊列的表示和實現，循環隊列和鏈隊列的進隊出隊算
法。
考試要求
1. 掌握棧和隊列兩種特殊的線性表的特點
2. 熟練掌握棧的基本操作即進棧、出棧、棧空、棧滿、取棧頂元素等操作；
3. 熟練掌握隊列的基本操作即入隊列、出隊列、判斷隊列空、隊列滿等；
四、串
考試內容
(1) 串類型的定義。
(2) 串的表示和實現，定長順序存儲表示。
(3) 串的匹配算法。
考試要求
1. 掌握串的定義與特點；
2. 掌握串的抽象數據類型的定義、定長順序存儲表示、基本操作；
3. 熟練掌握串的模式匹配算法中的樸素算法、首尾匹配算法；會計算 KMP 算法的
next[j]。
五、數組和廣義表
考試內容
(1) 數組的邏輯結構定義和存儲方法。
(2) 特殊矩陣和稀疏矩陣的壓縮存儲方法及其適用范圍。
(3) 廣義表的結構特點及其存儲方法。
考試要求
1. 掌握數組的定義；
2. 掌握二維數組的存儲結構及尋址方法；
3. 掌握矩陣壓縮存儲的基本思想特殊矩陣和稀疏矩陣的壓縮存儲方法及尋址方
法；
4. 掌握三元組順序表的轉置運算；
5. 掌握廣義表的定義、其基本概念及存儲方法；
六、樹和二叉樹
考試內容
(1) 二叉樹的定義、性質和存儲結構。
(2) 二叉樹的遍歷及有關算法，利用遍歷算法實現二叉樹的其他操作，如計算二
叉樹結點個數、葉子結點個數、二叉樹的高度等。
(3) 樹和森林的定義、存儲結構與二叉樹的轉換。
(4) 樹的應用，哈夫曼樹及哈夫曼編碼、帶權路徑長度的計算。
考試要求
1. 熟練掌握二叉樹的結構特性，了解相應的證明方法；
2. 熟練掌握二叉樹的二叉鏈表存儲；
3. 掌握二叉樹各種遍歷的遞歸算法，靈活運用遍歷算法實現二叉樹的其它操作；
4. 熟悉樹的各種存儲結構及其特點，
5. 掌握樹和森林與二叉樹的轉換方法；
6. 掌握哈夫曼樹的特性及建立哈夫曼樹和哈夫曼編碼的方法。
七、圖
考試內容
(1) 圖的定義及相關術語和性質。
(2) 圖的存儲結構：鄰接矩陣表示法、鄰接表。
(3) 圖的兩種遍歷策略：深度優先搜索和廣度優先搜索，以及相關算法。
(4) 圖的最小生成樹，構造最小生成樹的兩種算法：普里姆算法和克魯斯卡爾算
法。
(5) 拓撲排序和關鍵路徑。
(6) 兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法。
考試要求
1. 掌握理解圖的抽象數據類型定義及其基本術語；
2. 掌握圖的鄰接矩陣和鄰接表的存儲方法；
3. 掌握圖的遍歷方法及其在鄰接矩陣和鄰接表存儲結構上的實現；
4. 掌握構造最小生成樹的 Prim 算法和 Kruskal 算法的基本思想和求解過程；
5. 掌握求解最短路徑的 Dijkstra 算法和 Floyd 算法的基本思想及過程；
6. 掌握拓撲序列的定義及拓撲排序算法；
7. 掌握關鍵路徑的定義及求解過程；
八、查找
考試內容
(1) 靜態查找：順序查找、折半查找的查找方法及其實現方法。
(2) 動態查找：二叉排序樹、平衡二叉樹。二叉排序樹的插入和查找算法及其實
現。
(3) 哈希表：哈希函數的構造方法、處理沖突的方法、哈希表的查找與分析。
考試要求
1. 掌握靜態查找（順序查找、折半查找）及其分析方法，并能靈活地運用；
2. 掌握二叉排序樹的構造方法、查找過程及其查找分析；
3. 掌握平衡二叉樹的構造、調整方法及平衡樹查找分析；
4. 掌握哈希表的建表方法和處理沖突的方法，理解哈希表與其他查找表的本質區
別；
5. 掌握各種查找方法的平均查找長度；
九、排序
考試內容
(1) 排序的基本概念。
(2) 插入排序：直接插入排序、其他插入排序和希爾排序。
(3) 交換排序：冒泡排序和快速排序。
(4) 選擇排序：簡單選擇排序、堆排序。
(5) 歸并排序：2-路歸并排序。
(6) 各種排序方法的算法實現。能從“關鍵字間的比較次數”分析算法的平均情
況和最壞情況的時間性能。排序方法“穩定”或“不穩定”的含義。
考試要求
1. 理解排序的基本概念，包括排序的穩定性及排序的性能分析（時間與空間復雜
度）；
2. 掌握插入排序、交換排序、選擇排序和歸并排序等的排序方法、性能分析方法
及手工執行排序算法；
? 參閱：
《數據結構》 嚴蔚敏、吳偉民 清華大學出版社
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
