山東大學(xué)851專業(yè)目錄

1、851山大計(jì)算機(jī)基礎(chǔ)綜合考試大綱 計(jì)算機(jī)基礎(chǔ)綜合包括數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)組成原理三部分內(nèi)容，每部分內(nèi)容各占1/3。I 數(shù)據(jù)結(jié)構(gòu)課程基本要求 全面系統(tǒng)地掌握隊(duì)列、堆、棧、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)，深刻理解和熟練掌握課程中的典型算法，為計(jì)算機(jī)學(xué)科的學(xué)習(xí)打下堅(jiān)實(shí)基礎(chǔ)。考試內(nèi)容1 鏈表、間接尋址和模擬指針2數(shù)組和矩陣3堆棧和隊(duì)列及其應(yīng)用4跳表和散列5二叉樹和其他樹6合并/搜索應(yīng)用,堆和堆排序7左高樹,霍夫曼編碼和競賽樹8搜索樹,AVL樹或紅黑樹,直方圖9圖10圖和貪婪算法11貨箱裝載,0/1背包,最短路徑和生成樹12分而治之算法13動態(tài)編程14回溯和分枝定界算法 參考書目1 數(shù)據(jù)結(jié)構(gòu)，算法與應(yīng)用 -

2、C+語言描述Data Structures,Algorithms,and Applications in C+Sartaj Sahni 著 汪詩林，孫曉東 譯 機(jī)械工業(yè)出版社 2000年出版 教材科，書店均有2 數(shù)據(jù)結(jié)構(gòu) 殷仁昆 著 清華大學(xué)出版社II 操作系統(tǒng)課程基本要求操作系統(tǒng)是計(jì)算機(jī)類學(xué)科的一門核心專業(yè)基礎(chǔ)課程，具有較強(qiáng)的理論性和實(shí)踐性。該課程的主要包括進(jìn)程管理、內(nèi)存管理、存儲管理（包括文件系統(tǒng)與輸入/輸出系統(tǒng)）、保護(hù)與安全等內(nèi)容的相關(guān)概念、設(shè)計(jì)原理和實(shí)現(xiàn)方法。要求：1. 了解操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的作用、地位、發(fā)展和特點(diǎn)。2. 理解操作系統(tǒng)的基本概念、主要功能、主要組成部分，掌握操作系

3、統(tǒng)各個組成部分的設(shè)計(jì)方法和實(shí)現(xiàn)技術(shù)。3. 能夠運(yùn)用所學(xué)的操作系統(tǒng)原理、方法和技術(shù)對相關(guān)問題進(jìn)行分析和解決?？荚噧?nèi)容一、導(dǎo)論1. 操作系統(tǒng)的概念2. 計(jì)算機(jī)系統(tǒng)的操作、存儲結(jié)構(gòu)、輸入輸出結(jié)構(gòu)和計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)3. 操作系統(tǒng)的結(jié)構(gòu)組成、操作系統(tǒng)的操作及各部分的功能、高速緩沖存儲器CACHE4. 操作系統(tǒng)的分類和運(yùn)行環(huán)境二、操作系統(tǒng)結(jié)構(gòu)1. 操作系統(tǒng)提供的服務(wù)類型2. 操作系統(tǒng)的用戶接口類型3. 系統(tǒng)調(diào)用及類型4. 操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)方法5. 操作系統(tǒng)的結(jié)構(gòu)分類及優(yōu)缺點(diǎn)6. 虛擬機(jī)的基本概念和原理三、進(jìn)程1. 進(jìn)程的概念、組織、控制和狀態(tài)轉(zhuǎn)換2. 進(jìn)程調(diào)度的基本概念3. 進(jìn)程的操作，包括進(jìn)程的

4、生成、終止等4. 進(jìn)程通信四、線程1. 線程的概念與動機(jī)2. 多線程模型五、CPU調(diào)度1. 調(diào)度的基本概念2. 調(diào)度的時機(jī)、切換和過程3. 調(diào)度的基本準(zhǔn)則4. 典型調(diào)度方法：先來先服務(wù)調(diào)度算法、最短作業(yè)優(yōu)先調(diào)度算法、優(yōu)先級調(diào)度算法、時間片輪轉(zhuǎn)調(diào)度算法、多級隊(duì)列調(diào)度算法、多級反饋隊(duì)列調(diào)度算法5. 線程調(diào)度6. 調(diào)度算法的性能評估六、進(jìn)程同步1. 進(jìn)程同步的基本概念2. 臨界區(qū)訪問的原則及實(shí)現(xiàn)臨界區(qū)互斥的基本方法：軟件實(shí)現(xiàn)方法和硬件實(shí)現(xiàn)方法3. 信號量概念與基本機(jī)制4. 經(jīng)典同步問題：生產(chǎn)者消費(fèi)者問題、讀者寫者問題、哲學(xué)家就餐問題和理發(fā)師問題。5. 管程的基本概念、原理和實(shí)現(xiàn)七、死鎖1. 死鎖的概

