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

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

湖南工商大學(xué)

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