828《數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)》復(fù)習(xí)大綱

一、考試的基本要求

要求考生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本知識(shí)，從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的操作三個(gè)方面掌握線性表、樹(shù)、圖等常用的數(shù)據(jù)結(jié)構(gòu)。掌握在各種常用數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高效的查找和排序算法，并對(duì)算法的時(shí)間和空間復(fù)雜性有一定的分析能力。針對(duì)簡(jiǎn)單的應(yīng)用問(wèn)題，能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)有效的算法。

另一方面，要求考生比較系統(tǒng)地掌握操作系統(tǒng)各要素的基本概念、基本原理和方法，對(duì)操作系統(tǒng)如何管理和控制計(jì)算機(jī)系統(tǒng)的所有硬件和軟件資源以達(dá)到方便用戶、提高資源的使用效率有較深入的了解。

要求考生具有較強(qiáng)的抽象思維能力、邏輯推理能力、軟件設(shè)計(jì)和實(shí)現(xiàn)能力以及綜合運(yùn)用所學(xué)的知識(shí)分析問(wèn)題和解決問(wèn)題的能力。

二、考試方式和考試時(shí)間

閉卷考試，總分150（數(shù)據(jù)結(jié)構(gòu)90+操作系統(tǒng)60），考試時(shí)間為3小時(shí)。

三、參考書目（僅供參考）

《數(shù)據(jù)結(jié)構(gòu)與算法》（第四版），廖明宏，郭福順，張巖，李秀坤，高等教育出版社，2007年

《計(jì)算機(jī)操作系統(tǒng)》(第三版)，湯小丹，梁紅兵，哲鳳屏，湯子瀛，西安電子科技大學(xué)出版社，2007年

四、試題類型：

主要包括選擇題 、編程題、計(jì)算題、綜合題等類型，并根據(jù)每年的考試要求做相應(yīng)調(diào)整。

五、考試內(nèi)容及要求

第一部分 數(shù)據(jù)結(jié)構(gòu)-線性表

掌握：線性表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及描述方式；順序表的定義、插入、刪除；單鏈表、雙向鏈表和循環(huán)鏈表的定義、插入、刪除；順序棧、鏈棧的表示、入棧和出棧操作；順序隊(duì)列、鏈隊(duì)列的表示、入隊(duì)和出隊(duì)操作；循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷；串的定義、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，串的KMP模式匹配方法；廣義表的定義；矩陣的壓縮存儲(chǔ)的概念以及有關(guān)計(jì)算方法；稀疏矩陣的三元組表示方法；

熟悉：線性結(jié)構(gòu)的定義和特點(diǎn)；順序表和單鏈表的組織方法、特點(diǎn)、算法和性能分析；單鏈表、雙向鏈表和循環(huán)鏈表之間的區(qū)別；棧和隊(duì)的特點(diǎn)；棧和隊(duì)列的定義；順序棧和鏈棧上基本運(yùn)算的實(shí)現(xiàn)和簡(jiǎn)單算法設(shè)計(jì)；鏈隊(duì)上基本運(yùn)算的實(shí)現(xiàn)和簡(jiǎn)單算法設(shè)計(jì)；串的基本運(yùn)算，串的傳統(tǒng)匹配方法；多維數(shù)組的定義以及邏輯結(jié)構(gòu)；廣義表的鏈表表示和算法；特殊矩陣的非零元下標(biāo)與數(shù)組下標(biāo)的對(duì)應(yīng)關(guān)系。

第二部分 數(shù)據(jù)結(jié)構(gòu)-樹(shù)

掌握：樹(shù)的邏輯結(jié)構(gòu)；二叉樹(shù)的定義以及性質(zhì)；二叉樹(shù)的不同表示方法；二叉樹(shù)的構(gòu)建方法；二叉樹(shù)的三種遍歷算法；線索二叉樹(shù)的定義及構(gòu)造方法；樹(shù)的存儲(chǔ)結(jié)構(gòu)；哈夫曼樹(shù)的構(gòu)建及其應(yīng)用，哈夫曼編碼；表達(dá)式樹(shù)的構(gòu)建及其應(yīng)用；集合樹(shù)的表示以及集合等價(jià)分類算法；

