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

一、考查目標

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

二、考試形式與試卷結構

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

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

（二）答題方式

答題方式為閉卷、筆試。

（三）試卷內(nèi)容結構

各部分內(nèi)容所占分值為：

數(shù)據(jù)結構    75分

操作系統(tǒng)    75分

（四）試卷題型結構

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

三、考查范圍

數(shù)據(jù)結構

一、考查目標

1、掌握數(shù)據(jù)結構的基本概念、方法和技術。

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

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

二、考查內(nèi)容

1. 數(shù)據(jù)結構概述

數(shù)據(jù)結構的概念；

基本概念與術語；

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

2. 線性表

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

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

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

線性表的各種實現(xiàn)方式下能夠實現(xiàn)指定的操作。

3.棧和隊

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

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

4. 串

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

5.數(shù)組

數(shù)組的定義，數(shù)組的存儲，行序和列序；

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

6.樹和二叉樹

二叉樹的概念，二叉樹的五個性質(zhì)；

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

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

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

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

7. 圖

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

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

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

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

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

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

8. 查找

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

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

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

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

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

9.排序

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

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

冒泡排序，快速排序；

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

歸并排序；

基數(shù)排序。

操作系統(tǒng)

一、考查目標

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

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

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

二、考查內(nèi)容

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

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

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

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

2、用戶界面

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

命令控制界面接口；

系統(tǒng)調(diào)用

3、處理機管理

(1)進程管理

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

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

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

(2)處理機調(diào)度

調(diào)度的基本概念，調(diào)度的目標，功能與性能衡量；

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

4、存儲管理

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

覆蓋與交換技術；

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

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

段式與段頁式管理：基本原理和實現(xiàn)；

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

5、文件管理

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

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

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

磁盤組織與管理:磁盤調(diào)度算法

6、設備管理

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

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

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

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

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

虛擬設備，Spooling技術