考試大綱不僅能給你一個復習的方向，還能幫助你梳理整個知識脈絡(luò)，方便記憶。今天，小編為大家整理了“2021考研大綱：昆明理工大學877數(shù)據(jù)結(jié)構(gòu)與算法分析2021年碩士研究生入學考試大綱及部分參考書目匯總”的相關(guān)內(nèi)容，希望對大家有所幫助！
昆明理工大學碩士研究生入學考試《數(shù)據(jù)結(jié)構(gòu)與算法分析》考試大綱
第一部分考試形式與試卷結(jié)構(gòu)
一、試卷滿分及考試時間
試卷滿分為150分，考試時間為180分鐘。
二、答題方式
答題方式為閉卷、筆試。
三、試卷內(nèi)容結(jié)構(gòu)
基本概念、基本知識、基本方法約占40%～50%；
綜合應用、算法和程序設(shè)計與算法分析約占60%～50%。
四、試卷題型結(jié)構(gòu)
試卷共150分,基本的考試題型為：
(1)單項選擇題和多項選擇題；
(2)填空題(基本概念、基本知識、基本方法)；
(3)畫圖題；
(4)簡答題；
(5)應用題(求解問題)；
(6)算法和程序設(shè)計填空題；
(7)算法和程序設(shè)計與分析題；
(8)其它題型。
五、特別說明
用C語言(或C++)描述算法和程序設(shè)計。
第二部分考察的知識及范圍
1.數(shù)據(jù)結(jié)構(gòu)和算法
數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)的概念；數(shù)據(jù)類型與抽象數(shù)據(jù)類型；算法的概念,用C/C++描述算法和程序設(shè)計。
2.線性表
線性表的定義和基本操作；線性表的抽象數(shù)據(jù)類型；線性表的順序存儲結(jié)構(gòu)，
應用舉例；線性表的鏈式存儲結(jié)構(gòu)(單鏈表,雙鏈表,循環(huán)鏈表),應用舉例。
3.棧
棧的定義和基本操作；棧的抽象數(shù)據(jù)類型；順序棧，鏈式棧；棧和遞歸算法,算術(shù)表達式求值,其它應用。
4．隊列
隊列的定義和基本操作；隊列的抽象數(shù)據(jù)類型；順序隊列，鏈式隊列；雙端隊列的定義和基本操作；應用舉例。
5.數(shù)組和廣義表
(1)數(shù)組
數(shù)組的定義和基本操作；數(shù)組的順序存儲結(jié)構(gòu)，應用舉例；特殊矩陣和稀疏矩陣的壓縮存儲。
(2)廣義表
廣義表的定義和基本操作,廣義表的抽象數(shù)據(jù)類型,廣義表的存儲結(jié)構(gòu)。
*廣義表運算的實現(xiàn)舉例。
6.字符串
字符串的定義和基本操作,字符串的存儲結(jié)構(gòu),字符串操作的實現(xiàn)舉例,字符串和模式匹配。
7.樹和二叉樹
(1)樹的基本概念和基本操作,樹的抽象數(shù)據(jù)類型。
(2)二叉樹的概念和性質(zhì),特殊二叉樹；二叉樹的存儲結(jié)構(gòu)；
(3)二叉樹的生成與建立。
(4)遍歷二叉樹：前序遍歷,中序遍歷,后序遍歷,層次遍歷。
(5)二叉樹其它操作實現(xiàn)舉例。
(6)線索二叉樹的概念和存儲結(jié)構(gòu),二叉樹的線索化,線索二叉樹的遍歷。
(7)樹的存儲結(jié)構(gòu),樹與二叉樹之間的轉(zhuǎn)換,森林與二叉樹之間的轉(zhuǎn)換,樹和森林的遍歷。
(8)樹的路徑長度和帶權(quán)路徑長度,哈夫曼樹(Huffman)的概念,哈夫曼算法,哈夫曼編碼樹。
(9)二叉排序樹的的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作實現(xiàn)舉例。
8.圖
(1)圖的基本概念和基本操作，圖的抽象數(shù)據(jù)類型。
(2)圖的存儲結(jié)構(gòu)：數(shù)組表示法(鄰接矩陣)；鄰接表，逆鄰接表，十字鏈表；鄰接多重表。
(3)圖的遍歷：深度優(yōu)先搜索法,寬度優(yōu)先搜索法,求圖的連通分量。
(4)生成樹、最小生成樹的概念；克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法。
*(5)從一個頂點到其余各頂點的最短路徑,每對頂點之間的最短路徑。
*(6)拓撲排序和關(guān)鍵路徑
9.查找
(1)查找的概念,關(guān)鍵字比較次數(shù),平均查找長度。
(2)順序表的查找:順序查找,折半查找,分塊查找。
(3)樹表的查找:二叉排序樹,平衡二叉樹。
(4)哈希(Hash)表的查找:哈希表的概念,哈希函數(shù)構(gòu)造方法,哈希表的建立和查找,沖突處理方法。
10.排序
(1)排序的概念；排序的穩(wěn)定性；比較關(guān)鍵字次數(shù),移動記錄次數(shù)；順序表的排序,鏈接表(單鏈表)的排序。
(2)內(nèi)排序方法與算法
(a)交換排序:冒泡排序,快速排序。
(b)插入排序:直接插入排序,2路插入排序,折半插入排序,希爾排序。
(c)選擇排序:直接選擇排序,錦標賽排序,堆排序。
(d)歸并排序。
(e)基數(shù)排序。
(3)各種排序算法的評價和應用。
11.文件
(1)文件的基本概念,文件的基本操作。
(2)文件的物理結(jié)構(gòu)：順序文件,索引文件與索引順序文件,直接存取文件，
鏈接文件和多重鏈表文件，倒排文件。
*12.外排序
外排序的基本過程,初始歸并段的生成,多路平衡歸并排序,最佳歸并樹。
13.算法分析
（1）算法分析基礎(chǔ)
(a)熟悉漸近表示法，掌握漸近符號O等的定義，能判斷一個較復雜的函數(shù)屬于哪個漸近增長階；
(b)熟悉一些算法復雜度分析的方法，比如說主定理法等，能對結(jié)構(gòu)復雜的算法進行分析。
(2)算法設(shè)計基礎(chǔ)
(a)熟悉算法設(shè)計的三大技巧：貪心算法、分而治之，動態(tài)規(guī)劃。
(b)能證明各種算法的正確性。
(c)能用這三大技巧設(shè)計相應的算法。
(3)NP完備性理論及近似算法
(a)了解并掌握NP完備性理論及其實際意義；
(b)熟悉多項式規(guī)約。掌握證明一個問題NP完全性的基本方法和思路；
(c)熟悉最小點覆蓋、最大獨立集等問題的NP完備性證明；
(d)了解并掌握近似算法的設(shè)計步驟與技巧，掌握點覆蓋等問題的近似算法的設(shè)計。
說明:帶“*”號的章節(jié)為一般考查內(nèi)容,其余為重點考查內(nèi)容。
原文標題：昆明理工大學2021年碩士研究生入學考試大綱
原文鏈接：http://yjs.kmust.edu.cn/info/1016/2968.htm
以上就是“2021考研大綱：昆明理工大學877數(shù)據(jù)結(jié)構(gòu)與算法分析2021年碩士研究生入學考試大綱及部分參考書目匯總”的全部內(nèi)容，更多考研大綱信息，請多多關(guān)注！