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

1、大連海事大學(xué)碩士研究生入學(xué)考試大綱大連海事大學(xué)碩士研究生入學(xué)考試大綱考試科目：數(shù)據(jù)結(jié)構(gòu)試卷滿分及考試時(shí)間：試卷滿分為100分，考試時(shí)間為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ù)類型的表示和實(shí)現(xiàn)。(3)算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析?？荚囈罂荚囈?.掌握和理解數(shù)據(jù)結(jié)構(gòu)的概念；2.運(yùn)用形式化方法定義和描述一個(gè)

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

3、的不同特點(diǎn)及其適用場(chǎng)合?？荚囈罂荚囈?.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的各自特點(diǎn)；2.區(qū)分?jǐn)?shù)組和順序表及線性表的特征與關(guān)聯(lián)；3.熟練掌握順序表和鏈?zhǔn)奖淼牟迦?、刪除和查找等基本操作；4.能夠編制和實(shí)現(xiàn)順序表和鏈?zhǔn)奖砘静僮鞯某绦颍?.掌握線性表在計(jì)算機(jī)內(nèi)部與外部所起的重要作用；通過(guò)對(duì)它們各自算法的時(shí)間復(fù)雜度分析，能夠綜合判斷和衡量一個(gè)好的算法即程序的標(biāo)準(zhǔn)。三、棧和隊(duì)列三、棧和隊(duì)列考試內(nèi)容考試內(nèi)容(1)棧的定義及特點(diǎn)，棧的順序存

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

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

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

7、術(shù)語(yǔ)；2.掌握?qǐng)D的鄰接矩陣和鄰接表的存儲(chǔ)方法；理解圖的十字鏈表存儲(chǔ)；3.掌握?qǐng)D的遍歷方法及其在鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；4.理解無(wú)向圖的連通性；了解有向圖的連通性；5.掌握構(gòu)造最小生成樹的Prim算法和Kruskal算法的基本思想和求解過(guò)程；6.掌握求解最短路徑的Dijkstra算法和Floyd算法的基本思想及過(guò)程；7.掌握拓?fù)湫蛄械亩x及拓?fù)渑判蛩惴ǎ?.掌握關(guān)鍵路徑的定義及求解過(guò)程；理解求關(guān)鍵路徑的算法。八、查找八、查找考試