|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
1
828《數據結構與操作系統》復習大綱
一、考試的基本要求
要求考生比較系統地理解數據結構的基本概念和基本知識，從數據結構的邏
輯結構、存儲結構和數據的操作三個方面掌握線性表、樹、圖等常用的數據結構。
掌握在各種常用數據結構上實現高效的查找和排序算法，并對算法的時間和空間
復雜性有一定的分析能力。針對簡單的應用問題，能夠選擇合適的數據結構設計
有效的算法。
另一方面，要求考生比較系統地掌握操作系統各要素的基本概念、基本原理
和方法，對操作系統如何管理和控制計算機系統的所有硬件和軟件資源以達到方
便用戶、提高資源的使用效率有較深入的了解。
要求考生具有較強的抽象思維能力、邏輯推理能力、軟件設計和實現能力以
及綜合運用所學的知識分析問題和解決問題的能力。
二、考試方式和考試時間
閉卷考試，總分 150（數據結構 90+操作系統 60），考試時間為 3 小時。
三、參考書目（僅供參考）
《數據結構與算法》（第四版），廖明宏，郭福順，張巖，李秀坤，高等教育
出版社，2007 年
《計算機操作系統》(第三版)，湯小丹，梁紅兵，哲鳳屏，湯子瀛，西安電
子科技大學出版社，2007 年
四、試題類型：
主要包括選擇題 、編程題、計算題、綜合題等類型，并根據每年的考試要
求做相應調整。
五、考試內容及要求
第一部分 數據結構-線性表
掌握：線性表的邏輯結構、存儲結構及描述方式；順序表的定義、插入、刪
除；單鏈表、雙向鏈表和循環鏈表的定義、插入、刪除；順序棧、鏈棧的表示、
入棧和出棧操作；順序隊列、鏈隊列的表示、入隊和出隊操作；循環隊列的隊空
和隊滿的判斷；串的定義、邏輯結構和存儲結構，串的 KMP 模式匹配方法；廣義
2
表的定義；矩陣的壓縮存儲的概念以及有關計算方法；稀疏矩陣的三元組表示方
法；
熟悉：線性結構的定義和特點；順序表和單鏈表的組織方法、特點、算法和
性能分析；單鏈表、雙向鏈表和循環鏈表之間的區別；棧和隊的特點；棧和隊列
的定義；順序棧和鏈棧上基本運算的實現和簡單算法設計；鏈隊上基本運算的實
現和簡單算法設計；串的基本運算，串的傳統匹配方法；多維數組的定義以及邏
輯結構；廣義表的鏈表表示和算法；特殊矩陣的非零元下標與數組下標的對應關
系。
第二部分 數據結構-樹
掌握：樹的邏輯結構；二叉樹的定義以及性質；二叉樹的不同表示方法；二
叉樹的構建方法；二叉樹的三種遍歷算法；線索二叉樹的定義及構造方法；樹的
存儲結構；哈夫曼樹的構建及其應用，哈夫曼編碼；表達式樹的構建及其應用；
集合樹的表示以及集合等價分類算法；
熟悉：樹的常用術語和含義；二叉樹性質的證明；利用二叉樹的遍歷設計有
關算法解決簡單應用問題；線索二叉樹的插入、刪除結點算法，利用線索二叉樹
確定結點的前驅和后繼結點；森林與二叉樹的轉換；利用表達式樹求表達式的值。
第三部分 數據結構-圖
掌握：圖的邏輯結構特征；圖的兩種表示方法；圖的深度優先搜索的算法及
實現；最小生成樹的概念，用 Prim 算法和 Kruskal 算法構造連通圖的最小生成
樹的方法和復雜度；對給定的有向圖，給出其中一個拓撲排序；AOE 網的基本原
理和實現方法；單源最短路徑 Dijkstra 算法的基本思想和性能分析；
熟悉：圖的定義和術語；圖的廣度優先搜索的算法及實現；圖的遍歷和樹的
遍歷之間的關系；生成樹概念，用兩種方法構建最小生成樹的實現；拓撲排序算
法的實現；單源最短路徑的實現方法；Floyd 算法的基本思想和性能分析；
Warshall 的算法實質；利用 Floyd 算法求有向圖的中心點。
第四部分 數據結構-查找和排序
掌握：二分查找的基本條件和方法；分塊查找的基本思想和性能分析；二分
查找和分塊查找的實現方法；二叉查找樹和平衡二叉樹的構建、插入結點和刪除
結點的方法；哈希表技術的相關概念、哈希函數的構造方法和原則以及產生沖突
3
的原因；插入排序、選擇排序、冒泡排序、快速排序、堆排序、歸并排序、基數
排序基本原理和性能分析；快速排序、歸并排序的算法實現；
熟悉：順序查找、二分查找和分塊查找、二叉排序樹和平衡二叉樹、哈希查
找的概念、性質及性能；順序查找、二叉排序樹的實現方法；哈希函數的構造方
法和處理沖突的方法；插入排序、希爾排序、快速排序、簡單選擇排序、堆排序、
歸并排序和基數排序的基本思想；希爾排序、基數排序的實現方法；排序算法的
穩定性分析。
第五部分 操作系統-進程管理
掌握：進程的基本概念；進程的特征與狀態；進程的創建、終止、堵塞與喚
醒、掛起與激活；進程的同步；幾個經典的進程同步問題；消息緩沖隊列通信機
制；線程的同步與通信；
熟悉：程序順序執行及其特征；程序并發執行及其特征；進程控制塊；進程
通信類型；消息傳遞通信的實現方法。
第六部分 操作系統-處理機調度與死鎖
掌握：調度隊列模型以及選擇調度算法的若干準則；高優先權優先調度算法、
時間片輪轉調度算法、最高響應比調度算法；利用銀行家算法避免死鎖；死鎖的
檢測與解除；
熟悉：處理機調度的基本概念；先來先服務調度算法、短作業優先調度算法；
產生死鎖的原因和必要條件；系統安全狀態。
第七部分 操作系統-存儲器管理
掌握：程序的裝入和連接；頁面與頁表；地址變換機構；兩級和多級頁表；
段頁式存儲管理方式；虛擬存儲器的特征；請求分頁存儲管理中的內存分配策略、
分配算法和調頁策略；最佳置換算法和 FIFO 算法 LRU 置換算法；Clock 置換算
法；
熟悉：存儲器的層次結構；連續分配方式：固定分區、動態分區、可重定位
分區、對換；反向頁表；分段存儲的基本原理；信息共享；虛擬存儲器的實現方
法；請求分頁中的硬件支持；請求分段中的硬件支持；分段的共享與保護。
第八部分 操作系統-設備管理
掌握： 程序 I/O 方式；中斷驅動 I/O 控制方法；DMA I/O 控制方法；循環
4
緩沖、緩沖池；中斷驅動程序；設備驅動程序；獨立型設備的分配與去配；共享
型設備的分配與去配；磁盤高速緩存；提高磁盤 I/O 速度的其它方法；
熟悉：I/O 設備；總線系統； I/O 通道控制方法；I/O 軟件的設計目標與原
則；設備獨立性軟件；用戶層軟件；設備分配的相關數據結構；磁盤調度；廉價
磁盤冗陣列。
第九部分 操作系統-文件管理與接口命令
掌握：索引文件、索引順序文件、直接文件和哈希文件；連續分配、鏈接分
派、索引分配；文件存儲的空閑表法、空閑鏈表發、位示圖法、成組鏈接法；基
于索引結點的共享方式、利用符號鏈實現文件共享；數據一致性控制；Shell 命
令語言；
熟悉： 文件、記錄和數據項的基本概念；文件類型和文件系統模型；文件
的基本操作；文件邏輯結構的類型；順序文件；文件控制塊與索引結點、目錄結
構、目錄查詢技術；重復數據的數據一致性問題；聯機用戶接口、聯機命令類型、
鍵盤終端處理程序；系統調用概念及基本類型；圖像界面接口。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
