《數據結構及操作系統》考試大綱

命題方式  招生單位自命題  科目類別  初試
滿分  150
考試性質
《數據結構及操作系統》課程主要包含數據結構和操作系統兩塊內容。該課程的考試是為招收工學類碩士研究生而設置的選拔考試。它的主要目的是測試考生對該課程的把握程度，包括對課程中的概念、基本原理和方法的理解和掌握，及能夠運用所學的原理和方法分析、判斷及解決有關理論問題和實際問題。
考試方式和考試時間
考試采用閉卷筆試形式，試卷滿分為150分（數據結構和操作系統各占75分），考試時間為3小時。
考試內容和考試要求
一、數據結構
（一）數據結構概論
考試內容：
1． 概念：數據結構，數據元素，數據項，數據的四種經典邏輯結構，數據的物理存儲結構，數據結構研究的三個方向，算法，算法的時間復雜度、空間復雜度
2． 理解和應用：
（1）數據的四種經典邏輯結構之間的區別和聯系
（2）算法的特性和設計的要求
（3）時間復雜度和空間復雜度的關系
考試要求
（1）掌握基本概念
（2）能計算出給定程序的時間復雜度

（二）線性結構
考試內容：
1. 概念：線性結構的特點，線性表，線性表的順序存儲特點，順序表中元素存儲位置之間的關系，線性鏈表， 循環鏈表，雙向鏈表，棧，隊列，循環隊列，串，子串，模式匹配算法
2.  理解與應用：
（1） 線性表、棧、隊列與線性結構的關系
（2） 線性表的順序存儲結構表示
（3） 順序表中的插入、刪除、合并操作算法的思想及實現方法
（4）線性表的鏈式存儲結構表示
（5）單鏈表的創建、查找、插入、刪除、合并算法的思想及實現方法
（6）雙向鏈表的插入和刪除算法的思想及實現
（7）棧中棧頂、棧底的含義，棧中元素操作的特點
（8）棧頂指針的作用及意義
（9）棧的進棧、出棧算法的思想及實現方法
（10）棧的應用
（11）隊列中隊頭、隊尾的含義，隊列的基本特點
（12）循環隊列的設計思路及實現方法
（13）隊列的入隊列、出隊列算法的思想及實現方法
（14）子串的位置及模式匹配
（15）子串的定位算法及KMP算法
考試要求：
（1）掌握基本概念
（2）對算法的思想能進行文字描述
（3）了解棧與隊列的操作特點

（三）樹
考試內容：
1. 概念：樹，子樹，二叉樹，結點的度，分支結點，雙親、兄弟、堂兄、祖先、子孫結點，樹的深度，無序樹，有序樹，森林，滿二叉樹，完全二叉樹，線索二叉樹，最優二叉樹，樹的帶權路徑長度
2. 理解與應用
（1）二叉樹的性質
（2）滿二叉樹與完全二叉樹的區別與聯系
（3）二叉樹的存儲結構及實現
（4）二叉樹的三種遍歷算法的思想及實現方法
（5）二叉樹的線索過程
（6）樹的存儲結構及表示
（7）樹、二叉樹、森林間的相互轉換
（8）樹、森林的遍歷與二叉樹的遍歷之間的聯系
（9）線索二叉樹的存儲結構
（10）二叉樹的線索化算法
（11）赫夫曼樹的構造算法及實現方法
考試要求：
（1）掌握基本概念
（2）掌握算法的思想，能對算法代碼實現
（3）了解樹、二叉樹、森林的存儲結構、遍歷關系

（四）圖
考試內容：
1. 概念：圖，頂點，弧，有向圖，無向圖，完全圖，子圖，頂點的度，路徑，簡單路徑，回路，連通圖，連通分量，強連通圖，強連通分量，生成樹，生成森林 ，有向無環圖，拓撲排序，關鍵路徑，AOV網，AOE網，最短路徑
2. 理解與應用：
（1）圖的特點
（2）圖的存儲結構及實現
（3）圖的遍歷算法思想及實現方法
（4）圖的最小生成樹構造算法思想及實現方法
（5）拓撲排序算法的思想及實現方法
（6）最短路徑的構造算法
考試要求：
（1）掌握基本概念
（2）掌握算法的思想，能對算法代碼實現
（3）了解各種算法的應用范圍和解決的實際問題

