2019年大連海事大學(xué)工業(yè)工程（專業(yè)學(xué)位）考研專業(yè)課數(shù)據(jù)結(jié)構(gòu)（同等學(xué)力加試）考試大綱

1、大連海事大學(xué)大連海事大學(xué)碩士研究生入學(xué)考試碩士研究生入學(xué)考試大綱大綱考試科目：數(shù)據(jù)結(jié)構(gòu)試卷滿分及考試時間：試卷滿分為100分，考試時間為180分鐘。一、數(shù)據(jù)結(jié)構(gòu)基本概念一、數(shù)據(jù)結(jié)構(gòu)基本概念考試內(nèi)容考試內(nèi)容(1)數(shù)據(jù)結(jié)構(gòu)的基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法等。(2)抽象數(shù)據(jù)類型的表示和實現(xiàn)。(3)算法時間復(fù)雜度和空間復(fù)雜度的分析?？荚囈罂荚囈?.掌握和理解數(shù)據(jù)結(jié)構(gòu)的概念；2.運用形式化方法定義和描述一個

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

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

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

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

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

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