研线网-考研网-考研科目/时间/专业-研线网

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