2021昆明理工大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法分析專業(yè)研究生考試大綱 正文

第一部分 考試形式與試卷結(jié)構(gòu)

一、試卷滿分及考試時(shí)間

試卷滿分為150分，考試時(shí)間為180分鐘。

二、答題方式

答題方式為閉卷、筆試。

三、試卷內(nèi)容結(jié)構(gòu)

基本概念、基本知識(shí)、基本方法約占40%～50%；
綜合應(yīng)用、算法和程序設(shè)計(jì)與算法分析約占60%～50%。

四、試卷題型結(jié)構(gòu)

試卷共150分,基本的考試題型為：
(1)單項(xiàng)選擇題和多項(xiàng)選擇題；
(2)填空題(基本概念、基本知識(shí)、基本方法)；
(3)畫圖題；
(4)簡(jiǎn)答題；
(5)應(yīng)用題(求解問題)；
(6)算法和程序設(shè)計(jì)填空題；
(7)算法和程序設(shè)計(jì)與分析題；
(8)其它題型。

五、特別說明

用C語言(或C++)描述算法和程序設(shè)計(jì)。 

第二部分  考察的知識(shí)及范圍

1.數(shù)據(jù)結(jié)構(gòu)和算法
數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的概念；數(shù)據(jù)類型與抽象數(shù)據(jù)類型；算法的概念,用C/C++描述算法和程序設(shè)計(jì)。
2.線性表
線性表的定義和基本操作；線性表的抽象數(shù)據(jù)類型；線性表的順序存儲(chǔ)結(jié)構(gòu)，
應(yīng)用舉例；線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(單鏈表,雙鏈表,循環(huán)鏈表),應(yīng)用舉例。
3.棧
棧的定義和基本操作；棧的抽象數(shù)據(jù)類型；順序棧，鏈?zhǔn)綏?；棧和遞歸算法, 算術(shù)表達(dá)式求值,其它應(yīng)用。
4．隊(duì)列
隊(duì)列的定義和基本操作；隊(duì)列的抽象數(shù)據(jù)類型；順序隊(duì)列，鏈?zhǔn)疥?duì)列；雙端隊(duì)列的定義和基本操作；應(yīng)用舉例。
5.數(shù)組和廣義表
(1)數(shù)組
數(shù)組的定義和基本操作；數(shù)組的順序存儲(chǔ)結(jié)構(gòu)，應(yīng)用舉例；特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)。
(2)廣義表
廣義表的定義和基本操作,廣義表的抽象數(shù)據(jù)類型,廣義表的存儲(chǔ)結(jié)構(gòu)。
 *廣義表運(yùn)算的實(shí)現(xiàn)舉例。
6.字符串
字符串的定義和基本操作,字符串的存儲(chǔ)結(jié)構(gòu),字符串操作的實(shí)現(xiàn)舉例,字符串和模式匹配。
7.樹和二叉樹
(1)樹的基本概念和基本操作,樹的抽象數(shù)據(jù)類型。
(2)二叉樹的概念和性質(zhì),特殊二叉樹；二叉樹的存儲(chǔ)結(jié)構(gòu)；
(3)二叉樹的生成與建立。  
(4)遍歷二叉樹：前序遍歷,中序遍歷,后序遍歷,層次遍歷。
(5)二叉樹其它操作實(shí)現(xiàn)舉例。
(6)線索二叉樹的概念和存儲(chǔ)結(jié)構(gòu),二叉樹的線索化,線索二叉樹的遍歷。
(7)樹的存儲(chǔ)結(jié)構(gòu),樹與二叉樹之間的轉(zhuǎn)換,森林與二叉樹之間的轉(zhuǎn)換,樹和森林的遍歷。
(8)樹的路徑長(zhǎng)度和帶權(quán)路徑長(zhǎng)度,哈夫曼樹(Huffman)的概念,哈夫曼算法, 哈夫曼編碼樹。
(9)二叉排序樹的的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作實(shí)現(xiàn)舉例。
8.圖
(1)圖的基本概念和基本操作，圖的抽象數(shù)據(jù)類型。
(2)圖的存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法(鄰接矩陣)；鄰接表，逆鄰接表，十字鏈表；鄰接多重表。
(3)圖的遍歷：深度優(yōu)先搜索法, 寬度優(yōu)先搜索法, 求圖的連通分量。
(4)生成樹、最小生成樹的概念；克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法。
 *(5)從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑,每對(duì)頂點(diǎn)之間的最短路徑。
*(6)拓?fù)渑判蚝完P(guān)鍵路徑
9.查找
(1)查找的概念,關(guān)鍵字比較次數(shù),平均查找長(zhǎng)度。
(2)順序表的查找:順序查找,折半查找,分塊查找。
(3)樹表的查找:二叉排序樹,平衡二叉樹。
(4)哈希(Hash)表的查找:哈希表的概念,哈希函數(shù)構(gòu)造方法,哈希表的建立和查找,沖突處理方法。
10.排序
(1)排序的概念；排序的穩(wěn)定性；比較關(guān)鍵字次數(shù),移動(dòng)記錄次數(shù)；順序表的排序,鏈接表(單鏈表)的排序。
(2)內(nèi)排序方法與算法
(a)交換排序:冒泡排序,快速排序。
(b)插入排序:直接插入排序,2路插入排序,折半插入排序,希爾排序。
(c)選擇排序:直接選擇排序,錦標(biāo)賽排序,堆排序。
(d)歸并排序。
(e)基數(shù)排序。
(3)各種排序算法的評(píng)價(jià)和應(yīng)用。
11.文件
(1)文件的基本概念, 文件的基本操作。
(2)文件的物理結(jié)構(gòu)：順序文件, 索引文件與索引順序文件, 直接存取文件，
鏈接文件和多重鏈表文件，倒排文件。
*12.外排序
外排序的基本過程, 初始?xì)w并段的生成,多路平衡歸并排序,最佳歸并樹。
13.算法分析
（1）算法分析基礎(chǔ)
(a) 熟悉漸近表示法，掌握漸近符號(hào) O 等的定義，能判斷一個(gè)較復(fù)雜的函數(shù)屬于哪個(gè)漸近增長(zhǎng)階；
(b) 熟悉一些算法復(fù)雜度分析的方法，比如說主定理法等，能對(duì)結(jié)構(gòu)復(fù)雜的算法進(jìn)行分析。
(2)算法設(shè)計(jì)基礎(chǔ)
(a) 熟悉算法設(shè)計(jì)的三大技巧：貪心算法、分而治之，動(dòng)態(tài)規(guī)劃。
(b) 能證明各種算法的正確性。
(c) 能用這三大技巧設(shè)計(jì)相應(yīng)的算法。
(3)NP 完備性理論及近似算法
(a) 了解并掌握 NP 完備性理論及其實(shí)際意義；
(b) 熟悉多項(xiàng)式規(guī)約。掌握證明一個(gè)問題 NP 完全性的基本方法和思路；
(c) 熟悉最小點(diǎn)覆蓋、最大獨(dú)立集等問題的 NP 完備性證明；
(d) 了解并掌握近似算法的設(shè)計(jì)步驟與技巧，掌握點(diǎn)覆蓋等問題的近似算法的設(shè)計(jì)。
說明:帶“*”號(hào)的章節(jié)為一般考查內(nèi)容,其余為重點(diǎn)考查內(nèi)容。
 
   

昆明理工大學(xué)

本文來源：http://www.qiang-kai.com/kunmingligongdaxue/cankaoshumu_379529.html