本科目包括《數據結構》和《計算機操作系統》兩門課程，總分150分，兩門課程各占75分

　　《數據結構》

　　一、總體要求

　　《數據結構》是計算機程序設計的重要理論技術基礎，是計算機科學與技術學科的核心課程。要求：

　　1.理解數據結構的基本概念；掌握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現。

　　2.掌握基本的數據處理原理和方法的基礎上，能夠分析算法的時間復雜度與空間復雜度。

　　3.能夠選擇合適的數據結構和算法策略進行問題求解，具備采用C 或C++或JAVA 語言設計與實現算法的能力。

　　二、內容

　　1. 數據結構及算法的相關概念和術語

　　（1） 數據結構及算法的概念

　?。?） 數據的邏輯結構和存儲結構

　?。?） 算法的定義及特性

　　（4） 算法時間復雜度和空間復雜度的分析方法

　　2．線性表

　?。?） 線性表的定義

　?。?） 線性表的基本操作及在順序存儲及鏈式存儲上的實現

　?。?） 各種變形鏈表（循環鏈表、雙向鏈表、帶頭結點的鏈表等）的表示和基本操作的實現

　　（4） 遞歸過程的特點及實現方法

　?。?） 棧和隊列的基本概念；棧和隊列的順序存儲結構、鏈式儲存結構及其存儲特點

　?。?） 棧和隊列的應用

　?。?） 循環隊列的判滿、判空方法

　　（8） 特殊矩陣的壓縮儲存

　　3．廣義表的基本概念、存儲結構和基本操作

　　4．樹和二叉樹

　?。?） 樹與森林的基本概念

　　（2） 樹與森林的存儲結構及遍歷

　?。?） 二叉樹的定義及6大性質

　　（4） 二叉樹的順序儲存與鏈式儲存結構

　?。?） 二叉樹的先序、中序、后序三種遍歷方式的關系以及實現；層序遍歷的實現

　?。?） 線索二叉樹的基本概念與構造方法

　　（7） 樹與二叉樹的應用：二叉排序樹；二叉平衡樹；哈夫曼樹與哈夫曼編碼

　　5．圖

　?。?） 圖的基本概念和術語

　?。?） 圖的存儲結構：鄰接矩陣、鄰接表、逆鄰接表

　?。?） 遍歷算法：深度優先搜索算法和廣度優先搜索算法

　　（4） 應用：最小生成樹；最短路徑，拓撲排序和關鍵路徑

　　6．查找

　　（1） 查找的基本概念；靜態查找與動態查找

　　（2） 順序查找、折半查找、索引查找

　?。?） 哈希查找

　　哈希函數的基本構造方法，解決地址沖突的基本策略

　　（4） 各種查找算法的時間復雜度和空間復雜度

　　7．排序

　　（1） 排序的基本概念

　?。?） 插入排序

　?。?） 簡單選擇排序

　　（4） 希爾排序

　　（5） 快速排序

　　（6） 堆排序

　?。?） 歸并排序

　?。?） 基數排序

　?。?） 排序算法的比較其中算法題分為閱讀、修改和編寫算法三類：

　　(1)閱讀算法：閱讀指定算法，回答使用的數據結構、算法實現的功能或執行的結果；

　　(2)修改算法：閱讀指定算法，指出算法的錯誤并修正；指出算法的不足并改進；按給定功能填寫算法空缺部分；

　　(3)編寫算法：根據算法功能要求，選擇或者設計合適的數據結構，用程序設計語言編寫算法，實現指定功能。

　　以上皆可分析給定或者設計的算法時空復雜度。

　　操作系統部分一、總體要求主要考察學生對操作系統基本概念、原理的理解程度，重點考察操作系統的設計方法與實現技術，同時能夠具備運用所學的操作系統原理、方法與技術分析問題和解決問題的能力。

　　二、內容

　　1. 操作系統的基本概念

　　1) 批處理與多道程序設計

　　2) 分時系統與實時系統

　　3) 操作系統的基本類型與特征

　　4) 并發與并行的概念

　　5) 操作系統的層次結構與功能模塊

　　6) 程序的并發執行與順序執行

　　2. 進程管理

　　1) 進程: 進程控制塊、進程的幾種基本狀態與狀態轉換（進程的創建、進程的終止、進程的阻塞與喚醒、進程的掛起與激活等）

　　2) 進程的同步與互斥：臨界資源、臨界區、進程同步與互斥問題、信號量機制以及P、V操作、管程機制

　　3) 進程間通信：進程通信的類型（直接通信和間接通信方式）、消息傳遞系統中的幾個問題、消息緩沖隊列通信機制

　　4) 線程與進程的調度:線程與進程的基本概念，調度的類型、調度隊列模型、調度方式、進程調度算法（先來先服務、短進程優先、時間片輪轉、基于優先級的調度算法等）

　　5) 死鎖:死鎖的基本概念，死鎖定理、死鎖預防、死鎖避免與處理死鎖的基本方法、銀行家

　　算法

　　6) 綜合應用：生產者消費者問題、讀者和寫者問題、哲學家進餐問題等

　　3. 內存管理

　　1) 內存管理的需求：重定位、內存保護、內存共享

　　2) 程序的裝入和鏈接：靜態裝入和可重定位裝入、靜態鏈接、動態鏈接、運行時動態鏈接。

　　3) 分區存儲管理：分區方式（單一連續分區、固定分區、可變式分區）、分區分配算法（首次適應算法、循環首次適應算法、最佳適應法、最壞適應法等）

　　4) 段式管理與頁式管理：段、頁、碎片等基本概念、段式管理與頁式管理機制

　　5) 虛擬內存：局部性原理、虛擬內存概念、請求分段與請求分頁、段頁式管理、段頁式地址結構與地址轉換、頁面置換算法（OPT、先進先出、LRU、Clock、改進型Clock置換）、抖動

　　4. 設備管理

　　1) I/O系統的：基本概念、I/O控制方式（程序I/0、中斷、DMA、通道）、相關數據結構、緩沖管理（單緩沖、雙緩沖、循環緩沖、緩沖池）

　　2) 磁盤管理與磁盤調度算法：SSTF算法，SCAN算法，CSCAN算法，N-STEP-SCAN算法，FSCAN 算法

　　3) 設備分配、設備處理、虛擬設備，Spooling系統

　　5. 文件系統

　　1) 基本概念：文件和文件系統、目錄、文件結構的物理結構和邏輯結構（順序文件、索引順

　　序文件、索引文件、HASH文件）、文件共享（基于索引節點、基于符號鏈接實現文件共享）

　　2) 外存分配方法：連續分配、鏈接分配、索引分配

　　3) 目錄管理：單級目錄、二級目錄、多級目錄

　　4) 文件存儲空間的管理技術：位示圖、空閑鏈表、索引