2017年渤海大學數據結構考研大綱

考研專業課大綱來源：中國考研網 2016-12-08　相關院校：渤海大學

《數據結構》考試大綱

一、考試性質

《數據結構》考試是為渤海大學信息科學與技術學院招收碩士研究生而設置的具有選拔性質的專業考試科目，其目的是科學、公平、有效地測試學生掌握大學本科階段數據結構的基本概念以及運用它們設計程序的能力，評價的標準是高等院校本科畢業生能夠達到的及格或者及格以上水平，以保證被錄取者對數據結構的相關知識有較好的掌握，為被錄取者在研究生階段的研究工作能夠順利進行做好鋪墊。

二、考查目標

數據結構考試要求考生：
1、熟悉數據結構中的基本概念，能夠準確、恰當的使用本學科的專業術語；
2、掌握計算機能處理的數據結構的特性；
3、能夠為所處理的數據選擇適當的邏輯結構、存儲結構；
4、能夠基于數據結構編寫結構清楚和正確易讀的算法；
5、初步掌握算法的時間分析和空間分析的技術。

三、考查內容

1、數據結構有關的概念和術語
（1）數據類型和抽象數據類型的概念；
（2）數據結構的基本概念和相關術語；
（3）算法，算法設計的要求，算法效率的度量。
2、線性表
（1）線性表的定義和基本操作、靜態鏈表的概念；
（2）順序表、單鏈表、循環鏈表和雙向鏈表的概念，順序表的應用；
（3）線性表的順序存儲結構及鏈式存儲結構的定義，查找、插入和刪除等基本操作的實現。
3、棧和隊列
（1）棧和隊列的概念、結構特性、典型應用；
（2）棧和隊列的順序存儲結構和鏈式存儲結構實現；
（3）遞歸的概念及執行過程。
4、數組和廣義表
（1）數組的概念和數組的存儲結構，廣義表的存儲結構；
（2）特殊矩陣和稀疏矩陣的壓縮存儲方法。
5、樹和二叉樹
（1）樹的定義、表示方法和基本操作；
（2）二叉樹的概念、性質、存儲結構和基本操作；
（3）二叉樹遍歷的遞歸算法及非遞歸算法；
（4）樹和森林的遍歷，樹與二叉樹的轉換方法；
（5）哈夫曼樹和哈夫曼編碼的概念，哈夫曼樹的構造方法。
6、圖算法及其應用
（1）圖的基本概念、鄰接矩陣和鄰接表存儲結構
（2）圖的遍歷算法；
（3）最小生成樹算法和最短路徑算法；
（4）有向圖的拓撲排序算法。
7、查找算法及其應用
（1）靜態查找表：順序表的查找、有序表的查找、索引順序表的查找；
（2）動態查找表：二叉排序樹和平衡二叉樹；
（3）哈希表：哈希函數的構造方法、沖突處理的方法、哈希表的查找及其分析。
8、排序算法及其應用
插入排序、快速排序、選擇排序、堆排序、歸并排序、基數排序的算法思想、復雜度分析以及它們之間的比較。