851計(jì)算機(jī)基礎(chǔ)綜合考試大綱5頁(yè)

1、851計(jì)算機(jī)基礎(chǔ)綜合考試大綱I數(shù)據(jù)結(jié)構(gòu)1. 鏈表、間接尋址和模擬指針2數(shù)組和矩陣3堆棧和隊(duì)列及其應(yīng)用4跳表和散列5二叉樹(shù)和其他樹(shù)6合并/搜索應(yīng)用，堆和堆排序7左高樹(shù)，霍夫曼編碼和競(jìng)賽樹(shù)8搜索樹(shù)，AVL樹(shù)或紅黑樹(shù)，直方圖9圖10圖和貪婪算法11貨箱裝載，0/1背包，最短路徑和生成樹(shù)12分而治之算法13動(dòng)態(tài)編程14回溯和分枝定界算法II操作系統(tǒng)一、導(dǎo)論操作系統(tǒng)的概念計(jì)算機(jī)系統(tǒng)的操作、存儲(chǔ)結(jié)構(gòu)、輸入輸出結(jié)構(gòu)和計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)操作系統(tǒng)的結(jié)構(gòu)組成、操作系統(tǒng)的操作及各部分的功能、高速緩沖存儲(chǔ)器CACHE操作系統(tǒng)的分類和運(yùn)行環(huán)境二、操作系統(tǒng)結(jié)構(gòu)操作系統(tǒng)提供的服務(wù)類型操作系統(tǒng)的用戶接口類型系統(tǒng)調(diào)用及類型操

2、作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)方法操作系統(tǒng)的結(jié)構(gòu)分類及優(yōu)缺點(diǎn)虛擬機(jī)的基本概念和原理三、進(jìn)程進(jìn)程的概念、組織、控制和狀態(tài)轉(zhuǎn)換進(jìn)程調(diào)度的基本概念進(jìn)程的操作，包括進(jìn)程的生成、終止等進(jìn)程通信四、線程線程的概念與動(dòng)機(jī)多線程模型五、CPU調(diào)度調(diào)度的基本概念調(diào)度的時(shí)機(jī)、切換和過(guò)程調(diào)度的基本準(zhǔn)則典型調(diào)度方法：先來(lái)先服務(wù)調(diào)度算法、最短作業(yè)優(yōu)先調(diào)度算法、優(yōu)先級(jí)調(diào)度算法、時(shí)間片輪轉(zhuǎn)調(diào)度算法、多級(jí)隊(duì)列調(diào)度算法、多級(jí)反饋隊(duì)列調(diào)度算法線程調(diào)度調(diào)度算法的性能評(píng)估六、進(jìn)程同步進(jìn)程同步的基本概念臨界區(qū)訪問(wèn)的原則及實(shí)現(xiàn)臨界區(qū)互斥的基本方法：軟件實(shí)現(xiàn)方法和硬件實(shí)現(xiàn)方法信號(hào)量概念與基本機(jī)制經(jīng)典同步問(wèn)題：生產(chǎn)者消費(fèi)者問(wèn)題、讀者寫(xiě)者問(wèn)題、哲學(xué)家就餐

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

4、索能力、逆向頁(yè)表等十、文件系統(tǒng)接口文件的基本概念文件的結(jié)構(gòu)：順序文件、索引文件等文件的訪問(wèn)方法目錄結(jié)構(gòu)：文件的存儲(chǔ)結(jié)構(gòu)、單級(jí)目錄結(jié)構(gòu)、兩級(jí)目錄結(jié)構(gòu)、樹(shù)形目錄結(jié)構(gòu)、無(wú)環(huán)圖目錄結(jié)構(gòu)、通用圖目錄結(jié)構(gòu)文件共享十一、文件系統(tǒng)實(shí)現(xiàn)文件系統(tǒng)的結(jié)構(gòu)文件系統(tǒng)的實(shí)現(xiàn)目錄的實(shí)現(xiàn)文件的磁盤空間分配方法：連續(xù)、鏈?zhǔn)健⑺饕臻e空間的管理十二、大容量存儲(chǔ)磁盤的結(jié)構(gòu)磁盤的調(diào)度方法：先到先服務(wù)調(diào)度算法、最短尋道時(shí)間調(diào)度算法、SCAN調(diào)度算法、CSCAN調(diào)度算法、LOOK調(diào)度算法、CLOOK調(diào)度算法磁盤管理：格式化、引導(dǎo)塊、壞塊的處理RAID結(jié)構(gòu)十三、輸入/輸出系統(tǒng)輸入/輸出硬件輸入/輸出訪問(wèn)控制方式輸入/輸出應(yīng)用接口內(nèi)核輸入/

5、輸出子系統(tǒng)：輸入/輸出調(diào)度、緩存、緩沖、假脫機(jī)與設(shè)備預(yù)留、錯(cuò)誤處理、輸入/輸出保護(hù)、內(nèi)核數(shù)據(jù)結(jié)構(gòu)輸入/輸出從請(qǐng)求到硬件操作的轉(zhuǎn)換過(guò)程十四、保護(hù)保護(hù)的目標(biāo)與原則保護(hù)域訪問(wèn)矩陣及實(shí)現(xiàn)方法：全局表、訪問(wèn)列表、能力表十五、安全系統(tǒng)中存在的安全問(wèn)題以及安全措施的級(jí)別程序的威脅：木馬、后門、邏輯炸彈、棧與緩沖溢出、病毒系統(tǒng)與網(wǎng)絡(luò)威脅：蠕蟲(chóng)、端口掃描、DoSIII計(jì)算機(jī)組成原理計(jì)算機(jī)系統(tǒng)概述計(jì)算機(jī)發(fā)展歷程計(jì)算機(jī)系統(tǒng)層次結(jié)構(gòu)計(jì)算機(jī)硬件的基本組成計(jì)算機(jī)軟件的分類計(jì)算機(jī)的工作過(guò)程計(jì)算機(jī)性能指標(biāo)吞吐量、響應(yīng)時(shí)間；CPU時(shí)鐘周期、主頻、CPI、CPU執(zhí)行時(shí)間；MIPS、MFLOPS。數(shù)據(jù)的表示和運(yùn)算數(shù)制與編碼進(jìn)位計(jì)數(shù)

6、制及其相互轉(zhuǎn)換真值和機(jī)器數(shù)BCD碼字符與字符串校驗(yàn)碼定點(diǎn)數(shù)的表示和運(yùn)算定點(diǎn)數(shù)的表示無(wú)符號(hào)數(shù)的表示；有符號(hào)數(shù)的表示。定點(diǎn)數(shù)的運(yùn)算定點(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ù)的表示浮點(diǎn)數(shù)的表示范圍浮點(diǎn)數(shù)的加/減運(yùn)算算術(shù)邏輯單元ALU串行加法器和并行加法器算術(shù)邏輯單元ALU的功能和機(jī)構(gòu)存儲(chǔ)器層次機(jī)構(gòu)存儲(chǔ)器的分類存儲(chǔ)器的層次化結(jié)構(gòu)半導(dǎo)體隨機(jī)存取存儲(chǔ)器SRAM存儲(chǔ)器的工作原理DRAM存儲(chǔ)器的工作原理只讀存儲(chǔ)器Flash存儲(chǔ)器主存儲(chǔ)器與CPU的連接雙口RAM和多模塊存儲(chǔ)器高速緩沖存儲(chǔ)器（Cache）程序訪問(wèn)的局部Cach

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