|
|
|
|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
《數據結構及計算機組成原理》考試大綱和參考書目
第一部分 數據結構
參考教材：
《數據結構》（C 語言版），嚴蔚敏等主編，清華大學出版社，2012 年
第一章 緒論
明確數據結構的定義、研究的內容，掌握算法及算法分析的概念，了解抽象數據類型的
概念。
第二章 線性表
掌握線性表的概念，兩種存儲結構順序表和鏈表的表示和實現、掌握鏈表（單鏈表、
單循環鏈表和雙向鏈表）上的查找、插入、刪除基本操作及能編寫鏈表上的綜合操作程序。
第三章 棧和隊列
掌握棧的概念，掌握順序棧、鏈棧的進棧、出棧操作程序。能利用棧寫出表達式求值過
程，能用棧讀寫遞歸程序。
掌握隊列的概念，掌握循環隊列、循環鏈隊列的入隊、出隊操作程序。
第四章 串
掌握串的基本運算的含義，掌握求子串位置的定位函數，理解 KMP 模式匹配算法和時
間復雜度。
第五章 多維數組和廣義表
掌握多維數組及特殊矩陣的地址公式，廣義表的運算和存儲。了解廣義表的遞歸算法。
第六章 樹和二叉樹。
掌握樹、二叉樹的定義、術語，二叉樹的性質，掌握二叉樹的遞歸和非遞歸遍歷算法，
掌握中序線索二叉樹的概念和遍歷算法，掌握 Haffman 樹及其應用，了解樹與二叉樹的關系，
了解回溯法與樹的遍歷。
第七章 圖
掌握圖的定義、術語，掌握圖的存儲，圖的遍歷算法，掌握最小生成樹、拓撲排序、關
鍵路徑、最短路徑概念，了解其算法。
第九章 查找
掌握有序表的查找算法和查找的時間復雜度，掌握二叉排序樹的查找、插入和刪除算法，
掌握平衡二叉樹和 B-樹的插入、刪除概念。
掌握哈希表構造、解決沖突的方法及哈希表的查找。
第十章 內部排序
掌握直接插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序和希爾排
序算法和時間復雜度，了解基數排序的概念。
專業課《數據結構》考試大綱和參考書目
參考教材:《數據結構·C 語言版》 , 嚴蔚敏主編 , 清華大學出版社
課程內容（無標記章節一般了解、不考，打*號標記章節要求掌握，打**號標記章節要求重
點掌握）
緒論
數據結構定義
基本概念和術語
*算法描述和算法分析
抽象數據類型的表示和實現
線性表
線性表的基本概念
線性表順序表示和實現
線性表的鏈式表示和實現：
**線性鏈表
**循環鏈表
*雙向鏈表
順序存儲結構與鏈式存儲結構的比較
**線性表的應用舉例
棧和隊列
*抽象數據類型棧的定義
*棧的表示和實現
棧的應用舉例：
迷宮求解
**表達式求值
**棧與遞歸的實現
*抽象數據類型隊列的定義
*鏈隊列—隊列的鏈式表示和實現
**循環隊列—隊列的順序表示和實現
串
串類型的定義
串的表示和實現
**串的模式匹配算法
串的應用舉例
數組和廣義表
數組的定義
*數組的順序表示和實現
*矩陣的壓縮存儲：
特殊矩陣
稀疏矩陣
*廣義表的概念
*廣義表的存儲
廣義表的應用舉例
樹和二叉樹
樹的定義和基本術語
*二叉樹：
二叉樹的定義
二叉樹的性質
二叉樹的存儲結構
**二叉樹的遍歷
**線索二叉樹
樹和森林：
樹的存儲結構
靜態鏈表
樹、森林和二叉樹的轉換
樹的遍歷
*樹的應用舉例：
哈夫曼樹
哈夫曼編碼
回溯法與樹的遍歷
圖
*圖的定義和基本術語
圖的存儲結構：
**鄰接矩陣
**鄰接表
十字鏈表
鄰接多重表
**圖的遍歷：
深度優先搜索遍歷
廣度優先搜索遍歷
*最小生成樹：
生成樹和最小生成樹
普里姆算法
克魯斯卡爾算法
有向無環圖及應用：
*拓撲排序
關鍵路徑
最短路徑
查找
查找基本概念
順序表的查找：
順序查找
**有序表的查找
分塊查找
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+樹
哈希表：
*哈希表的基本概念
構造哈希函數的方法
*解決哈希沖突的方法
*哈希表的查找
內部排序
排序的基本概念
**插入排序：
直接插入排序
希爾排序
**冒泡排序
**快速排序
**選擇排序：
直接選擇排序
堆排序
**歸并排序
基數排序
*各種內部排序方法比較
第一部分 計算機組成原理
一、考試范圍
計算機系統概論，運算方法與運算器，內部存儲器，指令系統，中央處理機，總線系統，
外圍設備，輸入輸出系統，操作系統支持。
在考查基本概念、基本理論的基礎上，注重考查學生運用基本知識分析和解決實際問題
的能力。要求學生對計算機組成原理有比較深入的認識，主要包括下面 3 個方面：
1、深刻理解計算機系統各功能部件的功能、組成和工作原理，正確理解各功能部件之
間相互關系以及它們在計算機系統中所起的作用。
2、了解和掌握計算機系統某些部件的設計與分析技術，包括數據與指令的編碼、存儲、
輸人輸出等。
3、理解和掌握計算機系統中的基本概念和方法，并能將這些概念和方法運用在后繼課
的學習中。
二、考試形式與試卷結構
1.考查內容及其考查比例：基本概念占 30%分、理解占 30%分、綜合能力占 40%分。
2.試卷結構與考試題型：填空題、選擇、問答題、綜合計算題等。
三、參考書目
《計算機組成原理》（第五版），白中英主編，科學出版社，2013 年。
四、考查要點
1、計算機系統層次結構的實際含義，各部件的基本功能。計算機系統的基本概念： 寄
存器、算術邏輯單元、存儲器、字、字節、地址、指令流、 地址流、CPU、總線、主存、
輔存、DMA 等。
2、數的基本知識，計算機中數的表示方法，機器數的定義及與真值的互換，信息校驗
的實際意義和方法。定點數運算方法；浮點數四則運算方法；算術邏輯單元的組成及工作原
理。運算器的功能，功能部件和結構。
3、存儲器的基本知識，現代主存儲器的結構和工作原理、設計原理和方法；高速緩沖
存儲器的組織、工作原理，地址影象方法及替換算法；軟硬盤存儲器的結構及工作原理，磁
記錄原理和磁記錄方式；存儲器的校驗和 CRC 碼校驗。虛擬存儲器概念及有關內容。
4、指令系統的意義和重要性；指令格式，指令和操作數的尋址方式和尋址過程；完備
性指令系統的設計。
5、中央處理機的功能與組織，指令處理的相關知識和控制原理，時序發生器設置的意
義及時序產生器的組織和工作原理。微程序控制器和硬布線控制器的設計思想、原理、組織
特征、工作原理及有關知識；流水 CPU 的有關概念。
6、單機系統總線結構及其特征，總線的仲裁與通信及其有關知識。
7、外圍設備的類型、功能和特點；多種信息存儲或顯示方式的工作原理。
8、幾種輸入輸出控制方式的控制原理和數據傳送的過程。中斷系統設置的意義及中斷
過程實現的技術和相關知識。
9、操作系統對計算機各功能部件的工作機理。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
|
|
上一篇文章： 2018年上海理工大學控制科學與工程復試參考科目考研復試大綱
下一篇文章： 2018年上海理工大學軟件工程復試筆試參考書目考研復試大綱
|
|
|
|
|
|
文章搜索
您現在的位置： 
