信與系統(tǒng)考試水平復(fù)習(xí)大綱

1、 833“計算機學(xué)科專業(yè)基礎(chǔ)綜合”復(fù)習(xí)參考提綱一、 考察目標(biāo)計算機學(xué)科專業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)結(jié)構(gòu)和計算機組織與體系結(jié)構(gòu)等學(xué)科專業(yè)基礎(chǔ)課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運用所學(xué)的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實際問題。二、 考試形式和試卷結(jié)構(gòu)1、 試卷滿分及考試時間：本試卷滿分為150，考試時間為180分鐘2、 答題方式：閉卷，筆試3、 試卷內(nèi)容結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)75分、計算機組織與體系結(jié)構(gòu)75分三、 考察范圍數(shù)據(jù)結(jié)構(gòu)：【總體要求】“數(shù)據(jù)結(jié)構(gòu)”要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的基本理論和基本方法，使學(xué)生具備基本的數(shù)據(jù)結(jié)構(gòu)分析、設(shè)計、求解實際問

2、題的能力。要求掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；掌握線性表、樹與二叉樹、圖的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、基本操作，以及基本操作在不同的物理結(jié)構(gòu)上的實現(xiàn)，并能夠?qū)Σ僮魉惴ㄟM行基本的時間復(fù)雜度和空間復(fù)雜度進行分析；掌握基本的查找和排序方法，并能夠利用這些方法對實際問題進行分析和求解，具備采用C或C+或 JAVA語言設(shè)計與實現(xiàn)算法的能力。（一）數(shù)據(jù)結(jié)構(gòu)基本概念 1.復(fù)習(xí)內(nèi)容數(shù)據(jù)結(jié)構(gòu)、算法的基本定義，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，算法的性能評價方法。2.具體要求數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)算法的概念和算法的性能評價（二）線性表 1.復(fù)習(xí)內(nèi)容線性表的概念和基本運算，線性表的順序存

3、儲和鏈式存儲，線性表的基本運算在順序存儲和鏈式存儲結(jié)構(gòu)上的實現(xiàn)。2.具體要求線性表的概念和基本運算線性表的順序存儲線性表的鏈式存儲線性表的應(yīng)用 （三）棧和隊列 1.復(fù)習(xí)內(nèi)容棧和隊列的基本概念、基本操作和存儲結(jié)構(gòu)。2.具體要求 棧和隊列的基本概念和基本操作棧和隊列的順序存儲結(jié)構(gòu)棧和隊列的鏈式存儲結(jié)構(gòu)棧和隊列的應(yīng)用（四）串 1.復(fù)習(xí)內(nèi)容串的基本概念、存儲結(jié)構(gòu)和模式匹配算法2.具體要求 串的基本概念和基本操作串的順序存儲結(jié)構(gòu)串的鏈式存儲結(jié)構(gòu)模式匹配算法（五）數(shù)組和廣義表 1.復(fù)習(xí)內(nèi)容數(shù)組和廣義表的基本概念、數(shù)組的順序存儲和特殊矩陣的壓縮存儲。2.具體要求數(shù)組的基本概念和基本操作數(shù)組的順序存

4、儲和實現(xiàn)特殊矩陣的壓縮存儲廣義表的基本概念和存儲（六）樹與二叉樹 1.復(fù)習(xí)內(nèi)容樹與二叉樹的基本概念、存儲結(jié)構(gòu)和性質(zhì)，樹與二叉樹的遍歷，樹、森林與二叉樹的轉(zhuǎn)換，哈夫曼(Huffman)樹的概念和應(yīng)用。2.具體要求（一）樹的概念（二）二叉樹二叉樹的定義及主要特征二叉樹的順序存儲結(jié)構(gòu)二叉樹的鏈式存儲結(jié)構(gòu)二叉樹的遍歷線索二叉樹的基本概念和構(gòu)造（三）樹、森林樹的存儲結(jié)構(gòu)樹、森林與二叉樹的轉(zhuǎn)換樹和森林的遍歷（四）哈夫曼(Huffman)樹和哈夫曼編碼（七）圖 1.復(fù)習(xí)內(nèi)容圖的基本概念和存儲結(jié)構(gòu)、圖的遍歷、圖的基本應(yīng)用算法。2.具體要求 (一)   圖的基本概念(二) 

