注：操作系統、數據結構各占50%操作系統：【考查目標】1、了解操作系統在計算機系統中的作用、地位、發展和特點。2、理解操作系統的基本概念、原理，掌握操作系統設計方法與實現技術。3、能夠運用所學的操作系統原理、方法與技術分析問題和解決問題。一、操作系統概述

1、操作系統的概念、作用和影響2、操作系統的形成和發展3、操作系統的基本功能、特征、運行環境和提供的服務4、操作系統的類型5、了解DOS、UNIX、LINUX、WINDOWS、OS/2類型及特點二、進程管理

（一）進程與線程1、進程的概念2、進程的狀態及其轉換3、進程的構成4、進程狀態的擴充-掛起狀態5、進程控制原語及其應用6、線程概念與多線程模型（二）進程的同步和互斥1、同步和互斥的基本概念2、實現臨界區互斥的鎖操作法3、信號量及其應用4、經典同步問題5、生產者-消費者問題；讀者-寫者問題；哲學家進餐問題（三）進程調度（四）死鎖1、死鎖的概念2、死鎖處理策略3、死鎖預防4、死鎖避免5、系統安全狀態：銀行家算法。6、死鎖檢測和解除三、作業與進程調度

1、作業的概念2、調度的基本概念3、調度的層次、作業調度和進程調度4、用戶與操作系統的接口5、調度時機、切換與過程6、調度的基本準則7、典型調度算法8、先來先服務調度算法：短作業（短任務、短進程、短線程）優先調度算法；時間片輪轉調度算法；優先級調度算法；高響應比優先調度算法；多級反饋隊列調度算法。四、存儲器管理

（一）內存管理基礎1、存儲器管理的基本任務2、邏輯地址與物理地址空間3、重定位4、程序裝入與鏈接（二）連續分配管理方式1、單一連續分配2、固定分區3、可變分區（三）覆蓋與交換技術（四）虛擬存儲器管理

1、虛擬內存的基本概念

2、分頁存儲管理3、頁面置換算法：OPT、FIFO、LRU、LFU4、頁面抖動5、分段存儲管理6、段頁式存儲管理五、設備管理

（一）設備管理概述1、設備的分類2、設備管理的目標和任務3、I/O應用接口4、I/O控制方式（二）設備分配與處理1、設備分配方法與過程2、緩沖區技術3、虛擬設備和SPOOL系統4、I/O

處理過程六、文件管理

1、文件及文件系統2、文件的組織形式和結構3、文件目錄4、輔存空間的管理5、文件的可靠性和安全性6、文件的AFT的作用7、文件基本操作的實現

七、UNIX簡介1、UNIX的特點2、UNIX進程的構成3、UNIX進程的狀態及其轉換

數據結構：第一章緒論[目的與要求]：深刻理解數據結構的概念，掌握數據結構的要素；掌握數據元素的邏輯結構；掌握數據元素的存貯結構；理解數據結構與算法的聯系；了解算法的效率及存貯空間的度量。[本章主要內容]：1.1什么是數據結構

1.2基本概念和術語

1.3數據結構的發展簡史及它在計算機科學中所處的地位

1.4算法的描述和算法分析

1.4.1算法的描述

1.4.2算法設計的要求

1.4.3算法效率的度量

1.4.4算法的存儲空間需求[本章重點]：1．基本概念和術語2．算法的描述和算法分析[本章難點]：1．算法的描述和算法分析第二章線性表[目的與要求]：掌握線性表順序存貯和鏈式存貯的特點；理解線性表的操作規律；了解線性表的應用。[本章主要內容]：2.1線性表的邏輯結構

2.2線性表的順序存儲結構

2.3線性表鏈式存儲結構

2.3.1線性鏈表

2.3.2循環鏈表

2.3.3雙向鏈表

2.4一元多項式的表示及相加[本章重點]：1．幾種常用鏈表的特點和運算2．從不同角度比較線性表在順序和鏈式兩種存儲結構的優缺點[本章難點]：1．幾種常用鏈表的特點和運算第三章棧和隊列[目的與要求]：掌握棧、隊列的定義及其相關數據結構的概念；了解棧的特征；掌握棧的表示和實現方法；了解棧空間的共用和棧的應用；掌握隊列的實現、鏈隊列及其操作；理解順序隊列的假溢出；掌握循環隊列的操作特點。

