2021湖南工商大學數據結構專業（學碩）研究生考試大綱 正文

2021年碩士研究生入學考試自命題考試大綱
考試科目代碼：808                          考試科目名稱：數據結構
一、試卷結構
1、試卷成績及考試時間
本試卷滿分為150分，考試時間為180分鐘。
2、答題方式：閉卷、筆試
3、試卷內容結構
數據結構 150分
4、題型結構
名詞解釋：4小題，每小題5分，共20分
問答題：4小題，每小題5分，共20分
應用題：4小題，每小題15分，共60分
算法設計題：2小題，每小題25分，共50分
二、考試內容與考試要求
參考書目：
1、李春葆. 數據結構教程（第5版）. 北京：清華大學出版社，2017.
2、馬克·艾倫·維斯. 數據結構與算法分析：C語言描述（英文版·原書第2版）. 北京：機械工業出版社，2020.
●考試目標：
1.深刻理解并領會數據結構的基本概念和基本理論，熟練掌握常用數據結構的邏輯結構、存儲結構及其相關的操作算法；
2.掌握算法的時間復雜度分析和空間復雜度分析的方法；
3．針對問題的特點選擇合適的數據結構，具有構建實用高效的算法及良好的程序設計能力；
4.準確、恰當地使用計算機專業術語，論述有據，條理清晰，符合邏輯，文字表達通順。
●考試內容
（一）數據結構緒論
1.數據、數據元素、數據項、數據結構等基本概念；
2.數據結構的邏輯結構、存儲結構及數據運算的含義及其相互關系；
3.數據的基本邏輯結構和四種常用的存儲表示方法；
4.算法及算法的特點，掌握算法描述和算法分析的方法。
（二）線性表、棧和隊列
1．線性表的基本邏輯結構特點、棧和隊列的受限特性；
2．線性表、棧、隊列在順序存儲結構下的基本運算的實現；
3．線性表、棧、隊列在鏈式存儲結構下的基本運算的實現；
4．利用線性表、棧、隊列設計算法解決實際的應用問題。
（三）數組和廣義表
1．數組和廣義表的邏輯結構特征；
2．數組順序存儲結構下隨機存儲的特性及地址計算方式；
3．特殊矩陣在壓縮存儲時的地址計算方法；
4．稀疏矩陣壓縮存儲的三元組表表示方法；
（四）樹和二叉樹
1.樹和二叉樹的基本概念、掌握樹的邏輯結構特征；
2.樹和二叉樹的性質；
3.二叉樹的在鏈式存儲結構下的基本運算實現，創建二叉樹、訪問節點，及遍歷運算等；
4.三種遍歷所得到的相應的結點訪問序列；理解以遍歷算法為基礎，應用遞歸方法設計有關算法解決簡單的應用問題；
5.二叉樹線索化的目的及實現；
6.構造二叉樹的方法；
7.哈夫曼樹的含義，掌握哈夫曼算法的思想及哈夫曼樹的應用。
（五）圖
1.圖的邏輯結構特征，理解圖的常用術語；
2.鄰接矩陣和鄰接表這兩種存儲結構的特點及適用范圍；
3.圖的基本運算的實現及圖的深度優先搜索和廣度優先搜索兩種遍歷算法；
4.利用圖的基本運算設計算法解決實際的應用問題；
5.生成樹和最小生成樹的概念，根據Prim和Kruskal算法構造出最小生成樹；
6.單源最短路徑的Dijkstra算法的基本思想，根據Dijkstra算法求解最短路徑的過程；
7.關鍵路徑的求取。
（六）查找
1.順序查找、二分查找、分塊查找的基本思想、算法實現和查找效率分析；
2.二叉查找樹和B-樹的定義和特點以及用途；
3.二叉查找樹的插入、刪除、建樹和查找算法及時間性能；
4.哈希表、哈希函數、哈希地址和裝填因子等有關概念；
5.解決哈希沖突的方法；
（七）內排序
1．插入類排序基本思想和典型算法實現；
2. 選擇類排序基本思想和典型算法實現；
3. 交換類排序基本思想和典型算法實現；
4．歸并排序的基本思想和算法實現。

湖南工商大學

本文來源：http://m.btfokj.cn/hnuc/cankaoshumu_382685.html