（招生代碼：10079）

《825數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)》

算法與數(shù)據(jù)結(jié)構(gòu)部分

一、考試內(nèi)容范圍：

1.建立有關(guān)數(shù)據(jù)結(jié)構(gòu)最基本的概念，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法，算法分析的基本概念與基本方法。

2.掌握線性表的定義，順序存儲(chǔ)線性表的基本運(yùn)算及其運(yùn)算的實(shí)現(xiàn)，堆棧和隊(duì)列的基本概念及運(yùn)算，多個(gè)棧的表示。

3.掌握單鏈表、鏈棧和鏈隊(duì)的存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算，了解循環(huán)鏈表和多重鏈表的基本概念。

4.掌握數(shù)組的尋址公式，數(shù)組的邏輯結(jié)構(gòu)，數(shù)組的順序存儲(chǔ)分配，矩陣的壓縮存儲(chǔ)，稀疏矩陣的存儲(chǔ)及運(yùn)算，廣義表的基本概念。

5.掌握串的定義以及各基本操作的特點(diǎn)，并能利用它們實(shí)現(xiàn)串的其它操作，理解串的各種表示方法，理解串匹配的各種算法。

6.掌握二叉樹(shù)的類(lèi)型定義，理解樹(shù)和二叉樹(shù)的結(jié)構(gòu)差別；熟練掌握二叉樹(shù)的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)對(duì)二叉樹(shù)的其他操作；理解二叉樹(shù)的線索化過(guò)程以及中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法；熟練掌握二叉樹(shù)和樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法；學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)二叉樹(shù)的各種操作的算法；了解哈夫曼樹(shù)的特性，掌握建立哈夫曼樹(shù)和哈夫曼編碼的方法。

7.掌握?qǐng)D的類(lèi)型定義，熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其選用原則，熟練掌握?qǐng)D的兩種遍歷算法，理解圖的各種應(yīng)用問(wèn)題的算法。

8.掌握以順序表或有序表表示靜態(tài)查找表時(shí)的查找方法。理解折半查找和分塊查找算法的原理。熟練掌握二叉排序樹(shù)的構(gòu)造和查找方法以及平衡二叉樹(shù)的構(gòu)造過(guò)程。了解B-樹(shù)的查找過(guò)程和在B-樹(shù)上插入，刪除結(jié)點(diǎn)的過(guò)程；熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其他結(jié)構(gòu)的表的實(shí)質(zhì)性差別。

9.理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。掌握各種排序方法的時(shí)間復(fù)雜度的分析算法的平均情況和最壞情況下的時(shí)間性能。理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。

10.理解順序文件、隨即文件、倒排文件、索引文件等。

二、考查重點(diǎn)：

1.緒論：數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)類(lèi)型、數(shù)據(jù)結(jié)構(gòu)及算法的基本概念。描述算法的方法及基本算法的分析方法。

2.順序存儲(chǔ)的線性表：線性表的定義，順序存儲(chǔ)線性表的基本運(yùn)算及其運(yùn)算的實(shí)現(xiàn)，堆棧和隊(duì)列的基本概念及運(yùn)算，多個(gè)棧的表示。

3.鏈表：?jiǎn)捂湵淼母拍罴盎具\(yùn)算的實(shí)現(xiàn)。鏈棧、鏈隊(duì)、循環(huán)鏈表、多重鏈表的基本概念。

4.數(shù)組：數(shù)組類(lèi)型的定義，存儲(chǔ)表示及尋址公式；特殊矩陣的壓縮存儲(chǔ)，稀疏矩陣的三元組表示及基本運(yùn)算的實(shí)現(xiàn)；廣義表的概念。

5.串：串的定義、存儲(chǔ)以及串的實(shí)現(xiàn)方法。

6.樹(shù)：二叉樹(shù)的性質(zhì)、存儲(chǔ)、遍歷及其它操作，樹(shù)的應(yīng)用，哈夫曼樹(shù)和哈夫曼編碼。

7.圖：圖的類(lèi)型定義，圖的存儲(chǔ)表示，圖的深度優(yōu)先搜索，圖的廣度優(yōu)先搜索，無(wú)向圖的最小生成樹(shù)，最短路徑，拓?fù)渑判?，關(guān)鍵路徑。

