2019年大連海事大學(xué)軟件工程專碩考試大綱【初試】數(shù)據(jù)結(jié)構(gòu)

1、大連海事大學(xué)大連海事大學(xué)碩士研究生入學(xué)考試碩士研究生入學(xué)考試大綱大綱考試科目：數(shù)據(jù)結(jié)構(gòu)試卷滿分及考試時(shí)間：試卷滿分為150分，考試時(shí)間為180分鐘?？荚噧?nèi)容考試內(nèi)容1.緒論問題、問題實(shí)例；數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)；集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)；邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)；算法及其特性、算法的正確性、可讀性、健壯性、算法的時(shí)間與空間復(fù)雜度分析及其度量。2.線性表線性表的定義與結(jié)構(gòu)特點(diǎn)；線性表的存儲(chǔ)結(jié)構(gòu)及其基本操作；有序表；靜態(tài)鏈表

2、；循環(huán)鏈表與雙向鏈表；關(guān)于線性表的問題實(shí)例。3.棧與隊(duì)列棧的定義與結(jié)構(gòu)特點(diǎn)；棧的存儲(chǔ)結(jié)構(gòu)及其基本操作；遞歸與遞歸的執(zhí)行過程；關(guān)于棧的問題實(shí)例。隊(duì)列的定義與結(jié)構(gòu)特點(diǎn)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)及其基本操作；循環(huán)隊(duì)列；關(guān)于隊(duì)列的問題實(shí)例。4.串串的定義與結(jié)構(gòu)特點(diǎn)；串的存儲(chǔ)結(jié)構(gòu)及其基本操作；串的模式匹配算法。5.數(shù)組與廣義表數(shù)組的定義與結(jié)構(gòu)特點(diǎn)；數(shù)組的存儲(chǔ)結(jié)構(gòu)及其基本操作；矩陣的壓縮存儲(chǔ)。廣義表的定義與結(jié)構(gòu)特點(diǎn)；廣義表的存儲(chǔ)結(jié)構(gòu)及其基本操作。6.樹與二叉

3、樹樹的定義與結(jié)構(gòu)特點(diǎn)；樹的相關(guān)概念；有序樹與無序樹；森林；二叉樹的定義與結(jié)構(gòu)特點(diǎn)；二叉樹的性質(zhì)；二叉樹的存儲(chǔ)結(jié)構(gòu)及其基本操作；遍歷二叉樹與線索二叉樹；樹與森林的存儲(chǔ)結(jié)構(gòu)；樹與二叉樹的轉(zhuǎn)換關(guān)系；樹與森林的遍歷；Huffman樹及其應(yīng)用；關(guān)于樹與二叉樹的問題實(shí)例。7圖圖的定義與結(jié)構(gòu)特點(diǎn)；圖的相關(guān)概念；有向圖、無向圖、有向網(wǎng)、無向網(wǎng)；圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷；最小生成樹；有向無環(huán)圖及其應(yīng)用、拓?fù)渑判?、關(guān)鍵路徑；最短路徑；關(guān)于圖的問題實(shí)例。8.查

4、找表查找表的相關(guān)概念；靜態(tài)查找表、有序表的查找、索引順序表的查找；動(dòng)態(tài)查找表、二叉排序樹與平衡二叉樹、B樹與B樹；哈希(Hash)表；關(guān)于查找表的問題實(shí)例。9.排序排序的概念；穩(wěn)定排序、不穩(wěn)定排序、內(nèi)部排序、外部排序；插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序、各種排序方法的比較分析；外部排序者樹實(shí)現(xiàn)多路歸并，以及通過置換選擇進(jìn)行外部排序的方法。13.了解文件的相關(guān)概念。●參閱1.《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏、吳偉民編著，清華大