（五）查找
考試內容：
1. 概念：查找表，關鍵字，靜態查找，動態查找，平均查找長度，二叉排序樹，平衡因子，平衡二叉樹，B-樹，B+樹，鍵樹，TRIE樹，哈希表，
2. 理解與應用：
（1）理解靜態查找和動態查找的區別
（2）靜態查找的三種方法及實現，三種方法的特點及適用范圍
（3）二叉排序樹的構造和插入算法的思想及實現方法
（4）二叉排序樹構造過程中的平衡處理算法的思想
（5）各種查找方法的ASL計算
（6）B-樹上的查找、插入、刪除算法的思想
（7）哈希函數的構造方法
（8）哈希構造中處理沖突的方法
考試要求：
（1）掌握基本概念
（2）掌握算法的思想，能對算法代碼實現
（3）掌握哈希表的構造方法
（4）了解各種算法的應用范圍和解決的實際問題
（六）排序
1. 概念：排序，穩定，內排序，外排序
2. 理解與應用：
（1）排序算法的分類，重要指標
（2）各種排序算法的思想及實現方法
（3）各種算法的穩定性、時間復雜度、空間復雜度
（4）各種排序算法的特點和適用范圍
考試要求：
（1）掌握基本概念
（2）掌握各種排序算法的思想，能對算法代碼實現
（3）理解各種排序方法的優缺點和適用范圍
（4）了解穩定性、時間復雜度和空間復雜度對排序的影響

二、操作系統原理
（一）操作系統概論
考試內容：
1． 概念：操作系統的定義、功能和地位，操作系統的發展，操作系統基本特征
2． 理解和應用：
（1）批處理多道系統、分時系統和實時系統三個基本操作系統的工作原理及特征
（2）分時系統與實時系統的區別
（3）基本操作系統的特征
考試要求
（1）掌握基本概念
（2）理解操作系統在計算機系統中的地位和三個基本特征

（二）進程管理
考試內容：
1．概念：前趨圖，進程的定義、特征、三種基本狀態（就緒、阻塞和運行），進程控制塊，臨界資源，臨界區，同步機制應遵循的原則，管程的定義，條件變量，進程通信的類型，線程，線程的屬性，處理機的三級調度，進程的兩種調度方式，周轉時間，帶權周轉時間，常用的幾種調度算法（先來先服務、短作業（進程）優先、高優先權優先、高響應比優先、時間片輪轉法、多級反饋隊列調度），優先權，響應比，死鎖，產生死鎖的原因、必要條件及處理死鎖的基本方法，死鎖定理
2． 理解與應用：
（1）進程與程序的區別
（2）進程三個基本狀態之間的轉換及引起轉換的原因
（3）進程的兩種制約關系，并能進行辨別
（4）能夠辨別臨界資源
（5）常用的幾種信號量機制及每種機制的原理
（6）利用信號量實現進程的互斥、同步和前趨關系
（7）理解經典的進程同步問題（生產者-消費者問題；讀者-寫者問題；哲學家進餐問題）
（8）利用管理解決生產者和消費者問題
（9）消息傳遞通信的實現方法
（10）消息緩沖隊列通信的實現方法
（11）理解什么是內核支持線程和用戶級線程
（12）進程與線程的區別
（13）進程調度方式中搶占式的搶占原則
（14）理解每種調度算法的算法思想、優缺點，并能根據算法思想完成相應計算
（15）預防死鎖的各種方法
（16）銀行家算法的思想
（17）能夠根據銀行家算法和安全性檢測算法判斷系統的安全狀態及決定是否分配資源
（18）死鎖檢測的方法
（19）死鎖解除的方法
考試要求：
（1）掌握基本概念及基本原理
（2）重點：進程的概念和進程的并發特征；進程與程序的區別；進程狀態及轉換；相關臨界區問題和臨界資源；用信號量解決進程的同步與互斥問題；進程調度算法；死鎖的概念與解決死鎖的方法。
（3）難點：進程的相互制約；相關臨界區的概念；進程通信；用信號量解決進程的互斥與同步；