5、;  圖的存儲結(jié)構(gòu) 鄰接矩陣法 鄰接表法  逆鄰接表法 十字鏈表 鄰接多重表(三)   圖的遍歷 深度優(yōu)先遍歷 廣度優(yōu)先遍歷(四)   圖的基本應(yīng)用算法最小生成樹拓撲排序關(guān)鍵路徑 最短路徑（八）查找 1.復(fù)習(xí)內(nèi)容查找的基本概念、靜態(tài)查找表和動態(tài)查找表、哈希表。2.具體要求(一)   查找的基本概念(二)   靜態(tài)查找表順序查找法 折半查找法索引順序查找法(三)  動態(tài)查找表 &

6、#160; 二叉排序樹及其基本操作 平衡二叉排序樹及其基本操作B樹及其基本操作B+樹的基本概念(五)   哈希(Hash)表哈希表的基本概念哈希函數(shù)的構(gòu)造沖突的解決方法(六)   查找算法的分析及應(yīng)用 （九）排序 1.復(fù)習(xí)內(nèi)容排序的基本概念、排序算法和性能分析。2.具體要求(一)   排序的基本概念(二)   插入排序直接插入排序折半插入排序2-路插入排序表插入排序希爾排序(三)   交換排序起泡排序快速排序(四)  

7、; 選擇排序簡單選擇排序堆排序(五)   歸并排序(六)   基數(shù)排序(七) 外部排序計算機組織與體系結(jié)構(gòu)四、 總體要求 “計算機組織與體系結(jié)構(gòu)”要求學(xué)生掌握單處理器計算機系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計算機系統(tǒng)的整機概念。要求掌握計算機系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面；掌握計算機數(shù)據(jù)表示的方法，包括定點數(shù)和浮點數(shù)的表示；掌握運算器的原理和實現(xiàn)電路；掌握存儲層次的概念，會解決Cache存儲的一些基本問題；掌握不同類型存儲器形式，包括SRAM，DRAM，ROM；掌握磁盤基本原理及RAID；掌

8、握指令集體系結(jié)構(gòu)的基本知識和基本實現(xiàn)方法；掌握中央處理器控制器部分的兩種基本設(shè)計方法，即硬布線和微程序控制，能夠根據(jù)模擬中央處理器化簡控制信號邏輯或者編寫簡單微操作流程；熟悉中央處理器的時序邏輯，即指令周期、CPU周期、節(jié)拍周期、時鐘周期之間的關(guān)系；掌握計算機輸入輸出系統(tǒng)的基本概念，程序查詢方式、中斷方式和直接內(nèi)存獲取方式；掌握總線的仲裁方式和特點；基本掌握并行計算機的原理和發(fā)展趨勢；基本掌握對稱多處理器系統(tǒng)的特點；掌握流水線技術(shù)，能夠計算各種流水線的性能指標(biāo)參數(shù)，分析流水線的特點，解決數(shù)據(jù)相關(guān)的方法等；能夠運用計算機組成的基本原理和基本方法，對有關(guān)計算機硬件系統(tǒng)中的理論和實際問題進行計算、分

9、析，并能對一些基本部件進行簡單設(shè)計。研究生課程考試是所學(xué)知識的總結(jié)性考試，考試水平應(yīng)達到或超過本科專業(yè)相應(yīng)的課程要求水平。五、 各章復(fù)習(xí)要點（一）計算機系統(tǒng)概論 1.復(fù)習(xí)內(nèi)容計算機的基本組成，馮.諾依曼計算機原理，計算機系統(tǒng)的層次結(jié)構(gòu)，計算機的分類及性能描述，計算機的發(fā)展歷程2.具體要求*計算機的基本組成*硬件部分*軟件組成*軟件的分類*馮.諾依曼計算機原理*馮.諾依曼計算機概念*馮.諾依曼計算機特點*計算機系統(tǒng)的層次結(jié)構(gòu)*層次結(jié)構(gòu)圖*各層的含義和界面定義*計算機體系結(jié)構(gòu)、組成和實現(xiàn)*計算機的分類及性能描述*Flynn分類法*Amdahl定律和應(yīng)用*吞吐量、響應(yīng)時間*CPU時鐘周期、主頻、CP

