博士研究生數(shù)據(jù)結(jié)構(gòu)及算法分析科目

1、3371 博士研究生數(shù)據(jù)結(jié)構(gòu)及算法分析科目入學考試大綱第一部分 考試說明一、考試性質(zhì) 數(shù)據(jù)結(jié)構(gòu)和算法分析是計算機專業(yè)的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)及算法分析是華中科技大學計算機軟件與理論專業(yè)博士研究生入學考試的一個綜合考試科目。 它的評價標準是，高等學校本學科優(yōu)秀畢業(yè)生能達到的及格或及格以上水平，以保證被錄取者具有基本的計算機專業(yè)理論基礎(chǔ)，以利于計算機軟件與理論專業(yè)各導師擇優(yōu)選拔。 考試對象為參加博士研究生入學考試的應(yīng)屆或非應(yīng)屆碩士畢業(yè)生和具有同等學力的在職人員。二、考試的學科范圍 1.數(shù)據(jù)結(jié)構(gòu) 各種基本類型的數(shù)據(jù)結(jié)構(gòu)的概念、特征、操作、存儲表示和基本應(yīng)用；各類查找表的查找方法，基本的內(nèi)排序和外排序方

2、法；文件在外存儲器中的表示方法；相關(guān)算法的C/C+描述與分析。 2.算法分析 算法的基本概念,分治策略，貪心策略，動態(tài)規(guī)劃，基本檢索與周游方法。三、評價目標 1.數(shù)據(jù)結(jié)構(gòu) 在考察數(shù)據(jù)結(jié)構(gòu)的基本概念、基本方法和相關(guān)算法的基礎(chǔ)上，注重考察綜合應(yīng)用的能力，即分析和解決實際問題的能力。 2.算法分析 掌握一定的算法分析能力, 掌握算法設(shè)計的基本觀點和基本方法, 能正確地選用常用的非數(shù)值計算算法, 能站在算法設(shè)計策略的高度上設(shè)計算法。 具體要求見第二部分“考查要點”。四、考試形式與試卷結(jié)構(gòu) 1.答卷方式：閉卷，筆試。 2.答題時間：180分鐘。 3.考查內(nèi)容及其考查比例 基本概念、基本方法約占40%50

3、%；綜合應(yīng)用、算法設(shè)計(程序設(shè)計)與分析約占60%50%。 4.試卷結(jié)構(gòu)與考試題型 (1)單項選擇題,多項選擇題: 約20% (2)填空題，簡答題，應(yīng)用題: 約35% (3)算法設(shè)計題, 算法分析題: 約35% (4)其它題型: 約10%五、參考書目 1.嚴蔚敏等，數(shù)據(jù)結(jié)構(gòu)(C語言版)，清華大學出版社 2.余祥宣 崔國華 鄒海明，計算機算法基礎(chǔ)(前五章)，華中理工大學出版社,2000 3.Horowitz,S Sahni,Fundamentals of Computer Algorithms.New York: Computer Science Press,1978第二部分 考查要點一、數(shù)據(jù)結(jié)

