《數據結構及計算機組成原理》考試大綱和參考書目

　　第一部分 數據結構

　　參考教材：

　　《數據結構》（C語言版），嚴蔚敏等主編，清華大學出版社，1997年4月第二版

　　第一章 緒論

　　明確數據結構的定義、研究的內容，掌握算法及算法分析的概念，了解抽象數據類型的概念。

　　第二章 線性表

　　掌握線性表的概念，兩種存儲結構順序表和鏈表的表示和實現、掌握鏈表（單鏈表、單循環(huán)鏈表和雙向鏈表）上的查找、插入、刪除基本操作及能編寫鏈表上的綜合操作程序。

　　第三章 棧和隊列

　　掌握棧的概念，掌握順序棧、鏈棧的進棧、出棧操作程序。能利用棧寫出表達式求值過程，能用棧讀寫遞歸程序。

　　掌握隊列的概念，掌握循環(huán)隊列、循環(huán)鏈隊列的入隊、出隊操作程序。

　　第四章 串

　　掌握串的基本運算的含義，掌握求子串位置的定位函數，理解KMP模式匹配算法和時間復雜度。

　　第五章 多維數組和廣義表

　　掌握多維數組及特殊矩陣的地址公式，廣義表的運算和存儲。了解廣義表的遞歸算法。

　　第六章 樹和二叉樹。

　　掌握樹、二叉樹的定義、術語，二叉樹的性質，掌握二叉樹的遞歸和非遞歸遍歷算法，掌握中序線索二叉樹的概念和遍歷算法，掌握Haffman樹及其應用，了解樹與二叉樹的關系，了解回溯法與樹的遍歷。

　　第七章 圖

　　掌握圖的定義、術語，掌握圖的存儲，圖的遍歷算法，掌握比較小生成樹、拓撲排序、關鍵路徑、比較短路徑概念，了解其算法。

　　第九章 查找

　　掌握有序表的查找算法和查找的時間復雜度，掌握二叉排序樹的查找、插入和刪除算法，掌握平衡二叉樹和B-樹的插入、刪除概念。

　　掌握哈希表構造、解決沖突的方法及哈希表的查找。

　　第十章 內部排序

　　掌握直接插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序和希爾排序算法和時間復雜度，了解基數排序的概念。

　　專業(yè)課《數據結構》考試大綱和參考書目

　　參考教材:《數據結構·C語言版》 , 嚴蔚敏主編 , 清華大學出版社

　　參考用書:《數據結構習題詳解》, 李春葆編著, 清華大學出版社

　　課程內容（無標記章節(jié)一般了解、不考，打*號標記章節(jié)要求掌握，打**號標記章節(jié)要求重點掌握）

　　緒論

　　數據結構定義

　　基本概念和術語

　　*算法描述和算法分析

　　抽象數據類型的表示和實現

　　線性表

　　線性表的基本概念

　　線性表順序表示和實現

　　線性表的鏈式表示和實現：

　　**線性鏈表

　　**循環(huán)鏈表

　　*雙向鏈表

　　順序存儲結構與鏈式存儲結構的比較

　　**線性表的應用舉例

　　棧和隊列

　　*抽象數據類型棧的定義

　　*棧的表示和實現

　　棧的應用舉例：

　　迷宮求解

　　**表達式求值

　　**棧與遞歸的實現

　　*抽象數據類型隊列的定義

　　*鏈隊列—隊列的鏈式表示和實現

　　**循環(huán)隊列—隊列的順序表示和實現

　　串

　　串類型的定義

　　串的表示和實現

　　**串的模式匹配算法

　　串的應用舉例

　　數組和廣義表

　　數組的定義

　　*數組的順序表示和實現

　　*矩陣的壓縮存儲：

　　特殊矩陣

　　稀疏矩陣

　　*廣義表的概念

　　*廣義表的存儲

　　廣義表的應用舉例

　　樹和二叉樹

　　樹的定義和基本術語

　　*二叉樹：

　　二叉樹的定義

　　二叉樹的性質

　　二叉樹的存儲結構

　　**二叉樹的遍歷

　　**線索二叉樹

　　樹和森林：

　　樹的存儲結構

　　靜態(tài)鏈表

　　樹、森林和二叉樹的轉換

　　樹的遍歷

　　*樹的應用舉例：

　　哈夫曼樹

　　哈夫曼編碼

　　回溯法與樹的遍歷

　　圖

　　*圖的定義和基本術語

　　圖的存儲結構：

　　**鄰接矩陣

　　**鄰接表

　　十字鏈表

　　鄰接多重表

　　**圖的遍歷：

　　深度優(yōu)先搜索遍歷

　　廣度優(yōu)先搜索遍歷

　　*比較小生成樹：

　　生成樹和比較小生成樹

