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

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

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ù)據(jù)結(jié)構(gòu)。掌握在各種常用數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高效的查找和排序算法，并對(duì)算法的時(shí)間和空間復(fù)雜性有一定的分析能力。針對(duì)簡(jiǎn)單的應(yīng)用問題，能夠選擇合適的數(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í)分析問題和解決問題的能力。

二、考試方式和考試時(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)-樹

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

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

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

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

熟悉：圖的定義和術(shù)語;圖的廣度優(yōu)先搜索的算法及實(shí)現(xiàn);圖的遍歷和樹的遍歷之間的關(guān)系;生成樹概念，用兩種方法構(gòu)建最小生成樹的實(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)方法;二叉查找樹和平衡二叉樹的構(gòu)建、插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)的方法;哈希表技術(shù)的相關(guān)概念、哈希函數(shù)的構(gòu)造方法和原則以及產(chǎn)生沖突的原因;插入排序、選擇排序、冒泡排序、快速排序、堆排序、歸并排序、基數(shù)排序基本原理和性能分析;快速排序、歸并排序的算法實(shí)現(xiàn);

熟悉：順序查找、二分查找和分塊查找、二叉排序樹和平衡二叉樹、哈希查找的概念、性質(zhì)及性能;順序查找、二叉排序樹的實(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)程同步問題;消息緩沖隊(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)度的基本概念;先來先服務(wù)調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法;產(chǎn)生死鎖的原因和必要條件;系統(tǒng)安全狀態(tài)。

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

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

熟悉：存儲(chǔ)器的層次結(jié)構(gòu);連續(xù)分配方式：固定分區(qū)、動(dòng)態(tài)分區(qū)、可重定位分區(qū)、對(duì)換;反向頁表;分段存儲(chǔ)的基本原理;信息共享;虛擬存儲(chǔ)器的實(shí)現(xiàn)方法;請(qǐng)求分頁中的硬件支持;請(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命令語言;

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