《數據結構與操作系統(tǒng)》考試大綱

一、考查目標

數據結構和操作系統(tǒng)是計算機類專業(yè)的核心課程?！稊祿Y構和操作系統(tǒng)》科目考察的內容包括《數據結構》和《操作系統(tǒng)》的基本內容，要求考生掌握相關的概念、方法和技術，并具備較強的程序設計能力，能夠靈活應用相關的方法和技術解決實際問題。

二、考試形式與試卷結構

（一）試卷成績及考試時間

本試卷滿分為150分，考試時間為180分鐘。

（二）答題方式

答題方式為閉卷、筆試。

（三）試卷內容結構

各部分內容所占分值為：

數據結構    75分

操作系統(tǒng)    75分

（四）試卷題型結構

選擇題，簡答題，綜合題，程序設計題

三、考查范圍

數據結構

一、考查目標

1、掌握數據結構的基本概念、方法和技術。

2、掌握程序設計的基本方法和技巧。

3、能夠應用相關知識解決一些有實際背景的問題。

二、考查內容

1. 數據結構概述

數據結構的概念；

基本概念與術語；

算法的概念，算法的特性，以及算法設計的要求，算法效率的度量。

2. 線性表

線性表的基本概念和結構特點；

線性表的順序存儲方式以及兩種不同的實現方法，線性表存儲空間的靜態(tài)分配和動態(tài)分配；

線性表的鏈式存儲方式的實現，鏈表與順序表的相似及不同之處，優(yōu)缺點比較，各自適用的場合；

線性表的各種實現方式下能夠實現指定的操作。

3.棧和隊

棧、隊列的定義及其相關數據結構的概念，包括：順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊列等；

棧與隊列插入刪除操作的特點；棧和遞歸的關系；棧和隊列各種實現方式。

4. 串

 串的基本概念，樸素的模式匹配算法。

5.數組

數組的定義，數組的存儲，行序和列序；

特殊矩陣的定義；特殊矩陣的壓縮存儲。

6.樹和二叉樹

二叉樹的概念，二叉樹的五個性質；

二叉樹的存儲結構：順序存儲和二叉鏈表存儲的各自優(yōu)缺點及適用場合；

二叉樹的三種遍歷方法：先序，中序和后序，線索二叉樹，線索化后二叉樹的遍歷方法；

哈夫曼樹概念，哈夫曼樹的構造方法，前綴碼概念，哈夫曼編碼。

樹的存儲表示方法，樹與森林轉化為二叉樹，樹和森林的遍歷問題。

7. 圖

圖的基本概念，圖的定義和特點；

圖的幾種存儲形式，重點是鄰接矩陣和鄰接表；

深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法；

生成樹、最小生成樹的概念以及最小生成樹的構造：PRIM算法和KRUSKAL算法；

有向無環(huán)圖，拓撲排序和關鍵路徑問題；

最短路徑問題：DIJSKTRA算法和FLOYD算法。

8. 查找

關鍵字、主關鍵字、次關鍵字的含義；

靜態(tài)查找與動態(tài)查找的含義及區(qū)別，平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結果；

順序表的查找，折半查找，索引順序表；

二叉排序樹，平衡二叉樹，B樹；

哈希表的概念，哈希函數的設計，沖突解決方法的選擇及沖突處理過程。

9.排序

要求掌握各種排序方法的思想和算法實現，排序算法穩(wěn)定性的概念，以及各自的特點。

插入排序：直接插入、折半插入、2路插入、希爾排序；

冒泡排序，快速排序；

選擇排序：簡單選擇、樹選擇、堆排序；

歸并排序；

基數排序。

操作系統(tǒng)

一、考查目標

1、了解操作系統(tǒng)在計算機系統(tǒng)中的作用、地位，操作系統(tǒng)的發(fā)展歷史，各類型操作系統(tǒng)的特點。

2、掌握操作系統(tǒng)資源管理的原理、機制、策略和關鍵技術，理解操作系統(tǒng)的運行過程。

3、能夠運用所學的操作系統(tǒng)原理、方法與技術分析和解決問題。

二、考查內容

1、操作系統(tǒng)概述

操作系統(tǒng)的概念、特征、功能和提供的服務；

操作系統(tǒng)的發(fā)展歷史與分類；

操作系統(tǒng)的運行環(huán)境

2、用戶界面

作業(yè)的概念及作業(yè)的建立過程；

命令控制界面接口；

系統(tǒng)調用

3、處理機管理

(1)進程管理

進程與線程，進程的狀態(tài)與轉換，進程控制，進程間通信；

進程同步與互斥，信號量機制與P、V操作，經典的同步互斥模型；

死鎖的預防、避免、檢測和解除

(2)處理機調度

調度的基本概念，調度的目標，功能與性能衡量；

典型調度算法：先來先服務、短作業(yè)（短進程）優(yōu)先、時間片輪轉、基于優(yōu)先級、最高響應比優(yōu)先、多級反饋輪轉等調度算法。

4、存儲管理

存儲管理的功能：虛擬存儲器、地址變換、內存的分配與回收、內存信息的共享與保護；

覆蓋與交換技術；

分區(qū)存儲管理：基本原理、分區(qū)的分配與回收；

頁式存儲管理：基本原理和實現，請求頁式管理中的頁面置換算法：先進先出置換算法（FIFO）、最近最少使用置換算法（LRU）、最佳置換算法（OPT）、時鐘置換算法（CLOCK）等；

段式與段頁式管理：基本原理和實現；

工作集、局部性原理和抖動問題

5、文件管理

文件和文件系統(tǒng)的基本概念；

文件邏輯結構與物理結構；

文件存儲管理：文件存儲空間管理，文件目錄管理，文件存取控制，文件系統(tǒng)層次結構；

磁盤組織與管理:磁盤調度算法

6、設備管理

設備管理的目的、設備管理的功能和任務；

數據傳輸控制方式：程序直接控制、中斷、DMA、通道；

中斷技術：中斷的概念、中斷的分類、軟中斷、中斷的處理過程；

緩沖技術：緩沖的種類、緩沖池的管理；

設備分配與回收：設備分配用數據結構、分配原則和分配算法；

虛擬設備，Spooling技術