2019年大連海事大學(xué)管理科學(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.掌握數(shù)據(jù)結(jié)構(gòu)的相關(guān)術(shù)語與基本

2、概念；3.掌握算法的時(shí)間復(fù)雜度及判斷算法好壞的方法。二、線性表二、線性表考試內(nèi)容考試內(nèi)容(1)線性表的類型定義。(2)線性表的順序存儲(chǔ)方法和實(shí)現(xiàn)，相關(guān)查找、插入和刪除算法算法實(shí)現(xiàn)，應(yīng)用舉例；(3)線性表的鏈?zhǔn)酱鎯?chǔ)方法和實(shí)現(xiàn)，相關(guān)查找、插入和刪除算法算法實(shí)現(xiàn)，應(yīng)用舉例?？荚囈罂荚囈?.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的各自特點(diǎn)；2.熟練掌握順序表和鏈?zhǔn)奖淼牟迦?、刪除和查找等基本操作；3.能夠編制和實(shí)現(xiàn)順序表和鏈?zhǔn)奖砘静僮鞯某绦?/p>

3、；三、棧和隊(duì)列三、棧和隊(duì)列考試內(nèi)容考試內(nèi)容(1)棧的定義及特點(diǎn)，棧的順序存儲(chǔ)和鏈接存儲(chǔ)的表示和實(shí)現(xiàn)，進(jìn)棧出棧算法。(2)棧的應(yīng)用舉例，如表達(dá)式求值、數(shù)制轉(zhuǎn)換等。(3)隊(duì)列的定義及特點(diǎn)，隊(duì)列的表示和實(shí)現(xiàn)，循環(huán)隊(duì)列和鏈隊(duì)列的進(jìn)隊(duì)出隊(duì)算法。考試要求考試要求1.掌握棧和隊(duì)列兩種特殊的線性表的特點(diǎn)2.熟練掌握棧的基本操作即進(jìn)棧、出棧、?？?、棧滿、取棧頂元素等操作；3.熟練掌握隊(duì)列的基本操作即入隊(duì)列、出隊(duì)列、判斷隊(duì)列空、隊(duì)列滿等；四、串四、串考試內(nèi)

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

5、Kruskal算法的基本思想和求解過程；5.掌握求解最短路徑的Dijkstra算法和Floyd算法的基本思想及過程；6.掌握拓?fù)湫蛄械亩x及拓?fù)渑判蛩惴ǎ?.掌握關(guān)鍵路徑的定義及求解過程；八、查找八、查找考試內(nèi)容考試內(nèi)容(1)靜態(tài)查找：順序查找、折半查找的查找方法及其實(shí)現(xiàn)方法。(2)動(dòng)態(tài)查找：二叉排序樹、平衡二叉樹。二叉排序樹的插入和查找算法及其實(shí)現(xiàn)。(3)哈希表：哈希函數(shù)的構(gòu)造方法、處理沖突的方法、哈希表的查找與分析?？荚囈罂荚囈?/p>

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