科目代碼：842

科目名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)

本門(mén)課程由數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)兩門(mén)課程組成，兩門(mén)課程各占75分，具體要求如下：

第一部分：數(shù)據(jù)結(jié)構(gòu)

一、考試的總體要求

掌握數(shù)據(jù)結(jié)構(gòu)中常用的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和基本操作，靈活運(yùn)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題;掌握典型的查找和排序算法，并能夠針對(duì)不同特征的數(shù)據(jù)集進(jìn)行有效應(yīng)用;能夠分析算法的時(shí)間復(fù)雜度，設(shè)計(jì)具有較高時(shí)空性能的算法。

二、考試的內(nèi)容

1、基本概念和術(shù)語(yǔ)

2、線(xiàn)性表

線(xiàn)性表的定義;線(xiàn)性表的邏輯結(jié)構(gòu);線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)(順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ));不同存儲(chǔ)方式下操作的實(shí)現(xiàn);線(xiàn)性表的應(yīng)用。

3、棧與隊(duì)列

棧：棧的定義;棧的邏輯結(jié)構(gòu);棧的存儲(chǔ)結(jié)構(gòu)(順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ));不同存儲(chǔ)方式下操作的實(shí)現(xiàn);棧的應(yīng)用。

隊(duì)列：隊(duì)列的定義;隊(duì)列的邏輯結(jié)構(gòu);隊(duì)列的存儲(chǔ)結(jié)構(gòu)(順序，鏈?zhǔn)?;不同存儲(chǔ)方式下操作的實(shí)現(xiàn);隊(duì)列的應(yīng)用。

4、樹(shù)和二叉樹(shù)

二叉樹(shù)：二叉樹(shù)的概念;二叉樹(shù)的基本性質(zhì);二叉樹(shù)的邏輯結(jié)構(gòu);二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(順序、鏈?zhǔn)?;各存儲(chǔ)結(jié)構(gòu)上的基本操作實(shí)現(xiàn);二叉樹(shù)的應(yīng)用。

樹(shù)和森林：樹(shù)(森林)的基本概念;樹(shù)(森林)的邏輯結(jié)構(gòu);樹(shù)(森林)的存儲(chǔ)結(jié)構(gòu)(雙親表示法，孩子鏈表表示法，孩子兄弟鏈表表示法);樹(shù)(森林)的基本操作實(shí)現(xiàn);樹(shù)(森林)的應(yīng)用。

樹(shù)(森林)與二叉樹(shù)之間的相互轉(zhuǎn)換;

哈夫曼樹(shù)(最優(yōu)二叉樹(shù))：哈夫曼樹(shù)的定義、哈夫曼樹(shù)的存儲(chǔ)與應(yīng)用。

5、圖

圖的定義與基本術(shù)語(yǔ);圖的邏輯結(jié)構(gòu);圖的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣，鄰接表及逆鄰接表);不同存儲(chǔ)結(jié)構(gòu)上的基本操作實(shí)現(xiàn);圖的應(yīng)用。

6、查找

基本概念與術(shù)語(yǔ);靜態(tài)查找(順序查找、折半查找、分塊查找);動(dòng)態(tài)查找(二叉排序樹(shù)、二叉平衡樹(shù)和B-樹(shù)的查找、插入和刪除);哈希查找(哈希表的概念、常用的哈希函數(shù)、解決沖突的方法);查找性能分析(平均查找長(zhǎng)度);

7、排序

插入類(lèi)排序(直接插入排序、折半插入排序、希爾排序)、交換類(lèi)排序(冒泡排序、快速排序)、選擇類(lèi)排序(簡(jiǎn)單選擇排序、堆排序)、歸并類(lèi)排序(二路歸并排序)、基數(shù)排序;各種排序方法的穩(wěn)定性和時(shí)間性能分析。

8.綜合應(yīng)用：根據(jù)實(shí)際問(wèn)題，設(shè)計(jì)有效的數(shù)據(jù)結(jié)構(gòu)和算法，并進(jìn)行時(shí)間復(fù)雜度分析。

三、考試的題型

選擇題、填空題、綜合題、算法設(shè)計(jì)題

第二部分：操作系統(tǒng)

一、考試的總體要求

要求考生熟練掌握計(jì)算機(jī)操作系統(tǒng)中的基本概念、基本原理; 從資源管理角度掌握計(jì)算機(jī)操作系統(tǒng)的主要功能及設(shè)計(jì)思想;了解和掌握現(xiàn)代計(jì)算機(jī)系統(tǒng)對(duì)其各種軟硬資源的管理方法及實(shí)現(xiàn)技術(shù);了解當(dāng)代計(jì)算機(jī)操作系統(tǒng)的新技術(shù)與發(fā)展趨勢(shì)。

二、考試的內(nèi)容

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

包括操作系統(tǒng)的定義;操作系統(tǒng)的發(fā)展過(guò)程;操作系統(tǒng)的分類(lèi);操作系統(tǒng)的特征和服務(wù);操作系統(tǒng)的功能;常用操作系統(tǒng)的結(jié)構(gòu)特點(diǎn)。

2.進(jìn)程管理：

包括進(jìn)程的基本概念;進(jìn)程控制(進(jìn)程的狀態(tài)機(jī)轉(zhuǎn)換);進(jìn)程同步;經(jīng)典的進(jìn)程同步互斥問(wèn)題;進(jìn)程通信;線(xiàn)程的定義及實(shí)現(xiàn)。

3.處理機(jī)調(diào)度與死鎖：

包括處理機(jī)調(diào)度的基本概念;調(diào)度方式及算法;死鎖的基本概念;死鎖的概念; 死鎖的處理策略。

4.存儲(chǔ)器管理：

包括程序的裝入和鏈接;連續(xù)分配存儲(chǔ)管理方式;覆蓋與交換;分頁(yè)存儲(chǔ)管理方式;分段存儲(chǔ)管理方式。虛擬存儲(chǔ)器的基本概念;請(qǐng)求分頁(yè)存儲(chǔ)管理方式;頁(yè)面置換算法;請(qǐng)求分段存儲(chǔ)管理方式。

5.設(shè)備管理：

包括I/O系統(tǒng)的組成;I/O控制方式;I/O軟件層次結(jié)構(gòu);設(shè)備獨(dú)立性;緩沖管理;假脫機(jī)技術(shù);設(shè)備分配;設(shè)備處理。

6.文件管理：

包括文件和文件系統(tǒng);文件邏輯結(jié)構(gòu);目錄管理;文件共享;文件保護(hù)。

7.磁盤(pán)管理：

包括磁盤(pán)I/O;外存分配方法;空閑存儲(chǔ)空間的管理;磁盤(pán)容錯(cuò)技術(shù)。

三、考試的題型

單向選擇題、填空題、應(yīng)用題