2014燕山大學(xué)數(shù)據(jù)庫(kù)與操作系統(tǒng)考研復(fù)習(xí)大綱

注：操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)各占50%操作系統(tǒng)：【考查目標(biāo)】1、了解操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的作用、地位、發(fā)展和特點(diǎn)。2、理解操作系統(tǒng)的基本概念、原理，掌握操作系統(tǒng)設(shè)計(jì)方法與實(shí)現(xiàn)技術(shù)。3、能夠運(yùn)用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題。一、操作系統(tǒng)概述

1、操作系統(tǒng)的概念、作用和影響2、操作系統(tǒng)的形成和發(fā)展3、操作系統(tǒng)的基本功能、特征、運(yùn)行環(huán)境和提供的服務(wù)4、操作系統(tǒng)的類型5、了解DOS、UNIX、LINUX、WINDOWS、OS/2類型及特點(diǎn)二、進(jìn)程管理

（一）進(jìn)程與線程1、進(jìn)程的概念2、進(jìn)程的狀態(tài)及其轉(zhuǎn)換3、進(jìn)程的構(gòu)成4、進(jìn)程狀態(tài)的擴(kuò)充-掛起狀態(tài)5、進(jìn)程控制原語及其應(yīng)用6、線程概念與多線程模型（二）進(jìn)程的同步和互斥1、同步和互斥的基本概念2、實(shí)現(xiàn)臨界區(qū)互斥的鎖操作法3、信號(hào)量及其應(yīng)用4、經(jīng)典同步問題5、生產(chǎn)者-消費(fèi)者問題；讀者-寫者問題；哲學(xué)家進(jìn)餐問題（三）進(jìn)程調(diào)度（四）死鎖1、死鎖的概念2、死鎖處理策略3、死鎖預(yù)防4、死鎖避免5、系統(tǒng)安全狀態(tài)：銀行家算法。6、死鎖檢測(cè)和解除三、作業(yè)與進(jìn)程調(diào)度

1、作業(yè)的概念2、調(diào)度的基本概念3、調(diào)度的層次、作業(yè)調(diào)度和進(jìn)程調(diào)度4、用戶與操作系統(tǒng)的接口5、調(diào)度時(shí)機(jī)、切換與過程6、調(diào)度的基本準(zhǔn)則7、典型調(diào)度算法8、先來先服務(wù)調(diào)度算法：短作業(yè)（短任務(wù)、短進(jìn)程、短線程）優(yōu)先調(diào)度算法；時(shí)間片輪轉(zhuǎn)調(diào)度算法；優(yōu)先級(jí)調(diào)度算法；高響應(yīng)比優(yōu)先調(diào)度算法；多級(jí)反饋隊(duì)列調(diào)度算法。四、存儲(chǔ)器管理

（一）內(nèi)存管理基礎(chǔ)1、存儲(chǔ)器管理的基本任務(wù)2、邏輯地址與物理地址空間3、重定位4、程序裝入與鏈接（二）連續(xù)分配管理方式1、單一連續(xù)分配2、固定分區(qū)3、可變分區(qū)（三）覆蓋與交換技術(shù)（四）虛擬存儲(chǔ)器管理

1、虛擬內(nèi)存的基本概念

2、分頁存儲(chǔ)管理3、頁面置換算法：OPT、FIFO、LRU、LFU4、頁面抖動(dòng)5、分段存儲(chǔ)管理6、段頁式存儲(chǔ)管理五、設(shè)備管理

（一）設(shè)備管理概述1、設(shè)備的分類2、設(shè)備管理的目標(biāo)和任務(wù)3、I/O應(yīng)用接口4、I/O控制方式（二）設(shè)備分配與處理1、設(shè)備分配方法與過程2、緩沖區(qū)技術(shù)3、虛擬設(shè)備和SPOOL系統(tǒng)4、I/O

處理過程六、文件管理

1、文件及文件系統(tǒng)2、文件的組織形式和結(jié)構(gòu)3、文件目錄4、輔存空間的管理5、文件的可靠性和安全性6、文件的AFT的作用7、文件基本操作的實(shí)現(xiàn)

七、UNIX簡(jiǎn)介1、UNIX的特點(diǎn)2、UNIX進(jìn)程的構(gòu)成3、UNIX進(jìn)程的狀態(tài)及其轉(zhuǎn)換

數(shù)據(jù)結(jié)構(gòu)：第一章緒論[目的與要求]：深刻理解數(shù)據(jù)結(jié)構(gòu)的概念，掌握數(shù)據(jù)結(jié)構(gòu)的要素；掌握數(shù)據(jù)元素的邏輯結(jié)構(gòu)；掌握數(shù)據(jù)元素的存貯結(jié)構(gòu)；理解數(shù)據(jù)結(jié)構(gòu)與算法的聯(lián)系；了解算法的效率及存貯空間的度量。[本章主要內(nèi)容]：1.1什么是數(shù)據(jù)結(jié)構(gòu)

1.2基本概念和術(shù)語

1.3數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡(jiǎn)史及它在計(jì)算機(jī)科學(xué)中所處的地位

1.4算法的描述和算法分析

1.4.1算法的描述

1.4.2算法設(shè)計(jì)的要求

1.4.3算法效率的度量

1.4.4算法的存儲(chǔ)空間需求[本章重點(diǎn)]：1．基本概念和術(shù)語2．算法的描述和算法分析[本章難點(diǎn)]：1．算法的描述和算法分析第二章線性表[目的與要求]：掌握線性表順序存貯和鏈?zhǔn)酱尜A的特點(diǎn)；理解線性表的操作規(guī)律；了解線性表的應(yīng)用。[本章主要內(nèi)容]：2.1線性表的邏輯結(jié)構(gòu)

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)

