2019年南京工業大學828數據結構與操作系統考研大綱

考研專業課大綱來源：中國考研網 2018-11-23　相關院校：南京工業大學

828《數據結構與操作系統》復習大綱

一、考試的基本要求

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

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

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

二、考試方式和考試時間

閉卷考試，總分150(數據結構90+操作系統60)，考試時間為3小時。

三、參考書目(僅供參考)

《數據結構與算法》(第四版)，廖明宏，郭福順，張巖，李秀坤，高等教育出版社，2007年

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

四、試題類型：

主要包括選擇題、編程題、計算題、綜合題等類型，并根據每年的考試要求做相應調整。

五、考試內容及要求

第一部分數據結構-線性表

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

熟悉：線性結構的定義和特點;順序表和單鏈表的組織方法、特點、算法和性能分析;單鏈表、雙向鏈表和循環鏈表之間的區別;棧和隊的特點;棧和隊列的定義;順序棧和鏈棧上基本運算的實現和簡單算法設計;鏈隊上基本運算的實現和簡單算法設計;串的基本運算，串的傳統匹配方法;多維數組的定義以及邏輯結構;廣義表的鏈表表示和算法;特殊矩陣的非零元下標與數組下標的對應關系。

第二部分數據結構-樹

掌握：樹的邏輯結構;二叉樹的定義以及性質;二叉樹的不同表示方法;二叉樹的構建方法;二叉樹的三種遍歷算法;線索二叉樹的定義及構造方法;樹的存儲結構;哈夫曼樹的構建及其應用，哈夫曼編碼;表達式樹的構建及其應用;集合樹的表示以及集合等價分類算法;

熟悉：樹的常用術語和含義;二叉樹性質的證明;利用二叉樹的遍歷設計有關算法解決簡單應用問題;線索二叉樹的插入、刪除結點算法，利用線索二叉樹確定結點的前驅和后繼結點;森林與二叉樹的轉換;利用表達式樹求表達式的值。

第三部分數據結構-圖

掌握：圖的邏輯結構特征;圖的兩種表示方法;圖的深度優先搜索的算法及實現;最小生成樹的概念，用Prim算法和Kruskal算法構造連通圖的最小生成樹的方法和復雜度;對給定的有向圖，給出其中一個拓撲排序;AOE網的基本原理和實現方法;單源最短路徑Dijkstra算法的基本思想和性能分析;

熟悉：圖的定義和術語;圖的廣度優先搜索的算法及實現;圖的遍歷和樹的遍歷之間的關系;生成樹概念，用兩種方法構建最小生成樹的實現;拓撲排序算法的實現;單源最短路徑的實現方法;Floyd算法的基本思想和性能分析;Warshall的算法實質;利用Floyd算法求有向圖的中心點。

第四部分數據結構-查找和排序

掌握：二分查找的基本條件和方法;分塊查找的基本思想和性能分析;二分查找和分塊查找的實現方法;二叉查找樹和平衡二叉樹的構建、插入結點和刪除結點的方法;哈希表技術的相關概念、哈希函數的構造方法和原則以及產生沖突的原因;插入排序、選擇排序、冒泡排序、快速排序、堆排序、歸并排序、基數排序基本原理和性能分析;快速排序、歸并排序的算法實現;

熟悉：順序查找、二分查找和分塊查找、二叉排序樹和平衡二叉樹、哈希查找的概念、性質及性能;順序查找、二叉排序樹的實現方法;哈希函數的構造方法和處理沖突的方法;插入排序、希爾排序、快速排序、簡單選擇排序、堆排序、歸并排序和基數排序的基本思想;希爾排序、基數排序的實現方法;排序算法的穩定性分析。

第五部分操作系統-進程管理

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

熟悉：程序順序執行及其特征;程序并發執行及其特征;進程控制塊;進程通信類型;消息傳遞通信的實現方法。

第六部分操作系統-處理機調度與死鎖

掌握：調度隊列模型以及選擇調度算法的若干準則;高優先權優先調度算法、時間片輪轉調度算法、最高響應比調度算法;利用銀行家算法避免死鎖;死鎖的檢測與解除;

熟悉：處理機調度的基本概念;先來先服務調度算法、短作業優先調度算法;產生死鎖的原因和必要條件;系統安全狀態。

第七部分操作系統-存儲器管理

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

熟悉：存儲器的層次結構;連續分配方式：固定分區、動態分區、可重定位分區、對換;反向頁表;分段存儲的基本原理;信息共享;虛擬存儲器的實現方法;請求分頁中的硬件支持;請求分段中的硬件支持;分段的共享與保護。

第八部分操作系統-設備管理

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