4、構(gòu)(約60%) 1.數(shù)據(jù)結(jié)構(gòu)和算法C/C+描述。 數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)的概念；數(shù)據(jù)類型與抽象數(shù)據(jù)類型；數(shù)據(jù)結(jié)構(gòu)和算法C+描述。 2.線性表：線性表的定義和基本操作；線性表的抽象數(shù)據(jù)類型；線性表的順序存儲結(jié)構(gòu)，應(yīng)用舉例；線性表的鏈式存儲結(jié)構(gòu)(單鏈表,雙鏈表,循環(huán)鏈表),應(yīng)用舉例。 3.棧：棧的定義和基本操作；棧的抽象數(shù)據(jù)類型；順序棧，鏈式棧；棧和遞歸,算術(shù)表達式求值,其它應(yīng)用。 4.隊列：隊列的定義和基本操作；隊列的抽象數(shù)據(jù)類型；順序隊列，鏈式隊列；雙端隊列 ；應(yīng)用舉例。 5.數(shù)組和廣義表 (1)數(shù)組：數(shù)組的定義和基本操作；數(shù)組的順序存儲結(jié)構(gòu)，數(shù)組應(yīng)用舉例；特殊矩陣和稀疏矩陣矩陣的壓縮存儲。 (2

5、)廣義表：廣義表的定義和基本操作，廣義表的抽象數(shù)據(jù)類型，廣義表的存儲結(jié)構(gòu)，廣義表運算的實現(xiàn)舉例。 6.字符串：字符串的定義和基本操作，字符串的存儲結(jié)構(gòu)，字符串操作的實現(xiàn)舉例，字符串和模式匹配。 7.樹和二叉樹 (1)樹的基本概念和基本操作,樹的抽象數(shù)據(jù)類型。 (2)二叉樹的基本概念和性質(zhì)，幾種特殊二叉樹,二叉樹的存儲結(jié)構(gòu), 遍歷二叉樹, 線索二叉樹,樹和森林。 (3)遍歷二叉樹：前序遍歷, 中序遍歷, 后序遍歷, 層次遍歷。 (4)二叉樹其它操作實現(xiàn)舉例。 (5)線索二叉樹的概念和存儲結(jié)構(gòu), 二叉樹的線索化, 線索二叉樹的遍歷。 (6)樹的存儲結(jié)構(gòu),樹與二叉樹之間的轉(zhuǎn)換, 森林與二叉樹之間的轉(zhuǎn)

6、換，樹和森林的遍歷。 (7)帶權(quán)路徑長度, 哈夫曼樹(Huffman)和哈夫曼算法, 哈夫曼編碼樹。 (8)二叉排序樹的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作實現(xiàn)舉例。 8.圖 (1)圖的基本概念和基本操作，圖的抽象數(shù)據(jù)類型。 (2)圖的存儲結(jié)構(gòu)：數(shù)組表示法(鄰接矩陣)；鄰接表，逆鄰接表；鄰接多重表。 (3)圖的遍歷：深度優(yōu)先搜索法, 寬度優(yōu)先搜索法, 求圖的連通分量。 (4)生成樹和最小生成樹的概念；克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法。 (5)最短路徑，拓撲排序，關(guān)鍵路徑。 9.查找 (1)查找的概念。 (2)順序表的查找：順序查找, 折半查找, 分塊查找

7、。 (3)樹表的查找: 二叉排序樹, 平衡二叉樹。 (4)哈希(Hash)表的查找: 哈希表的概念, 哈希函數(shù)的構(gòu)造方法, 哈希表的建立和查找, 沖突的處理方法。 10.排序 (1)排序的概念 (2)交換排序：冒泡排序, 快速排序。 (3)插入排序：直接插入排序, 2路插入排序，折半插入排序, 希爾排序。 (4)選擇排序：直接選擇排序, 錦標賽排序,堆排序。 (5)歸并排序，(6)基數(shù)排序 11.文件:文件的基本概念和基本操作；文件的物理結(jié)構(gòu)：順序文件,索引文件與索引順序文件, 直接存取文件，鏈接文件和多重鏈表文件，倒排文件。 12.外排序：外排序的基本過程,初始歸并段的生成,多路平衡歸并排序, 最佳歸并樹。二、算法分析(約40%) 1.基礎(chǔ)知識 算法的定義,它所涉及的內(nèi)容及在計算機科學中的地位和作用；算法分析的基本概念，基本步驟及其數(shù)學工具；基本的數(shù)據(jù)結(jié)構(gòu)，用SPARKS語言寫算法；集合的基本運算-查找和合并；遞歸程序和消去遞歸的十三條規(guī)則。 2.分治法 分治法的一般方法, 二分檢索, 找最大和最小元素, 歸并分類, 快速分類,選擇問題, 斯特拉森矩陣乘法。3.貪心方法 一般方法及背包問題, 帶有限期的作業(yè)排序, 最優(yōu)歸并模式, 最小