熟悉：樹(shù)的常用術(shù)語(yǔ)和含義；二叉樹(shù)性質(zhì)的證明；利用二叉樹(shù)的遍歷設(shè)計(jì)有關(guān)算法解決簡(jiǎn)單應(yīng)用問(wèn)題；線索二叉樹(shù)的插入、刪除結(jié)點(diǎn)算法，利用線索二叉樹(shù)確定結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)；森林與二叉樹(shù)的轉(zhuǎn)換；利用表達(dá)式樹(shù)求表達(dá)式的值。

第三部分 數(shù)據(jù)結(jié)構(gòu)-圖

掌握：圖的邏輯結(jié)構(gòu)特征；圖的兩種表示方法；圖的深度優(yōu)先搜索的算法及實(shí)現(xiàn)；最小生成樹(shù)的概念，用Prim算法和Kruskal算法構(gòu)造連通圖的最小生成樹(shù)的方法和復(fù)雜度；對(duì)給定的有向圖，給出其中一個(gè)拓?fù)渑判颍籄OE網(wǎng)的基本原理和實(shí)現(xiàn)方法；單源最短路徑Dijkstra算法的基本思想和性能分析；

熟悉：圖的定義和術(shù)語(yǔ)；圖的廣度優(yōu)先搜索的算法及實(shí)現(xiàn)；圖的遍歷和樹(shù)的遍歷之間的關(guān)系；生成樹(shù)概念，用兩種方法構(gòu)建最小生成樹(shù)的實(shí)現(xiàn)；拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)；單源最短路徑的實(shí)現(xiàn)方法；Floyd算法的基本思想和性能分析；Warshall的算法實(shí)質(zhì)；利用Floyd算法求有向圖的中心點(diǎn)。

第四部分 數(shù)據(jù)結(jié)構(gòu)-查找和排序

掌握：二分查找的基本條件和方法；分塊查找的基本思想和性能分析；二分查找和分塊查找的實(shí)現(xiàn)方法；二叉查找樹(shù)和平衡二叉樹(shù)的構(gòu)建、插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)的方法；哈希表技術(shù)的相關(guān)概念、哈希函數(shù)的構(gòu)造方法和原則以及產(chǎn)生沖突的原因；插入排序、選擇排序、冒泡排序、快速排序、堆排序、歸并排序、基數(shù)排序基本原理和性能分析；快速排序、歸并排序的算法實(shí)現(xiàn)；

熟悉：順序查找、二分查找和分塊查找、二叉排序樹(shù)和平衡二叉樹(shù)、哈希查找的概念、性質(zhì)及性能；順序查找、二叉排序樹(shù)的實(shí)現(xiàn)方法；哈希函數(shù)的構(gòu)造方法和處理沖突的方法；插入排序、希爾排序、快速排序、簡(jiǎn)單選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想；希爾排序、基數(shù)排序的實(shí)現(xiàn)方法；排序算法的穩(wěn)定性分析。

第五部分 操作系統(tǒng)-進(jìn)程管理

掌握：進(jìn)程的基本概念；進(jìn)程的特征與狀態(tài)；進(jìn)程的創(chuàng)建、終止、堵塞與喚醒、掛起與激活；進(jìn)程的同步；幾個(gè)經(jīng)典的進(jìn)程同步問(wèn)題；消息緩沖隊(duì)列通信機(jī)制；線程的同步與通信；

熟悉：程序順序執(zhí)行及其特征；程序并發(fā)執(zhí)行及其特征；進(jìn)程控制塊；進(jìn)程通信類型；消息傳遞通信的實(shí)現(xiàn)方法。