8.查找：順序表，有序表，索引順序表，靜態(tài)查找樹(shù)，二叉排序樹(shù)，平衡二叉樹(shù)，哈希表。

9.排序：插入排序，希爾排序，冒泡排序，快速排序，簡(jiǎn)單選擇排序，堆排序，基數(shù)排序，排序方法的綜合比較。

操作系統(tǒng)部分

一、考試內(nèi)容范圍：

1．操作系統(tǒng)引論

(1) 操作系統(tǒng)的目標(biāo)和作用

(2) 操作系統(tǒng)的發(fā)展過(guò)程

(3) 操作系統(tǒng)的基本特性

(4) 操作系統(tǒng)的主要功能

(5) 操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)

2. 進(jìn)程管理

(1) 線程的基本概念

(2) 進(jìn)程控制

(3) 進(jìn)程同步

(4) 經(jīng)典進(jìn)程的同步問(wèn)題

(5) 管程機(jī)制

(6) 進(jìn)程通信

(7) 線程

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

(1)處理機(jī)調(diào)度的基本概念

(2)調(diào)度算法

(3) 實(shí)時(shí)調(diào)度

(4) 多處理機(jī)系統(tǒng)中的調(diào)度

(5) 產(chǎn)生死鎖的原因和必要條件

(6) 預(yù)防死鎖的方法

(7) 死鎖的檢測(cè)和解除

4．存儲(chǔ)器管理

(1) 程序的裝入和鏈接

(2) 連續(xù)分配方式

(3) 基本分頁(yè)存儲(chǔ)管理方式

(4) 基本分段存儲(chǔ)管理方式

(5) 虛擬存儲(chǔ)器的基本概念

(6) 請(qǐng)求分頁(yè)存儲(chǔ)管理方式

(7) 頁(yè)面置換算法

(8) 請(qǐng)求分段存儲(chǔ)管理方式

5．設(shè)備管理

(1) I/O系統(tǒng)

(2) I/O控制方式

(3) 緩沖管理

(4) 設(shè)備分配

(5) 設(shè)備處理

(6) 磁盤(pán)存儲(chǔ)器管理

6．文件系統(tǒng)

(1) 文件和文件系統(tǒng)

(2) 文件的邏輯結(jié)構(gòu)

(3) 外存分配方式

(4) 目錄管理

(5) 文件存儲(chǔ)空間的管理

(6) 文件共享與文件保護(hù)

二、考查重點(diǎn)：

1．操作系統(tǒng)引論

(1) 操作系統(tǒng)的目標(biāo)和作用

(2) 操作系統(tǒng)的發(fā)展過(guò)程

(3) 操作系統(tǒng)的基本特性

(4) 操作系統(tǒng)的主要功能

2. 進(jìn)程管理

(1) 線程的基本概念

(2) 進(jìn)程控制

(3) 進(jìn)程同步

(4) 經(jīng)典進(jìn)程的同步問(wèn)題

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

(1)處理機(jī)調(diào)度的基本概念

(2)調(diào)度算法

(3) 產(chǎn)生死鎖的原因和必要條件

(4) 預(yù)防死鎖的方法

4．存儲(chǔ)器管理

(1) 程序的裝入和鏈接

(2) 連續(xù)分配方式

(3) 基本分頁(yè)存儲(chǔ)管理方式

(4) 基本分段存儲(chǔ)管理方式

(5) 虛擬存儲(chǔ)器的基本概念

(6) 請(qǐng)求分頁(yè)存儲(chǔ)管理方式

(7) 頁(yè)面置換算法

5．設(shè)備管理

(1) I/O系統(tǒng)

(2) I/O控制方式

(3) 緩沖管理

(4) 設(shè)備分配

(5) 設(shè)備處理

(6) 磁盤(pán)存儲(chǔ)器管理

6．文件系統(tǒng)

(1) 文件和文件系統(tǒng) （掌握）

(2) 文件的邏輯結(jié)構(gòu) （掌握）

(3) 外存分配方式 （掌握）

(4) 目錄管理 （掌握）

(5) 文件存儲(chǔ)空間的管理 （掌握）

更多學(xué)歷考試信息請(qǐng)查看學(xué)歷考試網(wǎng)