|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
遼寧科技大學 2018 年全國碩士研究生入學考試
《數據結構》考試大綱
本考試大綱由電信學院教授委員會于 2015 年 7 月 7 日通過。
科目代碼：812
I.考試性質
數據結構考試是為遼寧科技大學電信學院控制科學與工程和電力電子與電力傳動學科招收碩士研
究生而設置的具有選拔性質的全國統一入學考試科目，其目的是科學、公平、有效地測試學生掌握大
學本科階段數據結構課程的基本知識、基本理論，以及運用數據結構學科的基礎理論和方法分析和解
決問題的能力，評價的標準是高等學校本科畢業生能達到的及格或及格以上水平，以保證被錄取者具
有數據表示和操作及問題求解的素質，并有利于其他高等院校和科研院所相關專業上的擇優選拔。
II.考查目標
數據結構科考試涵蓋數據結構的基本概念、算法及算法性能分析、線性表順序和鏈式存儲及其上
的操作、棧和隊列的性質，存儲和操作、二維數組及特殊矩陣的存儲和元素地址求解、樹和二叉樹的
定義，性質，存儲表示，二叉樹的遍歷，樹與二叉樹及森林的轉換，哈夫曼樹及哈夫曼編碼、圖的定
義及重要術語，圖的存儲及深度和廣度遍歷，圖的應用（最小生成樹，最短路徑，拓撲排序，關鍵路
徑）、查找的定義和查找方法，二叉排序樹，平衡二叉樹的創建，散列應用、排序的定義及排序方法尤
其是快速排序和堆排序。要求考生：
（1）掌握數據結構的里線性表，樹和圖，查找，排序的相關概念及性質、各種邏輯結構在計算機
內部的表示，在各種結構上實現重要操作的算法及算法性能的分析。
（2）能熟練運用鏈表，棧和隊列，樹的遍歷，哈夫曼樹，圖的遍歷，最小生成樹，拓撲排序，最
短路徑，查找，排序求解問題。
Ⅲ.考試形式和試卷結構
1、試卷滿分及考試時間
本試卷滿分為 150 分，考試時間為 180 分鐘
2、答題方式
答題方式為閉卷，筆試。
3、試卷內容結構
數據結構概念、性質，算法及算法性能分析約 30%
數據結構應用鏈表，棧和隊列，樹的遍歷，哈夫曼樹，圖的遍歷，最小生成樹，拓撲排序，最短
路徑，查找，排序約 50%
算法及程序設計約 20%
Ⅳ.試卷題型結構
題型包括選擇題、填空題、判斷題、應用題和程序題（分程序閱讀寫結果和程序設計兩類）。
Ⅴ.考查內容
（一）緒論
21
遼寧科技大學 碩士研究生自命題大綱
了解和掌握數據結構的基本概念，這些概念包括:數據、數據元素、數據類型、抽象數
據類型、數據邏輯結構、數據存儲結構、數據結構上的操作集合、 算法及算法特點等。了
解和掌握算法效率分析的目的和方法。
考點：數據結構的定義，數據邏輯結構和存儲結構以及二者之間的關系、算法效率分析
（時間復雜度求解）。
（二）線性表
了解線性表的邏輯結構和基本操作；理解線性表的順序存儲結構和實現方法；理解線性
表的鏈式存儲結構和實現方法；了解單循環鏈表和雙向鏈表的概念和基本設計方法。
考點：單鏈表的存儲結構設計及操作實現算法，利用單鏈表完成差或等比及判斷雙鏈表
是否對稱的應用。
（三）棧和隊列
理解棧的概念、順序棧和鏈式棧的設計方法；理解隊列的概念、順序循環隊列和鏈式隊
列的設計方法；了解優先級隊列以及優先級隊列和一般隊列的差別；了解堆棧和隊列的應用
方法。
考點：棧和隊列的操作特性，雙棧共享空和滿的條件，循環隊列空，滿的條件及隊列中
元素個數的求解。
（四）字符串和多維
理解串的概念；了解串基本操作的實現方法；了解串的 BF 模式匹配方法，掌握 KMP
模式匹配方法。熟練掌握二維數組的概念，了解特殊矩陣和稀疏矩陣的壓縮存儲方法；及稀
疏矩陣的三元組表的概念。
考點：串的基本操作應用，KMP 模式匹配的 NEXT 求解；數組中元素地址的求解，特
殊矩陣的存儲。
（五）樹與二叉樹
了解樹的定義、表示方法及其典型存儲結構；理解二叉樹的定義、性質、存儲結構和操作
的實現方法；掌握二叉樹的遍歷算法及其應用實現；理解哈夫曼樹的概念及其應用；了解樹與二
叉樹的關系。
考點：二叉樹的性質；二叉樹的遍歷算法及應用；哈夫曼樹的構建和編碼的應用方法。
并能利用樹的遍歷實現如統計二叉樹深度或寬度的算法，會實現樹、二叉樹和森林的相互轉
換。
（六）圖
了解圖的基本概念和術語；掌握圖的鄰接矩陣和鄰接表存儲結構以及圖操作的實現方法；
理解圖的深度和廣度優先遍歷方法和算法設計方法；理解最小生成樹的概念以及普里姆算法
和單源最短路徑的狄杰斯特拉算法，拓撲排序和關鍵路徑。
考點：圖的鄰接矩陣和圖的鄰接表存儲結構；圖的深度和廣度遍歷算法；最小生成樹
的求解，單源點最短路徑的求解，拓撲排序。
（七）查找
了解查找的基本概念和查找方法的評判標準；理解順序查找，掌握折半（二分）查找的
算法設計方法；掌握二叉排序樹和平衡二叉樹樹的基本結構和插入、刪除方法；掌握散列函
數、散列沖突函數和散列表的構造方法。
考點：二叉排序樹和平衡二叉樹的構造；散列函數、散列沖突函數和散列表（開散列和
閉散列）的構造方法。
（八）排序
了解排序的基本概念和排序算法的評判標準；掌握直接插入排序、希爾排序、直接選擇
排序、堆排序、快速排序、二路歸并排序、基數排序的算法思想和算法設計方法；理解各種
排序方法的性能特點。
考點：希爾排序、堆排序、快速排序的實現，各種排序方法的時間復雜度分析。
VI 參考文獻
《數據結構（C++版）》（第二版），王紅梅編著，清華大學出版社，2011 年。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