10、I、CPU執(zhí)行時間*MIPS、MFLOPS（二）計算機系統(tǒng)中的數(shù)據(jù)表示 1.復(fù)習(xí)內(nèi)容數(shù)制與編碼，定點數(shù)據(jù)表示，浮點數(shù)據(jù)表示，糾錯和校驗2.具體要求*數(shù)制與編碼*進位計數(shù)制及其相互轉(zhuǎn)換*真值和機器數(shù)* BCD碼*字符與字符串*漢字的表示*定點數(shù)據(jù)表示*無符號數(shù)的表示*有符號數(shù)的表示*原碼、反碼、補碼、移碼*浮點數(shù)據(jù)表示*格式定義*規(guī)格化*數(shù)據(jù)范圍*IEEE754標(biāo)準*糾錯和校驗*奇偶校驗*漢明編碼*循環(huán)冗余校驗（三）運算方法與運算器1.復(fù)習(xí)內(nèi)容定點數(shù)的位移運算，原碼定點數(shù)的加/減運算，補碼定點數(shù)的加/減運算，定點數(shù)的乘/除運算，溢出概念和判別方法，浮點數(shù)的加/減運算，浮點數(shù)的乘/除運算，算術(shù)邏輯

11、單元ALU2.具體要求*原碼定點數(shù)的加/減運算*方法，應(yīng)用*補碼定點數(shù)的加/減運算*方法，應(yīng)用*行波進位、先行進位加法器*移位處理*溢出處理和判斷*定點數(shù)的乘/除運算*原碼乘法，補碼乘法*恢復(fù)余數(shù)，不恢復(fù)余數(shù)除法*陣列乘法器*陣列除法器*浮點數(shù)的加/減運算*對階*尾數(shù)加減*規(guī)格化*溢出處理*浮點數(shù)的乘/除運算*方法*應(yīng)用*規(guī)格化*算術(shù)邏輯單元ALU*組成*類型（四）存儲系統(tǒng)1.復(fù)習(xí)內(nèi)容存儲器的分類，存儲器的層次化結(jié)構(gòu)，半導(dǎo)體隨機存取存儲器，主存儲器與CPU的連接，雙口RAM和多模塊存儲器，高速緩沖存儲器，虛擬存儲器，硬盤存儲器2.具體要求*存儲器的分類*按照不同方式進行分類的方法*存儲器容量、

12、速度、可靠性*存儲器的層次化結(jié)構(gòu)*具體層次化形式*各種存儲器的位置*半導(dǎo)體隨機存取存儲器*SRAM存儲器的工作原理*DRAM存儲器的工作原理*只讀存儲器*主存儲器與CPU的連接*字擴展方式*位擴展方式*雙口RAM和多模塊存儲器*多端口組織形式*交叉存儲方式*按內(nèi)容存儲的存儲器*高速緩沖存儲器* Cache的基本工作原理*Cache和主存之間的映射方式*Cache中主存塊的替換算法*Cache寫策略*虛擬存儲器*虛擬存儲器的基本概念*頁式虛擬存儲器*段式虛擬存儲器*段頁式虛擬存儲器*TLB(快表)*硬盤存儲器*磁記錄方式基本原理*磁盤的基本參數(shù)及計算 *RAID（五）指令系統(tǒng) 1.復(fù)習(xí)內(nèi)容指令格