[本章主要內容]：3.1棧

3.1.1抽象數據類型棧的定義

3.1.2棧的表示和實現

3.2表達式求值

3.4隊列

3.4.1抽象數據類型隊列的定義

3.4.2鏈隊列——隊列的鏈式表示和實現

3.4.3循環隊列——隊列的順序表示和實現[本章重點]：1．順序棧和鏈棧上的進棧和退棧的算法2．在順序隊列上實現入隊和出隊的算法[本章難點]：1．順序棧和鏈棧上的進棧和退棧的算法2．在鏈隊列上實現入隊和出隊的算法第四章樹和叉樹[目的與要求]：掌握樹、二叉樹的定義；掌握樹、二叉樹的存貯方法；掌握二叉樹的先序、中序和后序遍歷規則及算法；了解線索二叉樹及其操作；掌握樹和二叉樹轉換的唯一性、森林與二叉樹的轉換規則；掌握哈夫曼樹及哈夫曼編碼。[本章主要內容]：4.1樹的定義和基本操作

4.2二叉樹

4.2.1二叉樹的操作

4.2.2二叉樹的性質

4.2.3二叉樹的存儲結構

4.3遍歷二叉樹和線索二叉樹

4.3.1遍歷二叉樹

4.3.2線索二叉樹

4.4樹和森林

4.4.1樹的存儲結構

4.4.2森林與二叉樹的轉換

4.4.3樹的遍歷4.6哈夫曼樹及其應用

4.6.1最優二叉樹

4.6.2哈夫曼編碼[本章重點]：1．二叉樹的性質與各種遍歷算法2．哈夫曼樹[本章難點]：1．遍歷二叉樹和線索二叉樹2．哈夫曼樹及其應用第五章圖[目的與要求]：掌握圖的基本概念，掌握圖的存貯方法、圖的深度優先算法和廣度優先遍歷規則及算法、最小生成樹的構造、拓撲排序、關鍵路徑和最短路徑。[本章主要內容]：5.1圖的定義和術語

5.2圖的存儲結構

5.2.1數組表示法

5.2.2鄰接表

5.3圖的遍歷

5.3.1深度優先搜索

5.3.2廣度優先搜索

5.4圖的連通性問題

5.4.1無向圖的連通分量和生成樹5.4.3最小生成樹

5.5有向無環圖及其應用

5.5.1拓樸排序

5.5.2關鍵路徑[本章重點]：1．圖的存儲結構2．圖的遍歷3．有向無環圖及其應用

[本章難點]：1．關鍵路徑2．最短路徑第六章查找[目的與要求]：掌握順序表的查找及其效率；理解折半查找的兩個條件；掌握二叉樹和平衡二叉樹的構造、四種類型的不平衡調整；理解哈希函數與哈希表；掌握沖突與沖突的解決方法；掌握哈希表的插入與刪除方法。會推導B-樹的平均查找長度。[本章主要內容]：6.1靜態表的查找

6.1.1有序表的查找

6.1.2靜態樹表的查找

6.1.3靜態樹表的查找

6.1.4索引順序表的查找

6.2動態查找表

6.2.1二叉排序樹和平衡二叉樹

6.3哈希表

6.3.1什么是哈希表

6.3.2哈希函數的構造方法

6.3.3處理沖突的方法

6.3.4哈希表的查找及其分析[本章重點]：1．靜態表2．哈希表[本章難點]：1．動態表第七章內部排序[目的與要求]：理解排序定義；了解排序的分類；掌握插入排序方法及效果；掌握集合的劃分及快速排序方法；掌握堆的構造及堆選排序方法；掌握歸并的效率及歸并排序方法；了解基數排序及其特點。[本章主要內容]：7.1概述

7.2插入排序

7.2.1直接插入排序

7.2.2其它插入排序

7.2.3希爾排序

7.3快速排