2017年大連海洋大學917數(shù)據(jù)結構復試考研大綱

　　考試科目：917數(shù)據(jù)結構

　　考試大綱

　　一、考試性質

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

　　二、考查目標

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

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

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

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

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

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

　　三、考試形式和試卷結構

　　一、試卷滿分及考試時間

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

　　二、答題方式

　　答題方式為閉卷、筆試。

　　三、試卷題型結構

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

　　四、考察內容

　　第一章緒論

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

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

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

　　4.了解算法描述規(guī)范以及如何對算法進行分析和評價的方法

　　第二章線性表

　　1.掌握線性表的邏輯結構、邏輯特性

　　2.掌握線性表的順序存儲結構及鏈接存儲結構

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

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

　　第三章棧和隊列

　　1.掌握棧和隊列的邏輯結構、邏輯特性

　　2.掌握棧和隊列的物理結構

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

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

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

　　第四章串

　　1.理解串的基本概念

　　2.掌握串的物理結構

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

　　3.掌握串的基本運算

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

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

　　第五章數(shù)組

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

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

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

　　第六章樹和二叉樹

　　1.理解樹形結構的基本概念

　　樹、森林、二叉樹、滿二叉樹、完全二叉樹、線索二叉樹、哈夫曼(Huffman)樹以及與樹形結構相關的概念

　　2.掌握二叉樹的性質

　　3.掌握樹形結構的物理結構

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

　　4.掌握樹形結構的操作

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

　　5.掌握哈夫曼樹的構造，求哈夫曼編碼

　　第七章圖

　　1.理解圖的基本概念

　　2.掌握圖的物理結構

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

　　3.掌握圖的遍歷方法

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

　　4.掌握圖的操作

　　求圖的生成樹或生成森林、求帶權圖的比較短路經、構造網絡的比較小生成樹、對有向圖進行拓撲排序

　　第八章查找

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

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

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

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

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

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

　　第九章內部排序

　　1.理解內部排序的基本概念

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

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

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

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

　　相關推薦：

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

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

　　歡迎關注研究生微信公眾號