2.3線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2.3.1線性鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表

2.4一元多項(xiàng)式的表示及相加[本章重點(diǎn)]：1．幾種常用鏈表的特點(diǎn)和運(yùn)算2．從不同角度比較線性表在順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)[本章難點(diǎn)]：1．幾種常用鏈表的特點(diǎn)和運(yùn)算第三章棧和隊(duì)列[目的與要求]：掌握棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念；了解棧的特征；掌握棧的表示和實(shí)現(xiàn)方法；了解?？臻g的共用和棧的應(yīng)用；掌握隊(duì)列的實(shí)現(xiàn)、鏈隊(duì)列及其操作；理解順序隊(duì)列的假溢出；掌握循環(huán)隊(duì)列的操作特點(diǎn)。

[本章主要內(nèi)容]：3.1棧

3.1.1抽象數(shù)據(jù)類型棧的定義

3.1.2棧的表示和實(shí)現(xiàn)

3.2表達(dá)式求值

3.4隊(duì)列

3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義

3.4.2鏈隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

3.4.3循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)[本章重點(diǎn)]：1．順序棧和鏈棧上的進(jìn)棧和退棧的算法2．在順序隊(duì)列上實(shí)現(xiàn)入隊(duì)和出隊(duì)的算法[本章難點(diǎn)]：1．順序棧和鏈棧上的進(jìn)棧和退棧的算法2．在鏈隊(duì)列上實(shí)現(xiàn)入隊(duì)和出隊(duì)的算法第四章樹和叉樹[目的與要求]：掌握樹、二叉樹的定義；掌握樹、二叉樹的存貯方法；掌握二叉樹的先序、中序和后序遍歷規(guī)則及算法；了解線索二叉樹及其操作；掌握樹和二叉樹轉(zhuǎn)換的唯一性、森林與二叉樹的轉(zhuǎn)換規(guī)則；掌握哈夫曼樹及哈夫曼編碼。[本章主要內(nèi)容]：4.1樹的定義和基本操作

4.2二叉樹

4.2.1二叉樹的操作

4.2.2二叉樹的性質(zhì)

4.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)

4.3遍歷二叉樹和線索二叉樹

4.3.1遍歷二叉樹

4.3.2線索二叉樹

4.4樹和森林

4.4.1樹的存儲(chǔ)結(jié)構(gòu)

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

4.4.3樹的遍歷4.6哈夫曼樹及其應(yīng)用

4.6.1最優(yōu)二叉樹

4.6.2哈夫曼編碼[本章重點(diǎn)]：1．二叉樹的性質(zhì)與各種遍歷算法2．哈夫曼樹[本章難點(diǎn)]：1．遍歷二叉樹和線索二叉樹2．哈夫曼樹及其應(yīng)用第五章圖[目的與要求]：掌握?qǐng)D的基本概念，掌握?qǐng)D的存貯方法、圖的深度優(yōu)先算法和廣度優(yōu)先遍歷規(guī)則及算法、最小生成樹的構(gòu)造、拓?fù)渑判?、關(guān)鍵路徑和最短路徑。[本章主要內(nèi)容]：5.1圖的定義和術(shù)語

5.2圖的存儲(chǔ)結(jié)構(gòu)

5.2.1數(shù)組表示法

5.2.2鄰接表

5.3圖的遍歷

5.3.1深度優(yōu)先搜索

5.3.2廣度優(yōu)先搜索

5.4圖的連通性問題

5.4.1無向圖的連通分量和生成樹5.4.3最小生成樹

5.5有向無環(huán)圖及其應(yīng)用

5.5.1拓樸排序

5.5.2關(guān)鍵路徑[本章重點(diǎn)]：1．圖的存儲(chǔ)結(jié)構(gòu)2．圖的遍歷3．有向無環(huán)圖及其應(yīng)用

[本章難點(diǎn)]：1．關(guān)鍵路徑2．最短路徑第六章查找[目的與要求]：掌握順序表的查找及其效率；理解折半查找的兩個(gè)條件；掌握二叉樹和平衡二叉樹的構(gòu)造、四種類型的不平衡調(diào)整；理解哈希函數(shù)與哈希表；掌握沖突與沖突的解決方法；掌握哈希表的插入與刪除方法。會(huì)推導(dǎo)B-樹的平均查找長(zhǎng)度。[本章主要內(nèi)容]：6.1靜態(tài)表的查找

6.1.1有序表的查找

6.1.2靜態(tài)樹表的查找

6.1.3靜態(tài)樹表的查找

6.1.4索引順序表的查找

6.2動(dòng)態(tài)查找表

6.2.1二叉排序樹和平衡二叉樹

6.3哈希表

6.3.1什么是哈希表

6.3.2哈希函數(shù)的構(gòu)造方法

6.3.3處理沖突的方法

6.3.4哈希表的查找及其分析[本章重點(diǎn)]：1．靜態(tài)表2．哈希表[本章難點(diǎn)]：1．動(dòng)態(tài)表第七章內(nèi)部排序[目的與要求]：理解排序定義；了解排序的分類；掌握插入排序方法及效果；掌握集合的劃分及快速排序方法；掌握堆的構(gòu)造及堆選排序方法；掌握歸并的效率及歸并排序方法；了解基數(shù)排序及其特點(diǎn)。[本章主要內(nèi)容]：7.1概述

7.2插入排序

7.2.1直接插入排序

7.2.2其它插入排序

7.2.3希爾排序

7.3快速排