2021湖南工商大學(xué)數(shù)據(jù)結(jié)構(gòu)專業(yè)（專碩）研究生考試大綱 正文

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

湖南工商大學(xué)

本文來源：http://www.lyhuahuisp.com/hnuc/cankaoshumu_382697.html