2019年大連海事大學工業(yè)工程（專業(yè)學位）考研專業(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.運用形式化方法定義和描述一個

2、實際問題對應的數(shù)據(jù)結構；3.掌握數(shù)據(jù)結構的相關術語與基本概念；4.掌握算法的時間復雜度與空間復雜度以及判斷算法好壞的方法。二、線性表二、線性表考試內容考試內容(1)線性表的類型定義。(2)線性表的順序存儲方法和實現(xiàn)，相關查找、插入和刪除算法算法實現(xiàn)。(3)線性表的鏈式存儲方法和實現(xiàn)，相關查找、插入和刪除算法算法實現(xiàn)，同時要注意鏈表中的頭結點、頭指針和首元結點的區(qū)別及循環(huán)鏈表、雙向鏈表的特點。(4)從時間和空間復雜度的角度比較兩種存儲結構

3、的不同特點及其適用場合?？荚囈罂荚囈?.掌握線性表的順序存儲結構和鏈式存儲結構的各自特點；2.區(qū)分數(shù)組和順序表及線性表的特征與關聯(lián)；3.熟練掌握順序表和鏈式表的插入、刪除和查找等基本操作；4.能夠編制和實現(xiàn)順序表和鏈式表基本操作的程序；5.掌握線性表在計算機內部與外部所起的重要作用；通過對它們各自算法的時間復雜度分析，能夠綜合判斷和衡量一個好的算法即程序的標準。三、棧和隊列三、棧和隊列考試內容考試內容(1)棧的定義及特點，棧的順序存

4、儲和鏈接存儲的表示和實現(xiàn)，進棧出棧算法，注意棧滿和?？盏臈l件。(2)棧的應用舉例，如表達式求值、數(shù)制轉換等。(3)棧與遞歸的實現(xiàn)。(2)二叉樹的遍歷及有關算法，利用遍歷算法實現(xiàn)二叉樹的其他操作，如計算二叉樹結點個數(shù)、葉子結點個數(shù)、二叉樹的高度等。(3)二叉樹的線索化，線索化二叉樹的特性及尋找某結點的前驅和后繼的方法。(4)樹和森林的定義、存儲結構與二叉樹的轉換。(5)樹的應用，哈夫曼樹及哈夫曼編碼、帶權路徑長度的計算?？荚囈罂荚囈?

5、.熟練掌握二叉樹的結構特性，了解相應的證明方法；2.熟悉二叉樹的各種存儲結構的特點及適用范圍；3.掌握各種遍歷的遞歸算法，靈活運用遍歷算法實現(xiàn)二叉樹的其它操作；4.理解二叉樹線索化的實質是建立結點與其在相應序列中的前驅或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法；5.熟悉樹的各種存儲結構及其特點，6.掌握樹和森林與二叉樹的轉換方法；7.掌握哈夫曼樹的特性及建立哈夫曼樹和哈夫曼編碼的方法

6、。七、圖七、圖考試內容考試內容(1)圖的定義及相關術語和性質。(2)圖的存儲結構四種存儲結構：數(shù)組表示法、鄰接表、十字鏈表和鄰接多重表。(3)圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索，以及相關算法。(4)圖的連通性，連通分量，最小生成樹，構造最小生成樹的兩種算法：普里姆算法和克魯斯卡爾算法。(5)拓撲排序和關鍵路徑。(6)兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法?？荚囈罂荚囈?.掌握理解圖的抽象數(shù)據(jù)類型定義及其基本

7、術語；2.掌握圖的鄰接矩陣和鄰接表的存儲方法；理解圖的十字鏈表存儲；3.掌握圖的遍歷方法及其在鄰接矩陣和鄰接表存儲結構上的實現(xiàn)；4.理解無向圖的連通性；了解有向圖的連通性；5.掌握構造最小生成樹的Prim算法和Kruskal算法的基本思想和求解過程；6.掌握求解最短路徑的Dijkstra算法和Floyd算法的基本思想及過程；7.掌握拓撲序列的定義及拓撲排序算法；8.掌握關鍵路徑的定義及求解過程；理解求關鍵路徑的算法。八、查找八、查找考試