2017年大連海洋大學917數據結構復試考研大綱

　　考試科目：917數據結構

　　考試大綱

　　一、考試性質

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

　　二、考查目標

　　《數據結構》課程在考察課程基本知識、基本理論的同時，注重考查考生運用數據的邏輯結構和物理結構分析、解決實際問題的能力和算法的分析、設計及實現的能力。考生應能：

　　1.理解數據的邏輯結構和物理結構的概念。

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

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

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

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

　　三、考試形式和試卷結構

　　一、試卷滿分及考試時間

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

　　二、答題方式

　　答題方式為閉卷、筆試。

　　三、試卷題型結構

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

　　四、考察內容

　　第一章緒論

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

　　2.掌握數據邏輯結構的概念及分類

　　3.掌握數據物理結構的概念及分類

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

　　第二章線性表

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

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

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

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

　　第三章棧和隊列

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

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

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

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

　　4.了解利用棧實現遞歸并解決實際問題的方法

　　第四章串

　　1.理解串的基本概念

　　2.掌握串的物理結構

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

　　3.掌握串的基本運算

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

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

　　第五章數組

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

　　2.了解多維數組的順序存儲

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

　　第六章樹和二叉樹

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

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

　　2.掌握二叉樹的性質

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

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

　　4.掌握樹形結構的操作

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

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

　　第七章圖

　　1.理解圖的基本概念

　　2.掌握圖的物理結構

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

　　3.掌握圖的遍歷方法

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

　　4.掌握圖的操作

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

　　第八章查找

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

　　2.掌握靜態查找表的查找方法

　　基于無序表的靜態查找、基于有序表的靜態查找、基于部分有序表的靜態查找

　　3.掌握動態查找表的查找方法

　　基于二叉排序樹的動態查找、基于平衡二叉排序樹的動態查找等

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

　　第九章內部排序

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

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

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

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

　　4.了解分析各種排序算法的穩定性

　　相關推薦：

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

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

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