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

　　考試大綱

　　一、考試性質(zhì)

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

　　二、考查目標

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

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

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

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

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

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

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

　　一、試卷滿分及考試時間

　　本試卷滿分為100分，考試時間為60分鐘。

　　二、答題方式

　　答題方式為閉卷、筆試。

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

　　客觀題10小題，每小題4分，共40分;主觀題4大題，每小題15分，共60分;合計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ī)范以及如何對算法進行分析和評價的方法

　　第二章線性表

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

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

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

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

　　第三章棧和隊列

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

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

　　棧和隊列的順序存儲、棧和隊列的鏈接存儲

　　3.掌握對棧和隊列進行插入、刪除等操作的相應算法

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

　　第四章串

　　1.理解串的基本概念

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

　　串的順序存儲、串的鏈接存儲

　　3.掌握串的基本運算

　　賦值、連接、求串長、取子串、求子串序號、插入、刪除和置換等

　　4.了解各種運算在文本編輯中的應用

　　第五章數(shù)組

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

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

　　3.了解稀疏矩陣的壓縮存儲

　　第六章樹和二叉樹

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

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

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

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

　　二叉樹的鏈式存儲結(jié)構(gòu)(二叉鏈表表示法)、完全二叉樹的順序存儲結(jié)構(gòu)、樹和森林的順序存儲結(jié)構(gòu)(雙親表示法)和鏈式存儲結(jié)構(gòu)(孩子兄弟表示法)

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

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

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

　　第七章圖

　　1.理解圖的基本概念

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

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

　　3.掌握圖的遍歷方法

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

　　4.掌握圖的操作

　　求圖的生成樹或生成森林、求帶權(quán)圖的比較短路經(jīng)、構(gòu)造網(wǎng)絡的比較小生成樹、對有向圖進行拓撲排序

　　第八章查找

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

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

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

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

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

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

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

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

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

　　直接插入排序、簡單選擇排序、起泡排序、快速排序、歸并排序

　　3.掌握分析各種排序算法的時間復雜度和空間復雜度

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

　　相關(guān)推薦：

　　2017年全國碩士研究生考試成績查詢時間

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

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