（三）存儲管理
考試內容：
1. 概念：相對地址，絕對地址，重定位，靜態重定位，動態重定位，碎片，拼接，頁表，快表，段表，虛擬存儲器的概念及特征，抖動（顛簸）
2. 理解與應用
（1）固定分區的內存分配原理
（2）動態（可變）分區的內存分配原理，及常用數據結構
（3）動態（可變）分區常用的三種分配算法（首次適應算法、循環首次適應算法、最佳適應算法）
（4）引入分頁和分段的原因
（5）基本分頁的實現原理及和機制
（6）基本分段的實現原理及和機制
（7）分頁與分段的主要區別
（8）請求分頁管理的實現原理和機制
（9）缺頁中斷的處理過程及缺頁中斷與一般中斷的區別
（10）掌握常用的頁面置換算法（最佳置換算法（OPT）；先進先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK）），并能根據算法思想完成相應計算
（11）請求分段管理的實現原理和機制
考試要求：
（1）掌握基本概念和原理
（2）重點：虛擬存儲器的概念；靜態與動態重定位及其區別；可變分區的管理算法；分頁管理的實現原理和機制；基本分段的實現原理和機制；典型的頁面替換算法；分頁與分段的區別。
（3）難點：虛擬存儲器的概念；頁面替換算法；分頁與分段的區別。

（四）設備管理
考試內容：
1. 概念：I/O設備的分類，通道，設備無關性，虛擬設備，SPOOLing技術，尋道時間，旋轉延遲時間
2. 理解與應用：
（1）設備管理的功能
（2）設備控制器的功能
（3）通道的分類
（4）I/O的幾種控制方式（程序I/O方式、中斷控制方式、DMA方式、通道控制方式）的工作原理及特點
（5）緩沖技術的引入目的和緩沖區的分類
（6）設備無關性；
（7）設備分配中常用的數據結構
（8）獨占設備的分配與釋放。
（9）SPOOLing系統的組成及實現
（10）磁盤調度常用的幾種調度算法（先來先服務、最短尋道優先、掃描算法、循環掃描算法），并能根據算法思想完成相應計算
考試要求：
（１）掌握基本概念和原理
（２）重點：I/O控制方式；緩沖技術的引入目的和緩沖區的種類；虛擬設備的概念和SPOOLING系統的組成和實現；磁盤調度算法。
（3）難點：設備無關性；虛擬設備；I/O控制方式。

（五）文件管理
考試內容：
1. 概念：文件、文件的分類，文件邏輯結構，文件物理結構，目錄，文件控制塊，按名存取，位示圖
2. 理解與應用：
（１）文件和文件系統的概念；
（２）文件的基本操作
（3）文件邏輯結構中的順序文件、索引文件和索引順序文件的形式和特點
（4）文件物理結構中涉及的連續分配、鏈接分配和索引分配如何實現一個文件在外存上的存放及每種分配方式的特點
（5）二級和多級文件目錄的形式及特點
（6）管理文件存儲空間的常用方法
（7）通過位示圖如何實現盤塊的分配和回收
考試要求：
（１）掌握基本概念和原理
（２）重點：文件的邏輯結構和物理結構；二級和多級文件目錄；管理文件存儲空間的方法。
（3）難點：文件的邏輯結構；文件的物理結構。
主要參考書目
《數據結構C語言版》，嚴蔚敏著，清華大學出版社
《計算機操作系統（第三版）》湯小丹著，西安電子科技大學出版社