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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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