2021遼寧大學(xué)計算機專業(yè)基礎(chǔ)專業(yè)研究生考試大綱 正文

一、操作系統(tǒng)
1、操作系統(tǒng)引論
（1）設(shè)計操作系統(tǒng)的目標(biāo)及操作系統(tǒng)的作用。
（2）操作系統(tǒng)的基本特征和操作系統(tǒng)的主要功能。
2、進程的描述與控制
（1）進程的概念、進程的特征及操作系統(tǒng)中引入進程的原因。
（2）進程與程序的區(qū)別。
（3）進程控制：進程的三種基本狀態(tài)及引起進程狀態(tài)轉(zhuǎn)換的事件。
（4）進程同步：使用信號量機制實現(xiàn)進程互斥、描述前趨圖。
（5）經(jīng)典進程的同步問題：生產(chǎn)者-消費者、哲學(xué)家進餐、讀者-寫者問題。
3、處理機調(diào)度與死鎖
（1）高級、中級及初級調(diào)度的功能。
（2）調(diào)度算法：先來先服務(wù)、短作業(yè)/進程優(yōu)先、高優(yōu)先權(quán)優(yōu)先、高響應(yīng)比優(yōu)先及多級反饋隊列調(diào)度算法的原理及應(yīng)用。當(dāng)調(diào)度算法應(yīng)用于進程調(diào)度時，需要考慮系統(tǒng)是否采用搶占式的調(diào)度方式。
（3）死鎖的定義及死鎖產(chǎn)生的必要條件。
（4）預(yù)防死鎖的方法及具體措施。
（5）避免死鎖：掌握銀行家算法的基本思想，并能夠應(yīng)用銀行家算法判定是否滿足某進程的資源請求，從而避免系統(tǒng)進入不安全狀態(tài)。
4、存儲器管理
（1）連續(xù)分配存儲管理方式：重點掌握動態(tài)分區(qū)分配方式。
（2）分頁存儲管理方式：實現(xiàn)的基本原理及將給定的邏輯地址轉(zhuǎn)換成相應(yīng)的物理地址。
（3）分段存儲管理方式：實現(xiàn)的基本原理及將給定的邏輯地址轉(zhuǎn)換成相應(yīng)的物理地址。
5、虛擬存儲器
（1）請求分頁存儲管理方式：實現(xiàn)的基本原理及將給定的邏輯地址轉(zhuǎn)換成相應(yīng)的物理地址。
（2）頁面置換算法：最佳置換、先進先出、最近最久未使用、簡單的Clock、改進型Clock等置換算法實現(xiàn)的基本原理及應(yīng)用。
6、輸入輸出系統(tǒng)
（1）Spooling系統(tǒng)的組成、特點及假脫機打印機系統(tǒng)的實現(xiàn)
（2）磁盤存儲器的性能和調(diào)度：掌握先來先服務(wù)、最短尋道時間優(yōu)先、掃描算法及循環(huán)掃描算法的原理與應(yīng)用。
7、文件管理
（1）文件系統(tǒng)的層次結(jié)構(gòu)
（2）文件系統(tǒng)中使用打開和關(guān)閉文件操作的目的
（3）文件的邏輯結(jié)構(gòu)
（4）文件目錄
8、磁盤存儲器的管理
（1）外存的組織方式：掌握鏈接組織方式及索引組織方式
（2）文件存儲空間的管理：掌握位示圖法和成組鏈接法。
二、數(shù)據(jù)結(jié)構(gòu)
1、緒論
（1）基本概念和術(shù)語
（2）數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的區(qū)別
（3）抽象數(shù)據(jù)類型的表示和實現(xiàn)
（4）算法的相關(guān)概念
（5）時間復(fù)雜度和空間復(fù)雜度的概念和分析
2、線性表 
（1）線性表的類型定義
（2）順序表，主要包括：順序表的特點、順序表的存儲結(jié)構(gòu)的定義、順序表的常見操作、順序表的合并、利用順序表解決簡單的應(yīng)用問題。
（3）鏈表，主要包括：鏈表的定義、鏈表的存儲結(jié)構(gòu)的定義、鏈表的常見操作、鏈表的合并、順序表和鏈表的比較、利用鏈表解決簡單的應(yīng)用問題。
3、棧和隊列
（1）棧，主要包括：棧的定義、棧的存儲結(jié)構(gòu)、棧的基本操作、棧的應(yīng)用。
（2）棧與遞歸，主要包括：遞歸的定義、遞歸算法、遞歸的應(yīng)用。
（3）隊列，主要包括：隊列的定義、隊列的存儲結(jié)構(gòu)、隊列的常見操作。
4、樹
（1）樹的定義和術(shù)語。
（2） 二叉樹，主要包括：二叉樹的定義、二叉樹的性質(zhì)、 二叉樹的遍歷、二叉樹的建立和應(yīng)用。
（3）樹和森林，主要包括：樹的存儲結(jié)構(gòu)、樹和森林與二叉樹之間轉(zhuǎn)換、樹和森林的遍歷、樹和森林與二叉樹之間轉(zhuǎn)換。
（4）赫夫曼樹，主要包括：赫夫曼樹的定義、赫夫曼算法、赫夫曼樹編碼、赫夫曼樹應(yīng)用。
5、圖
（1）圖的定義和基本概念
（2）圖的存儲，主要包括：數(shù)組表示法、鄰接表、圖的存儲結(jié)構(gòu)的對比。
（3）圖的常見操作，主要包括：圖的建立、度的計算、深度優(yōu)先遍歷、廣度優(yōu)先遍歷等。
（4）圖的連通性問題，主要包括：用Prim求最小生成樹、用Kruskal求最小生成樹。
（5）有向無環(huán)圖，主要包括：拓撲排序算法、關(guān)鍵路徑。
（6）最短路徑，主要包括：最短路徑定義和算法。
6、查找
（1）靜態(tài)查找，主要包括：相關(guān)概念、順序查找、二分查找。
（2）動態(tài)查找，主要包括：二叉排序樹、B樹。
（3）哈希查找，主要包括：哈希表定義、哈希表的構(gòu)造、哈希查找的分析。
7、排序
（1）排序的定義與相關(guān)概念。
（2）插入排序，主要包括：直接插入排序、希爾排序。
（3）交換排序，主要包括：起泡排序、快速排序。
（4）選擇排序，主要包括：簡單選擇排序、樹形選擇排序、堆排序。
（5）歸并排序

遼寧大學(xué)

本文來源：http://www.lyhuahuisp.com/liaoningdaxue/cankaoshumu_387843.html