一、考試目的

計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)考試內(nèi)容包括兩部分：數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)?？荚嚹康氖菣z查學(xué)生是否牢固掌握《數(shù)據(jù)結(jié)構(gòu)》和《操作系統(tǒng)》兩門課程相關(guān)知識(shí)的一次水平測(cè)定，全面考核普通高校計(jì)算機(jī)?？疲ê呗殻?yīng)屆畢業(yè)生對(duì)專業(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)，存儲(chǔ)結(jié)構(gòu)，運(yùn)算）；

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

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

（二）順序表

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

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

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

（三）鏈表

1、熟練掌握鏈表的概念及其特點(diǎn)；

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

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

（四）排序

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

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

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

（五）線性表的檢索

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

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

3、掌握散列法：

（1）掌握基本概念；

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

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

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

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

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

3、熟練掌握二叉樹的存儲(chǔ)表示

（1）二叉鏈表

（2）完全二叉樹的順序存儲(chǔ)；

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

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

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

（七）樹表檢索

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

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

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

（八）圖

1、熟練掌握?qǐng)D的概念和相關(guān)術(shù)語(yǔ)；

2、掌握?qǐng)D的存儲(chǔ)表示方法：鄰接矩陣，鄰接表，鄰接多重表；

3、掌握?qǐng)D的遍歷： 深度優(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)在計(jì)算機(jī)系統(tǒng)中的地位、操作系統(tǒng)的形成和發(fā)展；

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

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

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

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

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

2、掌握脫機(jī)作業(yè)控制方式，聯(lián)機(jī)作業(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、掌握脫機(jī)輸入輸出和SPOOLING 技術(shù)；

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

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

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

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

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

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

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

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

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

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

9、理解并熟練掌握利用信號(hào)量機(jī)制實(shí)現(xiàn)的生產(chǎn)者——消費(fèi)者問(wèn)題；

10、了解高級(jí)通訊原語(yǔ)（消息緩沖方式，信箱方式）；

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

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

13、了解單項(xiàng)資源的銀行家算法和多種資源的銀行家算法；

（五）存儲(chǔ)管理

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

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

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

4、理解并熟練掌握各種頁(yè)面置換算法（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)，文件存儲(chǔ)設(shè)備和存取法的關(guān)系；

7、掌握簡(jiǎn)單的文件目錄，二級(jí)目錄，多級(jí)目錄；

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

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

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

（七）設(shè)備管理

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

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

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

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

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

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

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

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

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

三、試題難易程度

較容易題 約30%

中等難度題 約50%

較難題 約20%

四、說(shuō)明

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

五、參考書目

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

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