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

一、考試的基本要求

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

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

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

二、考試方式和考試時間

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

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

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

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

四、試題類型：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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