《數(shù)據(jù)結(jié)構(gòu)及計(jì)算機(jī)組成原理》考試大綱和參考書(shū)目.doc

數(shù)據(jù)結(jié)構(gòu)及計(jì)算機(jī)組成原理考試大綱和參考書(shū)目第一部分 數(shù)據(jù)結(jié)構(gòu)參考教材：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），嚴(yán)蔚敏等主編，清華大學(xué)出版社，1997年4月第二版第一章 緒論 明確數(shù)據(jù)結(jié)構(gòu)的定義、研究的內(nèi)容，掌握算法及算法分析的概念，了解抽象數(shù)據(jù)類型的概念。第二章 線性表掌握線性表的概念，兩種存儲(chǔ)結(jié)構(gòu)順序表和鏈表的表示和實(shí)現(xiàn)、掌握鏈表（單鏈表、單循環(huán)鏈表和雙向鏈表）上的查找、插入、刪除基本操作及能編寫(xiě)鏈表上的綜合操作程序。第三章 棧和隊(duì)列掌握棧的概念，掌握順序棧、鏈棧的進(jìn)棧、出棧操作程序。能利用棧寫(xiě)出表達(dá)式求值過(guò)程，能用棧讀寫(xiě)遞歸程序。掌握隊(duì)列的概念，掌握循環(huán)隊(duì)列、循環(huán)鏈隊(duì)列的入隊(duì)、出隊(duì)操作程序。第四章 串掌握串的基本運(yùn)算的含義，掌握求子串位置的定位函數(shù)，理解KMP模式匹配算法和時(shí)間復(fù)雜度。第五章 多維數(shù)組和廣義表掌握多維數(shù)組及特殊矩陣的地址公式，廣義表的運(yùn)算和存儲(chǔ)。了解廣義表的遞歸算法。第六章 樹(shù)和二叉樹(shù)。掌握樹(shù)、二叉樹(shù)的定義、術(shù)語(yǔ)，二叉樹(shù)的性質(zhì)，掌握二叉樹(shù)的遞歸和非遞歸遍歷算法，掌握中序線索二叉樹(shù)的概念和遍歷算法，掌握Haffman樹(shù)及其應(yīng)用，了解樹(shù)與二叉樹(shù)的關(guān)系，了解回溯法與樹(shù)的遍歷。第七章 圖掌握?qǐng)D的定義、術(shù)語(yǔ)，掌握?qǐng)D的存儲(chǔ)，圖的遍歷算法，掌握最小生成樹(shù)、拓?fù)渑判?、關(guān)鍵路徑、最短路徑概念，了解其算法。第九章 查找掌握有序表的查找算法和查找的時(shí)間復(fù)雜度，掌握二叉排序樹(shù)的查找、插入和刪除算法，掌握平衡二叉樹(shù)和B-樹(shù)的插入、刪除概念。 掌握哈希表構(gòu)造、解決沖突的方法及哈希表的查找。第十章 內(nèi)部排序掌握直接插入排序、冒泡排序、簡(jiǎn)單選擇排序、快速排序、堆排序、歸并排序和希爾排序算法和時(shí)間復(fù)雜度，了解基數(shù)排序的概念。專業(yè)課數(shù)據(jù)結(jié)構(gòu)考試大綱和參考書(shū)目參考教材:數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 , 嚴(yán)蔚敏主編 , 清華大學(xué)出版社參考用書(shū):數(shù)據(jù)結(jié)構(gòu)習(xí)題詳解, 李春葆編著, 清華大學(xué)出版社課程內(nèi)容（無(wú)標(biāo)記章節(jié)一般了解、不考，打*號(hào)標(biāo)記章節(jié)要求掌握，打*號(hào)標(biāo)記章節(jié)要求重點(diǎn)掌握）緒論數(shù)據(jù)結(jié)構(gòu)定義基本概念和術(shù)語(yǔ)*算法描述和算法分析抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)線性表線性表的基本概念線性表順序表示和實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)： *線性鏈表 *循環(huán)鏈表 *雙向鏈表順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的比較*線性表的應(yīng)用舉例棧和隊(duì)列*抽象數(shù)據(jù)類型棧的定義*棧的表示和實(shí)現(xiàn)棧的應(yīng)用舉例： 迷宮求解 *表達(dá)式求值*棧與遞歸的實(shí)現(xiàn)*抽象數(shù)據(jù)類型隊(duì)列的定義*鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)*循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn)串串類型的定義串的表示和實(shí)現(xiàn)*串的模式匹配算法串的應(yīng)用舉例數(shù)組和廣義表數(shù)組的定義*數(shù)組的順序表示和實(shí)現(xiàn)*矩陣的壓縮存儲(chǔ)：特殊矩陣 稀疏矩陣 *廣義表的概念*廣義表的存儲(chǔ)廣義表的應(yīng)用舉例樹(shù)和二叉樹(shù)樹(shù)的定義和基本術(shù)語(yǔ)*二叉樹(shù)： 二叉樹(shù)的定義 二叉樹(shù)的性質(zhì) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)*二叉樹(shù)的遍歷*線索二叉樹(shù)樹(shù)和森林： 樹(shù)的存儲(chǔ)結(jié)構(gòu) 靜態(tài)鏈表 樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換 樹(shù)的遍歷*樹(shù)的應(yīng)用舉例： 哈夫曼樹(shù) 哈夫曼編碼回溯法與樹(shù)的遍歷圖*圖的定義和基本術(shù)語(yǔ)圖的存儲(chǔ)結(jié)構(gòu)： *鄰接矩陣 *鄰接表 十字鏈表 鄰接多重表*圖的遍歷： 深度優(yōu)先搜索遍歷 廣度優(yōu)先搜索遍歷*最小生成樹(shù)： 生成樹(shù)和最小生成樹(shù) 普里姆算法 克魯斯卡爾算法有向無(wú)環(huán)圖及應(yīng)用： *拓?fù)渑判?關(guān)鍵路徑最短路徑查找查找基本概念順序表的查找： 順序查找 *有序表的查找 分塊查找8.3樹(shù)表的查找 *8.3.1二叉搜索樹(shù) *8.3.2平衡二叉樹(shù) 8.3.3 B_樹(shù) 8.3.4 B+樹(shù)*8.4哈希表 8.4.1哈希表的基本概念 8.4.2構(gòu)造哈希函數(shù)的方法 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基數(shù)排序9.7各種內(nèi)部排序方法比較9.8外排序*二叉排序樹(shù)*平衡二叉樹(shù)*B_樹(shù)B+樹(shù)哈希表： *哈希表的基本概念 構(gòu)造哈希函數(shù)的方法 *解決哈希沖突的方法 *哈希表的查找內(nèi)部排序排序的基本概念*插入排序： 直接插入排序 希爾排序*冒泡排序*快速排序*選擇排序： 直接選擇排序 堆排序*歸并排序基數(shù)排序*各種內(nèi)部排序方法比較第一部分 計(jì)算機(jī)組成原理一、考試范圍計(jì)算機(jī)系統(tǒng)概論，運(yùn)算方法與運(yùn)算器，內(nèi)部存儲(chǔ)器，指令系統(tǒng)，中央處理機(jī)，總線系統(tǒng)，外圍設(shè)備，輸入輸出系統(tǒng)，操作系統(tǒng)支持。在考查基本概念、基本理論的基礎(chǔ)上，注重考查學(xué)生運(yùn)用基本知識(shí)分析和解決實(shí)際問(wèn)題的能力。要求學(xué)生對(duì)計(jì)算機(jī)組成原理有比較深入的認(rèn)識(shí)，主要包括下面3個(gè)方面：1、深刻理解計(jì)算機(jī)系統(tǒng)各功能部件的功能、組成和工作原理，正確理解各功能部件之間相互關(guān)系以及它們?cè)谟?jì)算機(jī)系統(tǒng)中所起的作用。2、了解和掌握計(jì)算機(jī)系統(tǒng)某些部件的設(shè)計(jì)與分析技術(shù)，包括數(shù)據(jù)與指令的編碼、存儲(chǔ)、輸人輸出等。 3、理解和掌握計(jì)算機(jī)系統(tǒng)中的基本概念和方法，并能將這些概念和方法運(yùn)用在后繼課的學(xué)習(xí)中。二、考試形式與試卷結(jié)構(gòu)1.考查內(nèi)容及其考查比例：基本概念占30%分、理解占30%分、綜合能力占40%分。2.試卷結(jié)構(gòu)與考試題型：填空題、選擇、問(wèn)答題、綜合計(jì)算題等。三、參考書(shū)目計(jì)算機(jī)組成原理（第四版），白中英主編，科學(xué)出版社，2007年12月。四、考查要點(diǎn)1、計(jì)算機(jī)系統(tǒng)層次結(jié)構(gòu)的實(shí)際含義，各部件的基本功能。計(jì)算機(jī)系統(tǒng)的基本概念： 寄存器、算術(shù)邏輯單元、存儲(chǔ)器、字、字節(jié)、地址、指令流、 地址流、CPU、總線、主存、輔存、DMA等。2、數(shù)的基本知識(shí)，計(jì)算機(jī)中數(shù)的表示方法，機(jī)器數(shù)的定義及與真值的互換，信息校驗(yàn)的實(shí)際意義和方法。定點(diǎn)數(shù)運(yùn)算方法；浮點(diǎn)數(shù)四則運(yùn)算方法；算術(shù)邏輯單元的組成及工作原理。運(yùn)算器的功能，功能部件和結(jié)構(gòu)。3、存儲(chǔ)器的基本知識(shí)，現(xiàn)代主存儲(chǔ)器的結(jié)構(gòu)和工作原理、設(shè)計(jì)原理和方法；高速緩沖存儲(chǔ)器的組織、工作原理，地址影象方法及替換算法；軟硬盤(pán)存儲(chǔ)器的結(jié)構(gòu)及工作原理，磁記錄原理和磁記錄方式；存儲(chǔ)器的校驗(yàn)和CRC碼校驗(yàn)。虛擬存儲(chǔ)器概念及有關(guān)內(nèi)容。4、指令系統(tǒng)的意義和重要性；指令格式，指令和操作數(shù)的尋址方式和尋址過(guò)程；完備性指令系統(tǒng)的設(shè)計(jì)。5、中央處理機(jī)的功能與組織，指令處理的相關(guān)知識(shí)和控制原理，時(shí)序發(fā)生器設(shè)置的意義及時(shí)序產(chǎn)生器的組織和工作原理。微程序控制器和硬布線控制器的設(shè)計(jì)思想、原理、組織特征、工作原理及有關(guān)知識(shí)；流水CPU的有