一、考試基本要求

本考試大綱適用于報考合肥學(xué)院電子信息（計算機類）的碩士研究生入學(xué)考試,。該考試科目包含《數(shù)據(jù)結(jié)構(gòu)》,、《操作系統(tǒng)》兩門課程，《數(shù)據(jù)結(jié)構(gòu)》主要考查考生對數(shù)據(jù)的組織,、存儲,、處理等能力，算法設(shè)計以及對算法的分析和評價的掌握程度,。要求考生理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念,，熟練掌握各種數(shù)據(jù)結(jié)構(gòu)以及有關(guān)算法，并具有綜合運用所學(xué)知識分析和解決實際問題的能力,?！恫僮飨到y(tǒng)》主要考查考生對操作系統(tǒng)的基本概念,、基本原理和基本功能，以及操作系統(tǒng)的整體運行過程的理解能力,，操作系統(tǒng)進程,、內(nèi)存、文件和I/O管理的策略,、算法,、機制以及相互關(guān)系的分析和應(yīng)用能力，要求考生能夠運用所學(xué)的操作系統(tǒng)原理,、方法與技術(shù)來分析和解決問題,。

二、考試方式與時間

考試方式：閉卷筆試,。

試卷滿分為150分,，考試時間為180分鐘

3. 考查內(nèi)容及范圍

考試科目包含《數(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)

2．邏輯結(jié)構(gòu)　

3．存儲結(jié)構(gòu)　

4．算法和算法分析

（二）線性表

1．線性表的基本概念

2．線性表的順序表示和實現(xiàn)

3．線性鏈表　　

4．循環(huán)鏈表　　

5．雙向鏈表　　

6．鏈表的應(yīng)用　

（三）棧和隊列　

1．棧和隊列的基本概念　

2．棧的順序?qū)崿F(xiàn)　　

3．棧的鏈式實現(xiàn)

4．棧的應(yīng)用

5．棧與遞歸的實現(xiàn)

6．隊列的順序?qū)崿F(xiàn)　

7．隊列的鏈式實現(xiàn)　

（四）串　　

1．串的定義,、性質(zhì)和特點；

2．串的設(shè)計,、實現(xiàn)方法和基本操作,；　

3．串的樸素模式匹配算法

4．KMP模式匹配算法　

（五）數(shù)組和廣義表　　

1．?dāng)?shù)組的順序表示和實現(xiàn)　　

2．特殊矩陣

3．稀疏矩陣

4．廣義表的定義

5．廣義表的存儲結(jié)構(gòu)　　

6．廣義表的運算　　

（六）樹和二叉樹

1．樹的定義和基本術(shù)語　

2．二叉樹的定義和性質(zhì)

3．二叉樹的順序存儲

4．二叉樹的鏈式存儲　　

5．遍歷二叉樹　　

6．線索二叉樹　　

7．樹的存儲結(jié)構(gòu)　　

8．森林與二叉樹的轉(zhuǎn)換　

9．樹和森林的遍歷　

10．樹與等價問題　

11．哈夫曼樹及其應(yīng)用　　

（七）圖　

1．圖的定義和基本術(shù)語

2．圖的數(shù)組表示法　　

3．鄰接表　

4．十字鏈表

5．鄰接多重表　　

6．圖的深度優(yōu)先搜索

7．圖的廣度優(yōu)先搜索　

8．無向圖的連通分量和生成樹　

9．有向圖的強連通分量　　

10．最小生成樹　

11．拓撲排序

12．關(guān)鍵路徑

（八）查找　

1．查找的基本概念　　

2．順序查找　

3．二分查找　　

4．分塊查找　

5．二叉排序樹　

6．平衡二叉樹　　

7．散列查找　　

（九）內(nèi)部排序　　

1．直接插入排序　　

2．希爾排序　

3．冒泡排序

4．快速排序　

5．簡單選擇排序

6．樹形選擇排序　　

7．堆排序

8．歸并排序　　

9．基數(shù)排序　　

10．各種內(nèi)部排序方法的比較　

《操作系統(tǒng)》

（一） 操作系統(tǒng)引論

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

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

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

4. 操作系統(tǒng)的運行環(huán)境

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

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

7. 系統(tǒng)調(diào)用

（二） 進程的描述與控制

1. 前趨圖和程序執(zhí)行

2. 進程的描述

3. 進程控制

4. 進程通信

5. 線程的基本概念

6. 線程的實現(xiàn)

（三） 處理機調(diào)度與死鎖

1. 處理機調(diào)度概述

2. 調(diào)度算法

3. 實時調(diào)度

4. 死鎖概述

5. 死鎖預(yù)防

6. 死鎖避免

7. 死鎖的檢測與解除

（四） 進程同步

1. 進程同步的基本概念

2. 軟件同步機制

3. 硬件同步機制

4. 信號量機制

5. 管程機制

6. 經(jīng)典進程的同步問題

（五） 存儲器管理

1. 存儲器的層次結(jié)構(gòu)

2. 程序的裝入和鏈接

3. 對換與覆蓋

4. 連續(xù)分配存儲管理方式

5. 分頁存儲管理方式

6. 分段存儲管理方式

7. 段頁式存儲管理方式

（六） 虛擬存儲器

1. 虛擬存儲器概述

2. 請求分頁存儲管理方式

3. 頁面置換算法

4. “抖動”與工作集

5. 請求分段存儲管理方式

6. 虛擬存儲器實現(xiàn)實例

（七）  輸入/輸出系統(tǒng)

1. I/O 系統(tǒng)的功能、模型和接口

2. I/O 設(shè)備和設(shè)備控制器

3. 中斷和中斷處理程序

4. 設(shè)備驅(qū)動程序

5. 與設(shè)備無關(guān)的 I/O 軟件

6. 用戶層的 I/O 軟件

7. 緩沖區(qū)管理

8. 磁盤性能概述和磁盤調(diào)度

（八）  文件管理

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

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

3. 文件目錄

4. 文件共享

5. 文件保護

（九）  磁盤存儲器管理

1. 外存的組織方式

2. 文件存儲空間的管理

3. 提高磁盤 I/O 速度的途徑

4. 提高磁盤可靠性的技術(shù)

5. 存儲新技術(shù)

6. 數(shù)據(jù)一致性控制

四,、考試的基本題型

選擇題,、填空題、簡答題,、綜合題等,。

五、參考書目

[1] 嚴蔚敏,、吳偉民等.《數(shù)據(jù)結(jié)構(gòu)》（C語言版）.清華大學(xué)出版社,2011

年,，11月.

[2] 湯小丹等.計算機操作系統(tǒng)(慕課版).人民郵電出版社，2021年6月.