2019年南京工業(yè)大學(xué)828數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研大綱

• 2025考研復(fù)試伴學(xué)班
• 2025考研復(fù)試標準班
• 2026考研英語全程班
• 26考研全科上岸規(guī)劃營「擇校▪規(guī)劃▪備考」
• 南京工業(yè)大學(xué)2025考研專業(yè)課復(fù)習(xí)資料「真題▪筆記▪講義▪題庫」

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);廣義表的鏈表表示和算法;特殊矩陣的非零元下標與數(shù)組下標的對應(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ù)雜度;對給定的有向圖，給出其中一個拓撲排序;AOE網(wǎng)的基本原理和實現(xiàn)方法;單源最短路徑Dijkstra算法的基本思想和性能分析;

熟悉：圖的定義和術(shù)語;圖的廣度優(yōu)先搜索的算法及實現(xiàn);圖的遍歷和樹的遍歷之間的關(guān)系;生成樹概念，用兩種方法構(gòu)建最小生成樹的實現(xiàn);拓撲排序算法的實現(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)度算法的若干準則;高優(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è)計目標與原則;設(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)用概念及基本類型;圖像界面接口。