2019年大連海事大學管理科學與工程（工科）考研專業(yè)課數(shù)據(jù)結構（同等學力加試）考試大綱

1、大連海事大學碩士研究生入學考試大綱大連海事大學碩士研究生入學考試大綱考試科目：數(shù)據(jù)結構試卷滿分及考試時間：試卷滿分為100分，考試時間為180分鐘。一、數(shù)據(jù)結構基本概念一、數(shù)據(jù)結構基本概念考試內容考試內容(1)數(shù)據(jù)結構的基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結構、數(shù)據(jù)的邏輯結構、物理結構、算法等。(2)抽象數(shù)據(jù)類型的表示和實現(xiàn)。(3)算法時間復雜度和空間復雜度的分析?？荚囈罂荚囈?.掌握和理解數(shù)據(jù)結構的概念；2.掌握數(shù)據(jù)結構的相關術語與基本

2、概念；3.掌握算法的時間復雜度及判斷算法好壞的方法。二、線性表二、線性表考試內容考試內容(1)線性表的類型定義。(2)線性表的順序存儲方法和實現(xiàn)，相關查找、插入和刪除算法算法實現(xiàn)，應用舉例；(3)線性表的鏈式存儲方法和實現(xiàn)，相關查找、插入和刪除算法算法實現(xiàn)，應用舉例?？荚囈罂荚囈?.掌握線性表的順序存儲結構和鏈式存儲結構的各自特點；2.熟練掌握順序表和鏈式表的插入、刪除和查找等基本操作；3.能夠編制和實現(xiàn)順序表和鏈式表基本操作的程序

3、；三、棧和隊列三、棧和隊列考試內容考試內容(1)棧的定義及特點，棧的順序存儲和鏈接存儲的表示和實現(xiàn)，進棧出棧算法。(2)棧的應用舉例，如表達式求值、數(shù)制轉換等。(3)隊列的定義及特點，隊列的表示和實現(xiàn)，循環(huán)隊列和鏈隊列的進隊出隊算法?？荚囈罂荚囈?.掌握棧和隊列兩種特殊的線性表的特點2.熟練掌握棧的基本操作即進棧、出棧、?？铡M、取棧頂元素等操作；3.熟練掌握隊列的基本操作即入隊列、出隊列、判斷隊列空、隊列滿等；四、串四、串考試內

4、容考試內容(3)圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索，以及相關算法。(4)圖的最小生成樹，構造最小生成樹的兩種算法：普里姆算法和克魯斯卡爾算法。(5)拓撲排序和關鍵路徑。(6)兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法?？荚囈罂荚囈?.掌握理解圖的抽象數(shù)據(jù)類型定義及其基本術語；2.掌握圖的鄰接矩陣和鄰接表的存儲方法；3.掌握圖的遍歷方法及其在鄰接矩陣和鄰接表存儲結構上的實現(xiàn)；4.掌握構造最小生成樹的Prim算法和

5、Kruskal算法的基本思想和求解過程；5.掌握求解最短路徑的Dijkstra算法和Floyd算法的基本思想及過程；6.掌握拓撲序列的定義及拓撲排序算法；7.掌握關鍵路徑的定義及求解過程；八、查找八、查找考試內容考試內容(1)靜態(tài)查找：順序查找、折半查找的查找方法及其實現(xiàn)方法。(2)動態(tài)查找：二叉排序樹、平衡二叉樹。二叉排序樹的插入和查找算法及其實現(xiàn)。(3)哈希表：哈希函數(shù)的構造方法、處理沖突的方法、哈希表的查找與分析?？荚囈罂荚囈?/p>

6、1.掌握靜態(tài)查找（順序查找、折半查找）及其分析方法，并能靈活地運用；2.掌握二叉排序樹的構造方法、查找過程及其查找分析；3.掌握平衡二叉樹的構造、調整方法及平衡樹查找分析；4.掌握哈希表的建表方法和處理沖突的方法，理解哈希表與其他查找表的本質區(qū)別；5.掌握各種查找方法的平均查找長度；九、排序九、排序考試內容考試內容(1)排序的基本概念。(2)插入排序：直接插入排序、其他插入排序和希爾排序。(3)交換排序：冒泡排序和快速排序。(4)選擇排