遼寧大學2021年全國碩士研究生招生考試初試自命題科目考試大綱

科目代碼：854               

科目名稱：計算機專業基礎

滿分：150 分

考試內容包括：操作系統和數據結構

一、操作系統

1、操作系統引論

（1）設計操作系統的目標及操作系統的作用。

（2）操作系統的基本特征和操作系統的主要功能。

2、進程的描述與控制

（1）進程的概念、進程的特征及操作系統中引入進程的原因。

（2）進程與程序的區別。

（3）進程控制：進程的三種基本狀態及引起進程狀態轉換的事件。

（4）進程同步：使用信號量機制實現進程互斥、描述前趨圖。

（5）經典進程的同步問題：生產者-消費者、哲學家進餐、讀者-寫者問題。

3、處理機調度與死鎖

（1）高級、中級及初級調度的功能。

（2）調度算法：先來先服務、短作業/進程優先、高優先權優先、高響應比優先及多級反饋隊列調度算法的原理及應用。當調度算法應用于進程調度時，需要考慮系統是否采用搶占式的調度方式。

（3）死鎖的定義及死鎖產生的必要條件。

（4）預防死鎖的方法及具體措施。

（5）避免死鎖：掌握銀行家算法的基本思想，并能夠應用銀行家算法判定是否滿足某進程的資源請求，從而避免系統進入不安全狀態。

4、存儲器管理

（1）連續分配存儲管理方式：重點掌握動態分區分配方式。

（2）分頁存儲管理方式：實現的基本原理及將給定的邏輯地址轉換成相應的物理地址。

（3）分段存儲管理方式：實現的基本原理及將給定的邏輯地址轉換成相應的物理地址。

5、虛擬存儲器

（1）請求分頁存儲管理方式：實現的基本原理及將給定的邏輯地址轉換成相應的物理地址。

（2）頁面置換算法：最佳置換、先進先出、最近最久未使用、簡單的Clock、改進型Clock等置換算法實現的基本原理及應用。

6、輸入輸出系統

（1）Spooling系統的組成、特點及假脫機打印機系統的實現

（2）磁盤存儲器的性能和調度：掌握先來先服務、最短尋道時間優先、掃描算法及循環掃描算法的原理與應用。

7、文件管理

（1）文件系統的層次結構

（2）文件系統中使用打開和關閉文件操作的目的

（3）文件的邏輯結構

（4）文件目錄

8、磁盤存儲器的管理

（1）外存的組織方式：掌握鏈接組織方式及索引組織方式

（2）文件存儲空間的管理：掌握位示圖法和成組鏈接法。

二、數據結構

1、緒論

（1）基本概念和術語

（2）數據結構和數據類型的區別

（3）抽象數據類型的表示和實現

（4）算法的相關概念

（5）時間復雜度和空間復雜度的概念和分析

2、線性表 

（1）線性表的類型定義

（2）順序表，主要包括：順序表的特點、順序表的存儲結構的定義、順序表的常見操作、順序表的合并、利用順序表解決簡單的應用問題。

（3）鏈表，主要包括：鏈表的定義、鏈表的存儲結構的定義、鏈表的常見操作、鏈表的合并、順序表和鏈表的比較、利用鏈表解決簡單的應用問題。

3、棧和隊列

（1）棧，主要包括：棧的定義、棧的存儲結構、棧的基本操作、棧的應用。

（2）棧與遞歸，主要包括：遞歸的定義、遞歸算法、遞歸的應用。

（3）隊列，主要包括：隊列的定義、隊列的存儲結構、隊列的常見操作。

4、樹

（1）樹的定義和術語。

（2） 二叉樹，主要包括：二叉樹的定義、二叉樹的性質、 二叉樹的遍歷、二叉樹的建立和應用。

（3）樹和森林，主要包括：樹的存儲結構、樹和森林與二叉樹之間轉換、樹和森林的遍歷、樹和森林與二叉樹之間轉換。

（4）赫夫曼樹，主要包括：赫夫曼樹的定義、赫夫曼算法、赫夫曼樹編碼、赫夫曼樹應用。

5、圖

（1）圖的定義和基本概念

（2）圖的存儲，主要包括：數組表示法、鄰接表、圖的存儲結構的對比。

（3）圖的常見操作，主要包括：圖的建立、度的計算、深度優先遍歷、廣度優先遍歷等。

（4）圖的連通性問題，主要包括：用Prim求最小生成樹、用Kruskal求最小生成樹。

（5）有向無環圖，主要包括：拓撲排序算法、關鍵路徑。

（6）最短路徑，主要包括：最短路徑定義和算法。

6、查找

（1）靜態查找，主要包括：相關概念、順序查找、二分查找。

（2）動態查找，主要包括：二叉排序樹、B樹。

（3）哈希查找，主要包括：哈希表定義、哈希表的構造、哈希查找的分析。

7、排序

（1）排序的定義與相關概念。

（2）插入排序，主要包括：直接插入排序、希爾排序。

（3）交換排序，主要包括：起泡排序、快速排序。

（4）選擇排序，主要包括：簡單選擇排序、樹形選擇排序、堆排序。

（5）歸并排序