2019年大連海事大學(xué)計算機科學(xué)與技術(shù)考研專業(yè)課數(shù)據(jù)結(jié)構(gòu)考試大綱

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

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

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

4、找表查找表的相關(guān)概念；靜態(tài)查找表、有序表的查找、索引順序表的查找；動態(tài)查找表、二叉排序樹與平衡二叉樹、B樹與B樹；哈希(Hash)表；關(guān)于查找表的問題實例。9.排序排序的概念；穩(wěn)定排序、不穩(wěn)定排序、內(nèi)部排序、外部排序；插入排序、快速握各種排序方法的時間復(fù)雜度。了解簡單(低效)排序方法與復(fù)雜(高效)排序方法的區(qū)別與應(yīng)用選擇。了解外部排序算法優(yōu)化的目標(biāo)和主要手段，熟悉應(yīng)用敗者樹實現(xiàn)多路歸并，以及通過置換選擇進行外部排序的方法。13.了解文件