一、考試目的

計算機科學與技術專業考試內容包括兩部分：數據結構和操作系統?？荚嚹康氖菣z查學生是否牢固掌握《數據結構》和《操作系統》兩門課程相關知識的一次水平測定，全面考核普通高校計算機?？疲ê呗殻獙卯厴I生對專業核心課程《數據結構》和《操作系統》的掌握程度，要求學生比較系統地理解數據結構和操作系統的基本概念和基本理論。

二、考試內容

《數據結構》部分

（一）數據結構的概念

1、熟練掌握什么是數據結構（邏輯結構，存儲結構，運算）；

2、掌握算法，算法分析，算法特性；

3、理解算法與程序的差別。

（二）順序表

1、熟練掌握線性表（向量）的定義，操作，算法；

2、熟練掌握棧的定義，操作，算法；

3、熟練掌握隊列的定義，操作，算法。

（三）鏈表

1、熟練掌握鏈表的概念及其特點；

2、熟練掌握單鏈表的概念，存儲表示，查找，輸入，刪除等運算和算法；

3、熟練掌握雙鏈表的概念，存儲表示，查找，輸入，刪除等運算和算法。

（四）排序

1、掌握排序的概念，內排序和外排序，排序算法的穩定性；

2、掌握內排序的分類；

3、熟練掌握各種排序的基本思想，例子，算法，穩定性，時空復雜度。

（五）線性表的檢索

1、熟練掌握順序檢索的概念，算法，時間復雜度；

2、熟練掌握二分檢索的概念，算法，時間復雜度；

3、掌握散列法：

（1）掌握基本概念；

（2）理解散列函數的構造方法；

（3）掌握沖突的處理：拉鏈法，開地址法，算法。

（六）樹形結構

1、熟練掌握樹和二叉樹的概念；

2、掌握樹（林）與二叉樹的相互轉換；

3、熟練掌握二叉樹的存儲表示

（1）二叉鏈表

（2）完全二叉樹的順序存儲；

4、熟練掌握二叉樹與樹的周游（遍歷）的概念，各種周游方法；

5、掌握二叉樹遍歷的算法；

6、理解二叉樹中其他算法（結點統計，高度計算，左右子樹交換等）。

（七）樹表檢索

1、掌握二叉排序樹的概念，插入，刪除運算；

2、掌握最佳二叉排序樹的概念，建立方法，算法；

3、理解平衡二叉排序樹（AVL）的概念，構造方法（如何調整。）

（八）圖

1、熟練掌握圖的概念和相關術語；

2、掌握圖的存儲表示方法：鄰接矩陣，鄰接表，鄰接多重表；

3、掌握圖的遍歷： 深度優先遍歷，廣度優先遍歷；

4、掌握最小生成樹的概念，構造方法，算法；

5、理解拓撲排序的概念，算法思想，算法；

6、掌握最短路徑的概念，構造方法，算法。

《操作系統》部分

（一）操作系統的基本概念

1、理解操作系統的定義、特征及設置操作系統的目的；

2、了解操作系統在計算機系統中的地位、操作系統的形成和發展；

3、掌握多道程序設計和虛擬處理機的基本原理；

4、了解操作系統的分類；掌握分時系統的特征。

5、了解研究操作系統的幾種不同觀點。

（二）用戶與操作系統的接口

1、理解作業，作業步，作業流的概念；

2、掌握脫機作業控制方式，聯機作業控制方式；

3、了解系統功能調用。

（三）作業管理

1、理解并掌握作業管理的基本功能；

2、理解并掌握作業控制的兩種方式；

3、掌握批處理作業的幾種調度算法以及作業調度和進程調度的關系；

4、掌握脫機輸入輸出和SPOOLING 技術；

5、了解作業控制塊和作業后備隊列。

（四）進程管理

1、理解并掌握程序的并發執行和資源共享；

2、掌握程序并發執行的特性；

3、理解并掌握進程的概念、進程的表示和調度狀態；

4、了解進程的控制機構及進程控制原語；

5、熟練掌握常用的進程調度算法（靜態優先級法，動態優先級法，時間片輪轉法）；

6、熟練掌握作業，進程，和程序之間的區別和聯系；

7、理解并掌握進程間的同步與互斥；

8、理解信號量及P，V操作，并能利用信號量機制實現進程間的同步與互斥；

9、理解并熟練掌握利用信號量機制實現的生產者——消費者問題；

10、了解高級通訊原語（消息緩沖方式，信箱方式）；

11、理解并掌握死鎖的概念、起因及產生死鎖的必要條件；

12、了解處理死鎖的四種對策（預防策略，避免策略，檢測和解除）；

13、了解單項資源的銀行家算法和多種資源的銀行家算法；

（五）存儲管理

1、理解并掌握存儲管理的基本概念功能及物理地址和邏輯地址之間的關系；

2、了解早期計算機系統中主要采用的單一連續分配，分區分配，覆蓋和交換的存儲管理方案；

3、理解并掌握頁式、段式和段頁式虛擬存儲管理的基本原理和地址轉換關系；

4、理解并熟練掌握各種頁面置換算法（FIFO，LRU，LRU近似算法）。

（六）文件管理系統

1、理解文件和文件系統的概念；

2、了解文件的基本類型及文件系統的基本功能；

3、理解文件的邏輯結構（記錄式文件，流式文件）；

4、理解文件的物理結構（連續結構，串連結構，索引文件）；

5、掌握文件的存取方法（順序存取法，直接存取法，按鍵存取法）；

6、理解文件結構，文件存儲設備和存取法的關系；

7、掌握簡單的文件目錄，二級目錄，多級目錄；

8、掌握文件存儲空間管理的各種辦法；

9、掌握文件存取控制的各種方法；

10、了解文件系統和用戶間的接口。

（七）設備管理

1、了解I/O設備類型及設備管理的設計目標；

2、了解設備管理的基本功能；

3、掌握I/O控制的幾種方式；

4、掌握通道功能及類型；

5、了解通道命令和通道程序；

6、了解順序存取存儲設備，直接存取存儲設備;

7、掌握磁盤的驅動調度算法。

（八）常用操作系統

了解DOS操作系統、WINDOWS操作系統和UNIX操作系統的概念和基本命令。

三、試題難易程度

較容易題 約30%

中等難度題 約50%

較難題 約20%

四、說明

試卷滿分為200分，《數據結構》和《操作系統》各100分?？荚嚂r間為180分鐘。

五、參考書目

1、嚴蔚敏、吳偉民，數據結構(C語言版)，清華大學出版社，2011年05月；

2、湯子瀛等《計算機操作系統》，西安電子科技大學出版社，2006年12月，修訂版。