906《數據結構》
一、考試性質
《數據結構》是碩士研究生招生院校招收電子信息專業碩士研究生而設置的具有選拔性質的考試科目。本考試大綱的制定力求反映招生類型的特點，科學、公平、準确、規範地測評考生的相關基礎知識掌握水平，考生分析問題和解決問題及綜合知識運用能力。考生應根據本大綱的内容和要求自行組織學習内容和掌握有關知識。
二、考試的總體要求
要求考生通過《數據結構》課程的學習，掌握數據結構的基本概念、基本原理和基本方法；掌握數據的邏輯結構、存儲結構及基本操作的實現，能夠對算法進行基本的時間複雜度與空間複雜度的分析；能夠運用數據結構基本原理和方法進行問題的分析與求解，具備采用C或C++語言設計與實現算法的能力。
三、考試内容
第1章 概論
1、考試内容：
（1）數據結構的基本概念
（2）算法的定義
1.算法複雜度
2.漸進表示法
2、考試要求
（1）掌握數據結構的基本概念；
（2）了解數據的邏輯結構、存儲結構以及二者之間的關系；
（3）掌握算法分析方法；
（4）掌握大O記号的表示。
第2章 數據結構實現基礎
（略）本章内容将在算法分析、設計中涉及，不做具體考點要求。
第3章 線性表
1、考試内容：
（1）線性表的定義和基本操作
（2）線性表的實現
1.順序存儲
2.鍊式存儲
3.線性表的應用
4.廣義表與多重鍊表
（3）堆棧和隊列的基本概念
（4）堆棧和隊列的順序存儲結構
（5）堆棧和隊列的鍊式存儲結構
（6）堆棧和隊列的應用
2、考試要求
（1）了解順序存儲結構和鍊接存儲結構的基本思想；
（2）掌握順序表和單鍊表的基本算法；
（3）了解順序表和單鍊表基本操作的時間性能；
（4）了解堆棧和隊列的操作特性；
（5）掌握堆棧和隊列基本操作的實現；
（6）了解循環隊列的存儲方法；
（7）掌握循環隊列中隊空和隊滿的判定條件；
（8）熟練掌握各種線性表的應用。
第4章 樹與二叉樹
1、考試内容：
（1）樹的基本概念
（2）二叉樹
1.二叉樹的定義及其主要特征
2.二叉樹的順序存儲結構和鍊式存儲結構
3.二叉樹的操作
（3）二叉樹的應用
1.二叉搜索樹
2.平衡二叉樹
3.堆及其操作
4.哈夫曼樹和哈夫曼編碼
5.集合及其運算
2、考試要求
（1）掌握樹和二叉樹的性質；
（2）掌握樹和二叉樹的存儲表示；
（3）掌握二叉樹的遍曆及遞歸/非遞歸算法實現；
（4）了解樹與二叉樹的轉換關系；
（5）熟練掌握二叉樹的幾種應用。
第5章 散列查找
1、考試内容：
（1）查找及散列查找的基本概念
（2）散列函數的構造方法
（3）處理沖突的方法
（4）散列表的性能分析
（5）散列查找的應用
2、考試要求
（1）了解散列函數的設計方法和原則
（2）了解處理沖突的常用方法；
（3）掌握平均成功/失敗查找長度的計算；
（4）了解各種查找技術的時間性能及對比。
第6章 圖
1、考試内容：
（1）圖的基本概念
（2）圖的存儲結構及基本操作
1.鄰接矩陣
2.鄰接表
（3）圖的遍曆
1.深度優先搜索
2.廣度優先搜索
（4）圖的基本應用
1.最小生成樹的概念及兩種構造算法
2.單源/多源最短路徑
3.拓撲排序
4.關鍵路徑計算
2、考試要求
（1）了解圖的基本術語；
（2）了解圖的各種存儲表示：
（3）掌握圖的兩種遍曆的思想及算法，能運用圖的遍曆算法解決圖的其他相關問題；
（4）熟練掌握圖的各種應用：最小生成樹算法、最短路徑算法、拓撲排序算法、關鍵路徑算法。
第7章 排序
1、考試内容：
（1）排序的基本概念
（2）選擇排序
1.簡單選擇排序
2.堆排序
（3）插入排序
1.直接插入排序
2.希爾排序
（4）交換排序
1.冒泡排序
2.快速排序
（5）歸并排序
（6）基數排序
（7）各種内部排序算法的比較
2、考試要求
（1）了解各種排序算法的基本思想；
（2）掌握各種排序算法的執行過程；
（3）了解各種排序算法的設計；
（4）掌握各種排序算法時間複雜度；
（5）了解各種排序算法之間的比較。
第8章 綜合應用案例分析
1、考試内容：
（1）銀行排隊問題
（2）暢通工程問題
2、考試要求
深刻理解各種數據結構及算法的設計思想，并能應用相應數據結構和算法的設計思想解決實際問題；對改進的算法，分析其改進的着眼點是什麼，自己能否從某一個方面改進一個算法，從而提高算法設計能力；對各類相似算法方法進行綜合對比，從而得出一般性結論，在實際應用中可以根據情況選取合适的算法。
四、考試形式與試卷結構
1、考試形式：閉卷、筆試。
2、試卷分值：150分。
3、考試時間：180分鐘。
4、題型結構（包括但不限于）：填空題、選擇題、判斷題、算法分析/設計題。
5、其他要求：無。
五、參考教材
1、陳越主編，《數據結構》（第二版），高等教育出版社，2016.6