5、念及條件2. 死鎖的處理策略3. 死鎖的預(yù)防及實(shí)現(xiàn)方法4. 死鎖的避免：系統(tǒng)安全狀態(tài)、資源分配圖算法、銀行家算法5. 死鎖的檢測方法和解除八、主存1. 內(nèi)存管理的基本概念：程序的裝入與鏈接、邏輯地址與物理地址、內(nèi)存保護(hù)2. 交換技術(shù)3. 內(nèi)存的分配管理方法：連續(xù)分配管理方法、分頁管理方法、分段管理方法、段頁式管理方法。九、虛擬內(nèi)存1. 虛擬內(nèi)存的基本概念2. 請求分頁管理方法3. 頁面置換算法：先進(jìn)先出置換算法、最佳置換算法、最近最少使用（近似）置換算法、近似最近最少使用置換算法4. 幀的分配策略5. 抖動現(xiàn)象的原因及解決方法6. 內(nèi)核內(nèi)存的分配方法7. 虛擬內(nèi)存中需要考慮的其他問題：預(yù)調(diào)頁、

6、頁大小的影響、TLB的搜索能力、逆向頁表等十、文件系統(tǒng)接口1. 文件的基本概念2. 文件的結(jié)構(gòu)：順序文件、索引文件等3. 文件的訪問方法4. 目錄結(jié)構(gòu)：文件的存儲結(jié)構(gòu)、單級目錄結(jié)構(gòu)、兩級目錄結(jié)構(gòu)、樹形目錄結(jié)構(gòu)、無環(huán)圖目錄結(jié)構(gòu)、通用圖目錄結(jié)構(gòu)5. 文件共享十一、文件系統(tǒng)實(shí)現(xiàn)1. 文件系統(tǒng)的結(jié)構(gòu)2. 文件系統(tǒng)的實(shí)現(xiàn)3. 目錄的實(shí)現(xiàn)4. 文件的磁盤空間分配方法：連續(xù)、鏈?zhǔn)?、索?. 空閑空間的管理十二、大容量存儲1. 磁盤的結(jié)構(gòu)2. 磁盤的調(diào)度方法：先到先服務(wù)調(diào)度算法、最短尋道時間調(diào)度算法、SCAN調(diào)度算法、C-SCAN調(diào)度算法、LOOK調(diào)度算法、C-LOOK調(diào)度算法3. 磁盤管理：格式化、引導(dǎo)塊、

7、壞塊的處理4. RAID結(jié)構(gòu)十三、輸入/輸出系統(tǒng)1. 輸入/輸出硬件2. 輸入/輸出訪問控制方式3. 輸入/輸出應(yīng)用接口4. 內(nèi)核輸入/輸出子系統(tǒng)：輸入/輸出調(diào)度、緩存、緩沖、假脫機(jī)與設(shè)備預(yù)留、錯誤處理、輸入/輸出保護(hù)、內(nèi)核數(shù)據(jù)結(jié)構(gòu)5. 輸入/輸出從請求到硬件操作的轉(zhuǎn)換過程十四、保護(hù)1. 保護(hù)的目標(biāo)與原則2. 保護(hù)域3. 訪問矩陣及實(shí)現(xiàn)方法：全局表、訪問列表、能力表十五、安全1. 系統(tǒng)中存在的安全問題以及安全措施的級別2. 程序的威脅：木馬、后門、邏輯炸彈、棧與緩沖溢出、病毒3. 系統(tǒng)與網(wǎng)絡(luò)威脅：蠕蟲、端口掃描、DoS參考書目1. Abraham Silberschatz / Peter Ba

8、er Galvin / Greg Gagne, Operating System Concepts (7th Edition), John Wiley & Sons, 2005.2. （美）西爾伯查茨，高爾文，加根著，操作系統(tǒng)概念（翻譯版），高等教育出版社，2007III 計(jì)算機(jī)組成原理課程基本要求1. 理解單處理器計(jì)算機(jī)系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計(jì)算機(jī)系統(tǒng)的整機(jī)概念；2. 理解計(jì)算機(jī)系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面，掌握指令集體系結(jié)構(gòu)的基本知識和基本實(shí)現(xiàn)方法；3. 能夠運(yùn)用計(jì)算機(jī)組成的基本原理和基本方法，對有關(guān)計(jì)算機(jī)硬件系統(tǒng)中的理論和

