832計算機組成原理與數(shù)據(jù)結(jié)構(gòu)(計算機新增考試大綱)

832計算機組成原理與數(shù)據(jù)結(jié)構(gòu)(計算機新增考試大綱)考試科目：832計算機組成原理與數(shù)據(jù)結(jié)構(gòu)一、復(fù)習(xí)要求：該考試科目涵蓋計算機組成原理和數(shù)據(jù)結(jié)構(gòu)等學(xué)科專業(yè)的基礎(chǔ)課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運用所學(xué)的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實際問題。二、試卷滿分及考試時間：本試卷滿分為150分，考試時間為180分鐘。1）答題方式為閉卷、筆試2）考試內(nèi)容結(jié)構(gòu)包括：計算機組成原理70分數(shù)據(jù)結(jié)構(gòu)80分3）試卷題型結(jié)構(gòu)單項選擇題60分（30小題，每小題2分）簡答分析題30分綜合應(yīng)用題60分三、復(fù)習(xí)內(nèi)容：A.計算機組成原理部分1．復(fù)習(xí)要求：1）理解單處理器計算機系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計算機系統(tǒng)的整機概念。2）理解計算機系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面，掌握指令集體系結(jié)構(gòu)的基本知識和基本實現(xiàn)方法。3）能夠運用計算機組成的基本原理和基本方法，對有關(guān)計算機硬件系統(tǒng)中的理論和實際問題進行計算、分析，并能對一些基本部件進行簡單設(shè)計。2．主要復(fù)習(xí)內(nèi)容：1)計算機系統(tǒng)概述（1）計算機發(fā)展歷程（2）計算機系統(tǒng)層次結(jié)構(gòu)a.計算機硬件的基本組成b.計算機軟件的分類c.計算機的工作過程（3）計算機性能指標吞吐量、響應(yīng)時間；CPU時鐘周期、主頻、CPI、CPU執(zhí)行時間；MIPS、MFLOPS。2)數(shù)據(jù)的（1）表示和運算數(shù)制與編碼a.進位計數(shù)制及其相互轉(zhuǎn)換b.真值和機器數(shù)c.BCD碼d.字符與字符串e.校驗碼（2）定點數(shù)的表示和運算a.定點數(shù)的表示（1）CPU的功能和基本結(jié)構(gòu)（2）指令執(zhí)行過程（3）數(shù)據(jù)通路的功能和基本結(jié)構(gòu)（4）控制器的功能和工作原理a.硬布線控制器b.微程序控制器微程序、微指令和微命令；微指令的編碼方式；微地址的形式方式。（5）指令流水線a.指令流水線的基本概念b.指令流水線的基本實現(xiàn)c.超標量和動態(tài)流水線的基本概念（6）多核處理器的基本概念6)輸入輸出（I/O）系統(tǒng)（1）I/O系統(tǒng)基本概念（2）I/O接口（I/O控制器）a.I/O接口的功能和基本結(jié)構(gòu)b.I/O端口及其編址c.I/O地址空間及其編碼（3）I/O方式a.程序查詢方式b.程序中斷方式中斷的基本概念；中斷響應(yīng)過程；中斷處理過程；多重中斷和中斷屏蔽的概念。c.DMA方式DMA控制器的組成；DMA傳送過程。d.通道方式B.數(shù)據(jù)結(jié)構(gòu)部分1．復(fù)習(xí)要求：1）掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。2）掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM行基本的時間復(fù)雜度與空間復(fù)雜度的分析。3）能夠數(shù)據(jù)結(jié)構(gòu)基本2．主要復(fù)習(xí)1）線性表原理和方法進行問題的分析與求解，具備采用C或C++或?qū)崿F(xiàn)算法的能力。內(nèi)容：（1）線性表的定義和基本操作（2）線性表的實現(xiàn)a.順序存儲b.鏈式存儲c.線性表的應(yīng)用2）棧、隊列和數(shù)組（1）棧和隊列的基本概念（2）棧和隊列的順序存儲結(jié)構(gòu)（3）棧和隊列的鏈式存儲結(jié)構(gòu)（4）棧和隊列的應(yīng)用特殊矩陣的壓縮存儲3）樹與二叉樹（5）（1）樹的概念（2）二叉樹a.二叉樹的定義及其主要特征b.二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)c.二叉樹的遍歷d.線索二叉樹的基本概念和構(gòu)造（3）樹、森林a.樹的存儲結(jié)構(gòu)b.森林與二叉樹的轉(zhuǎn)換c.樹和森林的遍歷（4）樹與二叉樹的應(yīng)用a.二叉排序樹b.平衡二叉樹c.哈夫曼（Huffman）樹和哈夫曼編碼4）圖（1）圖的基本概念（2）圖的存儲及基本操作a.鄰接矩陣法b.鄰接表法（3）圖的遍歷a.深度優(yōu)先搜索b.廣度優(yōu)先搜索（4）圖的基本應(yīng)用a.最?。ù鷥r）生成樹b.最短路徑c.拓撲排序d.關(guān)鍵路徑5）查找（1）查找的基本概念（2）（3）（4）順序查找法折半查找法散列（Hash）表（5）6）排序查找算法的分析及應(yīng)用（1）排序