考試科目：917數(shù)據(jù)結(jié)構(gòu)

　　考試大綱

　　一、考試性質(zhì)

　　《數(shù)據(jù)結(jié)構(gòu)》課程考試是為大連海洋大學(xué)招收計(jì)算機(jī)科學(xué)與技術(shù)碩士專業(yè)學(xué)位研究生而設(shè)置的具有選拔性質(zhì)的研究生考試復(fù)試科目，其目的是科學(xué)、公平、有效地測(cè)試考生是否具備繼續(xù)攻讀計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)術(shù)型碩士研究生所需要的基礎(chǔ)知識(shí)和基本技能，評(píng)價(jià)的標(biāo)準(zhǔn)是高等學(xué)校計(jì)算機(jī)相關(guān)專業(yè)本科畢業(yè)生能達(dá)到的及格或及格以上水平，以利于我校擇優(yōu)選拔，確保計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)術(shù)型碩士研究生的招生質(zhì)量。

　　二、考查目標(biāo)

　　《數(shù)據(jù)結(jié)構(gòu)》課程在考察課程基本知識(shí)、基本理論的同時(shí)，注重考查考生運(yùn)用數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)分析、解決實(shí)際問(wèn)題的能力和算法的分析、設(shè)計(jì)及實(shí)現(xiàn)的能力�？忌鷳�(yīng)能：

　　1.理解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的概念。

　　2.熟練掌握各種邏輯結(jié)構(gòu)上的基本操作，及這些基本操作基于不同物理結(jié)構(gòu)的實(shí)現(xiàn)。

　　3.具有針對(duì)實(shí)際問(wèn)題選擇合適數(shù)據(jù)結(jié)構(gòu)的能力。

　　4.熟練掌握查找、排序的基本概念及經(jīng)典的查找、排序算法。

　　5.具有算法的分析、設(shè)計(jì)及其實(shí)現(xiàn)等方面的基本技能和科學(xué)作風(fēng)。

　　三、考試形式和試卷結(jié)構(gòu)

　　一、試卷滿分及考試時(shí)間

　　本試卷滿分為100分，考試時(shí)間為60分鐘。

　　二、答題方式

　　答題方式為閉卷、筆試。

　　三、試卷題型結(jié)構(gòu)

　　客觀題10小題，每小題4分，共40分;主觀題4大題，每小題15分，共60分;合計(jì)100分。

　　四、考察內(nèi)容

　　第一章緒論

　　1.理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型、算法等基本概念

　　2.掌握數(shù)據(jù)邏輯結(jié)構(gòu)的概念及分類

　　3.掌握數(shù)據(jù)物理結(jié)構(gòu)的概念及分類

　　4.了解算法描述規(guī)范以及如何對(duì)算法進(jìn)行分析和評(píng)價(jià)的方法

　　第二章線性表

　　1.掌握線性表的邏輯結(jié)構(gòu)、邏輯特性

　　2.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)及鏈接存儲(chǔ)結(jié)構(gòu)

　　3.掌握單鏈表、循環(huán)鏈表進(jìn)行插入、刪除和查找等基本操作的算法

　　4.了解雙向鏈表進(jìn)行插入、刪除和查找等基本操作的算法

　　第三章棧和隊(duì)列

　　1.掌握棧和隊(duì)列的邏輯結(jié)構(gòu)、邏輯特性

　　2.掌握棧和隊(duì)列的物理結(jié)構(gòu)

　　棧和隊(duì)列的順序存儲(chǔ)、棧和隊(duì)列的鏈接存儲(chǔ)

　　3.掌握對(duì)棧和隊(duì)列進(jìn)行插入、刪除等操作的相應(yīng)算法

　　4.了解利用棧實(shí)現(xiàn)遞歸并解決實(shí)際問(wèn)題的方法

　　第四章串

　　1.理解串的基本概念

　　2.掌握串的物理結(jié)構(gòu)

　　串的順序存儲(chǔ)、串的鏈接存儲(chǔ)

　　3.掌握串的基本運(yùn)算

　　賦值、連接、求串長(zhǎng)、取子串、求子串序號(hào)、插入、刪除和置換等

　　4.了解各種運(yùn)算在文本編輯中的應(yīng)用

　　第五章數(shù)組

　　1.理解多維數(shù)組和稀疏矩陣的概念

　　2.了解多維數(shù)組的順序存儲(chǔ)

　　3.了解稀疏矩陣的壓縮存儲(chǔ)

　　第六章樹(shù)和二叉樹(shù)

　　1.理解樹(shù)形結(jié)構(gòu)的基本概念

　　樹(shù)、森林、二叉樹(shù)、滿二叉樹(shù)、完全二叉樹(shù)、線索二叉樹(shù)、哈夫曼(Huffman)樹(shù)以及與樹(shù)形結(jié)構(gòu)相關(guān)的概念

　　2.掌握二叉樹(shù)的性質(zhì)

　　3.掌握樹(shù)形結(jié)構(gòu)的物理結(jié)構(gòu)

　　二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表表示法)、完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)、樹(shù)和森林的順序存儲(chǔ)結(jié)構(gòu)(雙親表示法)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(孩子兄弟表示法)

　　4.掌握樹(shù)形結(jié)構(gòu)的操作

　　二叉樹(shù)的遍歷方法(前序遍歷法、中序遍歷法和后序遍歷法)、樹(shù)/森林與二叉樹(shù)之間的相互轉(zhuǎn)換、樹(shù)和森林的遍歷方法(按寬度方向和按深度方向進(jìn)行遍歷的方法)、二叉樹(shù)的線索化

　　5.掌握哈夫曼樹(shù)的構(gòu)造，求哈夫曼編碼

　　第七章圖

　　1.理解圖的基本概念

　　2.掌握?qǐng)D的物理結(jié)構(gòu)

　　圖的相鄰矩陣表示法、圖的鄰接表表示法、圖的鄰接多重表表示法、圖的十字鏈表表示法

　　3.掌握?qǐng)D的遍歷方法

　　圖的寬度(廣度)優(yōu)先遍歷、圖的深度優(yōu)先遍歷

　　4.掌握?qǐng)D的操作

　　求圖的生成樹(shù)或生成森林、求帶權(quán)圖的比較短路經(jīng)、構(gòu)造網(wǎng)絡(luò)的比較小生成樹(shù)、對(duì)有向圖進(jìn)行拓?fù)渑判?/p>

　　第八章查找

　　1.理解靜態(tài)查找表、動(dòng)態(tài)查找表和哈希表(hash)的基本概念

　　2.掌握靜態(tài)查找表的查找方法

　　基于無(wú)序表的靜態(tài)查找、基于有序表的靜態(tài)查找、基于部分有序表的靜態(tài)查找

　　3.掌握動(dòng)態(tài)查找表的查找方法

　　基于二叉排序樹(shù)的動(dòng)態(tài)查找、基于平衡二叉排序樹(shù)的動(dòng)態(tài)查找等

　　4.掌握哈希函數(shù)的構(gòu)造方法和解決沖突的方法

　　第九章內(nèi)部排序

　　1.理解內(nèi)部排序的基本概念

　　2.掌握幾種典型的排序算法

　　直接插入排序、簡(jiǎn)單選擇排序、起泡排序、快速排序、歸并排序

　　3.掌握分析各種排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度

　　4.了解分析各種排序算法的穩(wěn)定性

　　相關(guān)推薦：

　　2017年全國(guó)碩士研究生考試成績(jī)查詢時(shí)間

　　2018考研：全國(guó)各地區(qū)、學(xué)科備考交流群

　　歡迎關(guān)注研究生微信公眾號(hào)