一、考試目的

計算機科學(xué)與技術(shù)專業(yè)考試內(nèi)容包括兩部分：數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)?？荚嚹康氖菣z查學(xué)生是否牢固掌握《數(shù)據(jù)結(jié)構(gòu)》和《操作系統(tǒng)》兩門課程相關(guān)知識的一次水平測定，全面考核普通高校計算機?？疲ê呗殻?yīng)屆畢業(yè)生對專業(yè)核心課程《數(shù)據(jù)結(jié)構(gòu)》和《操作系統(tǒng)》的掌握程度，要求學(xué)生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)的基本概念和基本理論。

二、考試內(nèi)容

《數(shù)據(jù)結(jié)構(gòu)》部分

（一）數(shù)據(jù)結(jié)構(gòu)的概念

1、熟練掌握什么是數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)，運算）；

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

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

（二）順序表

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

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

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

（三）鏈表

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

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

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

（四）排序

1、掌握排序的概念，內(nèi)排序和外排序，排序算法的穩(wěn)定性；

2、掌握內(nèi)排序的分類；

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

（五）線性表的檢索

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

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

3、掌握散列法：

（1）掌握基本概念；

（2）理解散列函數(shù)的構(gòu)造方法；

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

（六）樹形結(jié)構(gòu)

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

2、掌握樹（林）與二叉樹的相互轉(zhuǎn)換；

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

（1）二叉鏈表

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

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

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

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

（七）樹表檢索

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

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

3、理解平衡二叉排序樹（AVL）的概念，構(gòu)造方法（如何調(diào)整。）

（八）圖

1、熟練掌握圖的概念和相關(guān)術(shù)語；

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

3、掌握圖的遍歷： 深度優(yōu)先遍歷，廣度優(yōu)先遍歷；

4、掌握最小生成樹的概念，構(gòu)造方法，算法；

5、理解拓?fù)渑判虻母拍?，算法思想，算法?/P>

6、掌握最短路徑的概念，構(gòu)造方法，算法。

《操作系統(tǒng)》部分

（一）操作系統(tǒng)的基本概念

1、理解操作系統(tǒng)的定義、特征及設(shè)置操作系統(tǒng)的目的；

2、了解操作系統(tǒng)在計算機系統(tǒng)中的地位、操作系統(tǒng)的形成和發(fā)展；

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

4、了解操作系統(tǒng)的分類；掌握分時系統(tǒng)的特征。

5、了解研究操作系統(tǒng)的幾種不同觀點。

（二）用戶與操作系統(tǒng)的接口

1、理解作業(yè)，作業(yè)步，作業(yè)流的概念；

2、掌握脫機作業(yè)控制方式，聯(lián)機作業(yè)控制方式；

3、了解系統(tǒng)功能調(diào)用。

（三）作業(yè)管理

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

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

3、掌握批處理作業(yè)的幾種調(diào)度算法以及作業(yè)調(diào)度和進(jìn)程調(diào)度的關(guān)系；

4、掌握脫機輸入輸出和SPOOLING 技術(shù)；

5、了解作業(yè)控制塊和作業(yè)后備隊列。

（四）進(jìn)程管理

1、理解并掌握程序的并發(fā)執(zhí)行和資源共享；

2、掌握程序并發(fā)執(zhí)行的特性；

3、理解并掌握進(jìn)程的概念、進(jìn)程的表示和調(diào)度狀態(tài)；

4、了解進(jìn)程的控制機構(gòu)及進(jìn)程控制原語；

5、熟練掌握常用的進(jìn)程調(diào)度算法（靜態(tài)優(yōu)先級法，動態(tài)優(yōu)先級法，時間片輪轉(zhuǎn)法）；

6、熟練掌握作業(yè)，進(jìn)程，和程序之間的區(qū)別和聯(lián)系；

7、理解并掌握進(jìn)程間的同步與互斥；

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

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

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

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

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

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

（五）存儲管理

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

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

3、理解并掌握頁式、段式和段頁式虛擬存儲管理的基本原理和地址轉(zhuǎn)換關(guān)系；

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

（六）文件管理系統(tǒng)

1、理解文件和文件系統(tǒng)的概念；

2、了解文件的基本類型及文件系統(tǒng)的基本功能；

3、理解文件的邏輯結(jié)構(gòu)（記錄式文件，流式文件）；

4、理解文件的物理結(jié)構(gòu)（連續(xù)結(jié)構(gòu)，串連結(jié)構(gòu)，索引文件）；

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

6、理解文件結(jié)構(gòu)，文件存儲設(shè)備和存取法的關(guān)系；

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

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

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

10、了解文件系統(tǒng)和用戶間的接口。

（七）設(shè)備管理

1、了解I/O設(shè)備類型及設(shè)備管理的設(shè)計目標(biāo)；

2、了解設(shè)備管理的基本功能；

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

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

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

6、了解順序存取存儲設(shè)備，直接存取存儲設(shè)備;

7、掌握磁盤的驅(qū)動調(diào)度算法。

（八）常用操作系統(tǒng)

了解DOS操作系統(tǒng)、WINDOWS操作系統(tǒng)和UNIX操作系統(tǒng)的概念和基本命令。

三、試題難易程度

較容易題 約30%

中等難度題 約50%

較難題 約20%

四、說明

試卷滿分為200分，《數(shù)據(jù)結(jié)構(gòu)》和《操作系統(tǒng)》各100分?？荚嚂r間為180分鐘。

五、參考書目

1、嚴(yán)蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)(C語言版)，清華大學(xué)出版社，2011年05月；

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