13、式，指令的尋址方式，CISC和RISC的基本概念。2.具體要求*指令格式*指令的基本格式*定長操作碼指令格式*擴展操作碼指令格式*端序*指令的尋址方式*有效地址的概念*數(shù)據(jù)尋址和指令尋址*常見尋址方式* CISC和RISC的基本概念*RISC的發(fā)展歷程*RISC的技術(shù)特點（六）中央處理器 1.復(fù)習(xí)內(nèi)容CPU的功能和基本結(jié)構(gòu)，指令執(zhí)行過程，數(shù)據(jù)通路的功能和基本結(jié)構(gòu)，控制器的功能和工作原理。2.具體要求* CPU的功能和基本結(jié)構(gòu)*CPU的主要構(gòu)成部件*CPU內(nèi)的常見寄存器*CPU內(nèi)部的數(shù)據(jù)通路*指令執(zhí)行過程*時序發(fā)生器*CPU內(nèi)部時序概念*典型指令的執(zhí)行過程*數(shù)據(jù)通路的功能和基本結(jié)構(gòu)*控制器的功能

14、和工作原理*硬布線控制器*微程序控制器*微操作、微命令、微指令、微程序*互斥和相容（七）流水線技術(shù)與指令級并行 1.復(fù)習(xí)內(nèi)容流水線概念，流水線分類，流水線性能指標(biāo)，流水線相關(guān)處理，超標(biāo)量處理，VLIW，多核處理器的基本概念。2.具體要求*流水線概念*流水線分類*不同方式進行分類*靜態(tài)多功能流水線*動態(tài)多功能流水線*流水線性能指標(biāo)*吞吐率*效率*加速比*時空圖*流水線相關(guān)處理*數(shù)據(jù)相關(guān)*指令相關(guān)*相關(guān)處理方式，相關(guān)直接通路*超標(biāo)量處理*定義*記分板*VLIW*VLIW概念及特點*多核處理器的基本概念（八）總線與輸入輸出系統(tǒng) 1.復(fù)習(xí)內(nèi)容總線概述，總線仲裁，總線操作和定時，總線標(biāo)準，I/O系統(tǒng)基本

15、概念，外部設(shè)備，I/O接口，I/O方式。2.具體要求*總線概述*總線的基本概念*總線的分類*總線的組成及性能指標(biāo)*總線仲裁*集中仲裁方式：菊花鏈方式、輪詢計數(shù)、獨立請求方式*分布仲裁方式*總線操作和定時*同步定時方式*異步定時方式*總線標(biāo)準* I/O系統(tǒng)基本概念*外部設(shè)備*輸入設(shè)備*輸出設(shè)備* I/O接口* I/O接口的功能和基本結(jié)構(gòu)* I/O端口及其編址* I/O地址空間及其編碼* I/O方式*程序查詢方式*程序中斷方式：中斷的基本概念；中斷響應(yīng)過程；中斷處理過程；多重中斷和中斷屏蔽的概念*DMA方式：DMA控制器的組成；DMA傳送過程*通道方式（九）并行體系結(jié)構(gòu) 1.復(fù)習(xí)內(nèi)容并行處理的基本

16、途徑，互連開關(guān)網(wǎng)絡(luò)，對稱多處理器。2.具體要求*并行處理的基本途徑*時間重疊*資源重復(fù)*資源共享*互連開關(guān)網(wǎng)絡(luò)*定義*基本交換開關(guān)網(wǎng)絡(luò)*對稱多處理器六、 參考書目1、裘雪紅， 李伯成，劉凱，車向泉，計算機組成與體系結(jié)構(gòu)，高等教育出版社，2009.2、裘雪紅， 李伯成，計算機組成與體系結(jié)構(gòu)，西安電子科技大學(xué)出版社，2012.3、John L. Hennessy, David A.Patterson Computer Architecture: A Quantitative Approach , fourth edition, 機械工業(yè)出版社（影?。?0074、Stallings W.計算機組織與結(jié)構(gòu)性能設(shè)計（第6版），張昆藏等譯。北京：清華大學(xué)出版社，20055、王閔編著，計算機組成原理，電子工業(yè)出版社，2001.6、王愛英主編，計算機組成與結(jié)構(gòu)（第3版），清華大學(xué)出版社，1999.7、白中英主編，計算機組成與體系結(jié)構(gòu)（第三版·網(wǎng)絡(luò)版），科學(xué)出版社，2003.8、