不知不覺21年考研黨全都投入到火熱的備考當(dāng)中了，各高校也陸續(xù)的發(fā)布了考試大綱，以便考生能夠根據(jù)考試目錄進(jìn)行有效的備考，小編為大家整理了“2021考研大綱：昆明理工大學(xué)877數(shù)據(jù)結(jié)構(gòu)與算法分析2021年碩士研究生入學(xué)考試大綱及部分參考書目匯總”的相關(guān)內(nèi)容，希望對大家有所幫助！

昆明理工大學(xué)碩士研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)與算法分析》考試大綱

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

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

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

二、答題方式

答題方式為閉卷、筆試。

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

基本概念、基本知識、基本方法約占40%～50%；

綜合應(yīng)用、算法和程序設(shè)計(jì)與算法分析約占60%～50%。

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

試卷共150分,基本的考試題型為：

(1)單項(xiàng)選擇題和多項(xiàng)選擇題；

(2)填空題(基本概念、基本知識、基本方法)；

(3)畫圖題；

(4)簡答題；

(5)應(yīng)用題(求解問題)；

(6)算法和程序設(shè)計(jì)填空題；

(7)算法和程序設(shè)計(jì)與分析題；

(8)其它題型。

五、特別說明

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

第二部分考察的知識及范圍

1.數(shù)據(jù)結(jié)構(gòu)和算法

數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)的概念；數(shù)據(jù)類型與抽象數(shù)據(jù)類型；算法的概念,用C/C++描述算法和程序設(shè)計(jì)。

2.線性表

線性表的定義和基本操作；線性表的抽象數(shù)據(jù)類型；線性表的順序存儲結(jié)構(gòu)，

應(yīng)用舉例；線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)(單鏈表,雙鏈表,循環(huán)鏈表),應(yīng)用舉例。

3.棧

棧的定義和基本操作；棧的抽象數(shù)據(jù)類型；順序棧，鏈?zhǔn)綏＃粭：瓦f歸算法,算術(shù)表達(dá)式求值,其它應(yīng)用。

4．隊(duì)列

隊(duì)列的定義和基本操作；隊(duì)列的抽象數(shù)據(jù)類型；順序隊(duì)列，鏈?zhǔn)疥?duì)列；雙端隊(duì)列的定義和基本操作；應(yīng)用舉例。

5.數(shù)組和廣義表

(1)數(shù)組

數(shù)組的定義和基本操作；數(shù)組的順序存儲結(jié)構(gòu)，應(yīng)用舉例；特殊矩陣和稀疏矩陣的壓縮存儲。

(2)廣義表

廣義表的定義和基本操作,廣義表的抽象數(shù)據(jù)類型,廣義表的存儲結(jié)構(gòu)。

*廣義表運(yùn)算的實(shí)現(xiàn)舉例。

6.字符串

字符串的定義和基本操作,字符串的存儲結(jié)構(gòu),字符串操作的實(shí)現(xiàn)舉例,字符串和模式匹配。

7.樹和二叉樹

(1)樹的基本概念和基本操作,樹的抽象數(shù)據(jù)類型。

(2)二叉樹的概念和性質(zhì),特殊二叉樹；二叉樹的存儲結(jié)構(gòu)；

(3)二叉樹的生成與建立。

(4)遍歷二叉樹：前序遍歷,中序遍歷,后序遍歷,層次遍歷。

(5)二叉樹其它操作實(shí)現(xiàn)舉例。

(6)線索二叉樹的概念和存儲結(jié)構(gòu),二叉樹的線索化,線索二叉樹的遍歷。

(7)樹的存儲結(jié)構(gòu),樹與二叉樹之間的轉(zhuǎn)換,森林與二叉樹之間的轉(zhuǎn)換,樹和森林的遍歷。

(8)樹的路徑長度和帶權(quán)路徑長度,哈夫曼樹(Huffman)的概念,哈夫曼算法,哈夫曼編碼樹。

(9)二叉排序樹的的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作實(shí)現(xiàn)舉例。

8.圖

(1)圖的基本概念和基本操作，圖的抽象數(shù)據(jù)類型。

(2)圖的存儲結(jié)構(gòu)：數(shù)組表示法(鄰接矩陣)；鄰接表，逆鄰接表，十字鏈表；鄰接多重表。

(3)圖的遍歷：深度優(yōu)先搜索法,寬度優(yōu)先搜索法,求圖的連通分量。

(4)生成樹、最小生成樹的概念；克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法。

*(5)從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑,每對頂點(diǎn)之間的最短路徑。

*(6)拓?fù)渑判蚝完P(guān)鍵路徑

9.查找

(1)查找的概念,關(guān)鍵字比較次數(shù),平均查找長度。

(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)各種排序算法的評價(jià)和應(yīng)用。

11.文件

(1)文件的基本概念,文件的基本操作。

(2)文件的物理結(jié)構(gòu)：順序文件,索引文件與索引順序文件,直接存取文件，

鏈接文件和多重鏈表文件，倒排文件。

*12.外排序

外排序的基本過程,初始?xì)w并段的生成,多路平衡歸并排序,最佳歸并樹。

13.算法分析

（1）算法分析基礎(chǔ)

(a)熟悉漸近表示法，掌握漸近符號O等的定義，能判斷一個(gè)較復(fù)雜的函數(shù)屬于哪個(gè)漸近增長階；

(b)熟悉一些算法復(fù)雜度分析的方法，比如說主定理法等，能對結(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ì)。

說明:帶“*”號的章節(jié)為一般考查內(nèi)容,其余為重點(diǎn)考查內(nèi)容。

原文標(biāo)題：昆明理工大學(xué)2021年碩士研究生入學(xué)考試大綱

原文鏈接：http://yjs.kmust.edu.cn/info/1016/2968.htm

以上就是“2021考研大綱：昆明理工大學(xué)877數(shù)據(jù)結(jié)構(gòu)與算法分析2021年碩士研究生入學(xué)考試大綱及部分參考書目匯總”的全部內(nèi)容，更多考研大綱信息，請多多關(guān)注！