|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
華中科技大學博士研究生入學考試
《數據結構及算法分析》考試大綱
第一部分 考試說明
一、考試性質
《數據結構》和《算法分析》是計算機專業的專業基礎課?！稊祿Y構及算
法分析》是華中科技大學計算機軟件與理論專業博士研究生入學考試的一個綜合
考試科目。
它的評價標準是，高等學校本學科優秀畢業生能達到的及格或及格以上水
平，以保證被錄取者具有基本的計算機專業理論基礎，以利于計算機軟件與理論
專業各導師擇優選拔。
考試對象為參加博士研究生入學考試的應屆或非應屆碩士畢業生和具有同
等學力的在職人員。
二、考試的學科范圍
1.數據結構
各種基本類型的數據結構的概念、特征、操作、存儲表示和基本應用；各類
查找表的查找方法，基本的內排序和外排序方法；文件在外存儲器中的表示方法；
相關算法的 C/C++描述與分析。
2.算法分析
算法的基本概念,分治策略，貪心策略，動態規劃，基本檢索與周游方法。
三、評價目標
1.數據結構
在考察數據結構的基本概念、基本方法和相關算法的基礎上，注重考察綜合
應用的能力，即分析和解決實際問題的能力。
2.算法分析
掌握一定的算法分析能力, 掌握算法設計的基本觀點和基本方法, 能正確
地選用常用的非數值計算算法, 能站在算法設計策略的高度上設計算法。
具體要求見第二部分“考查要點”。
四、考試形式與試卷結構
1.答卷方式：閉卷，筆試。
2.答題時間：180 分鐘。
3.考查內容及其考查比例
基本概念、基本方法約占 40%～50%；綜合應用、算法設計(程序設計)與分
析約占 60%～50%。
4.試卷結構與考試題型
(1)單項選擇題,多項選擇題: 約 20%
(2)填空題，簡答題，應用題: 約 35%
(3)算法設計題, 算法分析題: 約 35%
(4)其它題型: 約 10%
第二部分 考查要點
一、數據結構(約 60%)
1.數據結構和算法 C/C++描述。
數據結構、存儲結構的概念；數據類型與抽象數據類型；數據結構和算法
C++描述。
2.線性表：線性表的定義和基本操作；線性表的抽象數據類型；線性表的順
序存儲結構，應用舉例；線性表的鏈式存儲結構(單鏈表,雙鏈表,循環鏈表),應
用舉例。
3.棧：棧的定義和基本操作；棧的抽象數據類型；順序棧，鏈式棧；棧和遞
歸,算術表達式求值,其它應用。
4.隊列：隊列的定義和基本操作；隊列的抽象數據類型；順序隊列，鏈式隊
列；雙端隊列 ；應用舉例。
5.數組和廣義表
(1)數組：數組的定義和基本操作；數組的順序存儲結構，數組應用舉例；
特殊矩陣和稀疏矩陣矩陣的壓縮存儲。
(2)廣義表：廣義表的定義和基本操作，廣義表的抽象數據類型，廣義表的
存儲結構，廣義表運算的實現舉例。
6.字符串：字符串的定義和基本操作，字符串的存儲結構，字符串操作的實
現舉例，字符串和模式匹配。
7.樹和二叉樹
(1)樹的基本概念和基本操作,樹的抽象數據類型。
(2)二叉樹的基本概念和性質，幾種特殊二叉樹,二叉樹的存儲結構, 遍歷二
叉樹, 線索二叉樹,樹和森林。
(3)遍歷二叉樹：前序遍歷, 中序遍歷, 后序遍歷, 層次遍歷。
(4)二叉樹其它操作實現舉例。
(5)線索二叉樹的概念和存儲結構, 二叉樹的線索化, 線索二叉樹的遍歷。
(6)樹的存儲結構,樹與二叉樹之間的轉換, 森林與二叉樹之間的轉換，樹和
森林的遍歷。
(7)帶權路徑長度, 哈夫曼樹(Huffman)和哈夫曼算法, 哈夫曼編碼樹。
(8)二叉排序樹的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作
實現舉例。
8.圖
(1)圖的基本概念和基本操作，圖的抽象數據類型。
(2)圖的存儲結構：數組表示法(鄰接矩陣)；鄰接表，逆鄰接表；鄰接多重
表。
(3)圖的遍歷：深度優先搜索法, 寬度優先搜索法, 求圖的連通分量。
(4)生成樹和最小生成樹的概念；克魯斯卡爾(Kruskal)算法,普里姆(Prim)
算法。
(5)最短路徑，拓撲排序，關鍵路徑。
9.查找
(1)查找的概念。
(2)順序表的查找：順序查找, 折半查找, 分塊查找。
(3)樹表的查找: 二叉排序樹, 平衡二叉樹。
(4)哈希(Hash)表的查找: 哈希表的概念, 哈希函數的構造方法, 哈希表的
建立和查找, 沖突的處理方法。
10.排序
(1)排序的概念
(2)交換排序：冒泡排序, 快速排序。
(3)插入排序：直接插入排序, 2 路插入排序，折半插入排序, 希爾排序。
(4)選擇排序：直接選擇排序, 錦標賽排序,堆排序。
(5)歸并排序，(6)基數排序
11.文件:文件的基本概念和基本操作；文件的物理結構：順序文件,索引文
件與索引順序文件, 直接存取文件，鏈接文件和多重鏈表文件，倒排文件。
12.外排序：外排序的基本過程,初始歸并段的生成,多路平衡歸并排序, 最
佳歸并樹。
二、算法分析(約 40%)
1.基礎知識
算法的定義,它所涉及的內容及在計算機科學中的地位和作用；算法分析的
基本概念，基本步驟及其數學工具；基本的數據結構，用 SPARKS 語言寫算法；
集合的基本運算----查找和合并；遞歸程序和消去遞歸的十三條規則。
2.分治法
分治法的一般方法, 二分檢索, 找最大和最小元素, 歸并分類, 快速分類,
選擇問題, 斯特拉森矩陣乘法。
3.貪心方法
一般方法及背包問題, 帶有限期的作業排序, 最優歸并模式, 最小生成樹,
單源點最短路徑。
4.動態規劃
一般方法, 多段圖, 每對結點之間的最短距離, 最優二分檢索樹, 0/1 背包
問題, 可靠性設計, 貨郎擔問題, 流水線調度問題。
5.周游與檢索
基本概念與一般方法, 代碼優化, 雙連通分圖和深度優先檢索。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