9、實(shí)際問題進(jìn)行計(jì)算、分析，并能對一些基本部件進(jìn)行簡單設(shè)計(jì)?？荚噧?nèi)容一、 計(jì)算機(jī)系統(tǒng)概述（一） 計(jì)算機(jī)發(fā)展歷程（二） 計(jì)算機(jī)系統(tǒng)層次結(jié)構(gòu)1. 計(jì)算機(jī)硬件的基本組成2. 計(jì)算機(jī)軟件的分類3. 計(jì)算機(jī)的工作過程（三） 計(jì)算機(jī)性能指標(biāo)吞吐量、響應(yīng)時間；CPU時鐘周期、主頻、CPI、CPU執(zhí)行時間；MIPS、MFLOPS。二、 數(shù)據(jù)的表示和運(yùn)算（一） 數(shù)制與編碼1. 進(jìn)位計(jì)數(shù)制及其相互轉(zhuǎn)換2. 真值和機(jī)器數(shù)3. BCD碼4. 字符與字符串5. 校驗(yàn)碼（二） 定點(diǎn)數(shù)的表示和運(yùn)算1. 定點(diǎn)數(shù)的表示無符號數(shù)的表示；有符號數(shù)的表示。2. 定點(diǎn)數(shù)的運(yùn)算定點(diǎn)數(shù)的位移運(yùn)算；原碼定點(diǎn)數(shù)的加/減運(yùn)算；補(bǔ)碼定點(diǎn)數(shù)的加/減運(yùn)算

10、；定點(diǎn)數(shù)的乘/除運(yùn)算；溢出概念和判別方法。（三） 浮點(diǎn)數(shù)的表示和運(yùn)算1. 浮點(diǎn)數(shù)的表示浮點(diǎn)數(shù)的表示范圍 2. 浮點(diǎn)數(shù)的加/減運(yùn)算（四） 算術(shù)邏輯單元ALU1. 串行加法器和并行加法器2. 算術(shù)邏輯單元ALU的功能和機(jī)構(gòu)三、 存儲器層次機(jī)構(gòu)（一） 存儲器的分類（二） 存儲器的層次化結(jié)構(gòu)（三） 半導(dǎo)體隨機(jī)存取存儲器1. SRAM存儲器的工作原理2. DRAM存儲器的工作原理3. 只讀存儲器4. Flash存儲器（四） 主存儲器與CPU的連接（五） 雙口RAM和多模塊存儲器（六） 高速緩沖存儲器（Cache）1. 程序訪問的局部2. Cache的基本工作原理3. Cache和主存之間的映射方式4.

11、Cache中主存塊的替換算法5. Cache寫策略四、 指令系統(tǒng)（一） 指令格式1. 指令的基本格式2. 定長操作碼指令格式3. 擴(kuò)展操作碼指令格式（二） 指令的尋址方式1. 有效地址的概念2. 數(shù)據(jù)尋址和指令尋址3. 常見尋址方式（三） CISC和RISC的基本概念五、 中央處理器（CPU）（一） CPU的功能和基本結(jié)構(gòu)（二） 指令執(zhí)行過程（三） 數(shù)據(jù)通路的功能和基本結(jié)構(gòu)（四） 控制器的功能和工作原理1. 組合邏輯控制器2. 微程序控制器微程序、微指令和微命令；微指令的編碼方式；微地址的形式方式。（五） 指令流水線1. 指令流水線的基本概念2. 超標(biāo)量和動態(tài)流水線的基本概念六、 總線（一） 總線概述1. 總線的基本概念2. 總線的分類3. 總線的組成及性能指標(biāo)（二） 總線仲裁1. 集中仲裁方式2. 分布仲裁方式（三） 總線操作和定時1. 同步定時方式2. 異步定時方式（四） 總線標(biāo)準(zhǔn)七、 輸入輸出（I/O）系統(tǒng)（一） I/O系統(tǒng)基本概念（二） 外部設(shè)備1. 輸入設(shè)備：鍵盤、鼠標(biāo)2. 輸出設(shè)備：顯示器、打印機(jī)3. 外存儲器：硬盤存儲器、光盤存儲器（三） I/O接口（I/O控制器）1. I/O接口的功能和基本結(jié)構(gòu)2. I/O端口及其編址（四） I/O方式