第六部分 操作系統(tǒng)-處理機(jī)調(diào)度與死鎖

掌握：調(diào)度隊(duì)列模型以及選擇調(diào)度算法的若干準(zhǔn)則；高優(yōu)先權(quán)優(yōu)先調(diào)度算法、時(shí)間片輪轉(zhuǎn)調(diào)度算法、最高響應(yīng)比調(diào)度算法；利用銀行家算法避免死鎖；死鎖的檢測(cè)與解除；

熟悉：處理機(jī)調(diào)度的基本概念；先來(lái)先服務(wù)調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法；產(chǎn)生死鎖的原因和必要條件；系統(tǒng)安全狀態(tài)。

第七部分 操作系統(tǒng)-存儲(chǔ)器管理

掌握：程序的裝入和連接；頁(yè)面與頁(yè)表；地址變換機(jī)構(gòu)；兩級(jí)和多級(jí)頁(yè)表；段頁(yè)式存儲(chǔ)管理方式；虛擬存儲(chǔ)器的特征；請(qǐng)求分頁(yè)存儲(chǔ)管理中的內(nèi)存分配策略、分配算法和調(diào)頁(yè)策略；最佳置換算法和FIFO算法LRU置換算法；Clock置換算法；

熟悉：存儲(chǔ)器的層次結(jié)構(gòu)；連續(xù)分配方式：固定分區(qū)、動(dòng)態(tài)分區(qū)、可重定位分區(qū)、對(duì)換；反向頁(yè)表；分段存儲(chǔ)的基本原理；信息共享；虛擬存儲(chǔ)器的實(shí)現(xiàn)方法；請(qǐng)求分頁(yè)中的硬件支持；請(qǐng)求分段中的硬件支持；分段的共享與保護(hù)。

第八部分 操作系統(tǒng)-設(shè)備管理

掌握： 程序I/O方式；中斷驅(qū)動(dòng)I/O控制方法；DMA I/O控制方法；循環(huán)緩沖、緩沖池；中斷驅(qū)動(dòng)程序；設(shè)備驅(qū)動(dòng)程序；獨(dú)立型設(shè)備的分配與去配；共享型設(shè)備的分配與去配；磁盤高速緩存；提高磁盤I/O速度的其它方法；

熟悉：I/O設(shè)備；總線系統(tǒng)； I/O通道控制方法；I/O軟件的設(shè)計(jì)目標(biāo)與原則；設(shè)備獨(dú)立性軟件；用戶層軟件；設(shè)備分配的相關(guān)數(shù)據(jù)結(jié)構(gòu)；磁盤調(diào)度；廉價(jià)磁盤冗陣列。

第九部分 操作系統(tǒng)-文件管理與接口命令

掌握：索引文件、索引順序文件、直接文件和哈希文件；連續(xù)分配、鏈接分派、索引分配；文件存儲(chǔ)的空閑表法、空閑鏈表發(fā)、位示圖法、成組鏈接法；基于索引結(jié)點(diǎn)的共享方式、利用符號(hào)鏈實(shí)現(xiàn)文件共享；數(shù)據(jù)一致性控制；Shell命令語(yǔ)言；

熟悉： 文件、記錄和數(shù)據(jù)項(xiàng)的基本概念；文件類型和文件系統(tǒng)模型；文件的基本操作；文件邏輯結(jié)構(gòu)的類型；順序文件；文件控制塊與索引結(jié)點(diǎn)、目錄結(jié)構(gòu)、目錄查詢技術(shù)；重復(fù)數(shù)據(jù)的數(shù)據(jù)一致性問(wèn)題；聯(lián)機(jī)用戶接口、聯(lián)機(jī)命令類型、鍵盤終端處理程序；系統(tǒng)調(diào)用概念及基本類型；圖像界面接口。

更多學(xué)歷考試信息請(qǐng)查看學(xué)歷考試網(wǎng)