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

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

2、；循環(huán)鏈表與雙向鏈表；關(guān)于線(xiàn)性表的問(wèn)題實(shí)例。3.棧與隊(duì)列棧的定義與結(jié)構(gòu)特點(diǎn)；棧的存儲(chǔ)結(jié)構(gòu)及其基本操作；遞歸與遞歸的執(zhí)行過(guò)程；關(guān)于棧的問(wèn)題實(shí)例。隊(duì)列的定義與結(jié)構(gòu)特點(diǎn)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)及其基本操作；循環(huán)隊(duì)列；關(guān)于隊(duì)列的問(wèn)題實(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.樹(shù)與二叉

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

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