　　普里姆算法

　　克魯斯卡爾算法

　　有向無環(huán)圖及應用：

　　*拓撲排序

　　關鍵路徑

　　比較短路徑

　　查找

　　查找基本概念

　　順序表的查找：

　　順序查找

　　**有序表的查找

　　分塊查找

　　8.3樹表的查找

　　*8.3.1二叉搜索樹

　　*8.3.2平衡二叉樹

　　8.3.3 B_樹

　　8.3.4 B+樹

　　*8.4哈希表

　　8.4.1哈希表的基本概念

　　8.4.2構造哈希函數的方法

　　8.4.3解決哈希沖突的方法

　　8.4.4哈希表的查找

　　*第九章 排序

　　9.1排序的基本概念

　　9.2插入排序

　　9.2.1直接插入排序

　　9.2.2希爾排序

　　9.3交換排序

　　9.3.1冒泡排序

　　9.3.2快速排序

　　9.4選擇排序

　　9.4.1直接選擇排序

　　9.4.2堆排序

　　9.5歸并排序

　　9.6基數排序

　　9.7各種內部排序方法比較

　　9.8外排序

　　**二叉排序樹

　　*平衡二叉樹

　　*B_樹

　　B+樹

　　哈希表：

　　*哈希表的基本概念

　　構造哈希函數的方法

　　*解決哈希沖突的方法

　　*哈希表的查找

　　內部排序

　　排序的基本概念

　　**插入排序：

　　直接插入排序

　　希爾排序

　　**冒泡排序

　　**快速排序

　　**選擇排序：

　　直接選擇排序

　　堆排序

　　**歸并排序

　　基數排序

　　*各種內部排序方法比較

　　第一部分 計算機組成原理

　　一、考試范圍

　　計算機系統(tǒng)概論，運算方法與運算器，內部存儲器，指令系統(tǒng)，中央處理機，總線系統(tǒng)，外圍設備，輸入輸出系統(tǒng)，操作系統(tǒng)支持。

　　在考查基本概念、基本理論的基礎上，注重考查學生運用基本知識分析和解決實際問題的能力。要求學生對計算機組成原理有比較深入的認識，主要包括下面3個方面：

　　1、深刻理解計算機系統(tǒng)各功能部件的功能、組成和工作原理，正確理解各功能部件之間相互關系以及它們在計算機系統(tǒng)中所起的作用。

　　2、了解和掌握計算機系統(tǒng)某些部件的設計與分析技術，包括數據與指令的編碼、存儲、輸人輸出等。

　　3、理解和掌握計算機系統(tǒng)中的基本概念和方法，并能將這些概念和方法運用在后繼課的學習中。

　　二、考試形式與試卷結構

　　1.考查內容及其考查比例：基本概念占30%分、理解占30%分、綜合能力占40%分。

　　2.試卷結構與考試題型：填空題、選擇、問答題、綜合計算題等。

　　三、參考書目

　　《計算機組成原理》（第四版），白中英主編，科學出版社，2007年12月。

　　四、考查要點

　　1、計算機系統(tǒng)層次結構的實際含義，各部件的基本功能。計算機系統(tǒng)的基本概念： 寄存器、算術邏輯單元、存儲器、字、字節(jié)、地址、指令流、 地址流、CPU、總線、主存、輔存、DMA等。

　　2、數的基本知識，計算機中數的表示方法，機器數的定義及與真值的互換，信息校驗的實際意義和方法。定點數運算方法；浮點數四則運算方法；算術邏輯單元的組成及工作原理。運算器的功能，功能部件和結構。

　　3、存儲器的基本知識，現代主存儲器的結構和工作原理、設計原理和方法；高速緩沖存儲器的組織、工作原理，地址影象方法及替換算法；軟硬盤存儲器的結構及工作原理，磁記錄原理和磁記錄方式；存儲器的校驗和CRC碼校驗。虛擬存儲器概念及有關內容。

　　4、指令系統(tǒng)的意義和重要性；指令格式，指令和操作數的尋址方式和尋址過程；完備性指令系統(tǒng)的設計。

　　5、中央處理機的功能與組織，指令處理的相關知識和控制原理，時序發(fā)生器設置的意義及時序產生器的組織和工作原理。微程序控制器和硬布線控制器的設計思想、原理、組織特征、工作原理及有關知識；流水CPU的有關概念。

　　6、單機系統(tǒng)總線結構及其特征，總線的仲裁與通信及其有關知識。

　　7、外圍設備的類型、功能和特點；多種信息存儲或顯示方式的工作原理。

　　8、幾種輸入輸出控制方式的控制原理和數據傳送的過程。中斷系統(tǒng)設置的意義及中斷過程實現的技術和相關知識。

　　9、操作系統(tǒng)對計算機各功能部件的工作機理。