854計(jì)算機(jī)專業(yè)基礎(chǔ)

1、遼寧大學(xué) 2020 年全國碩士研究生招生考試初試自命題科目考試大綱科目代 碼：854 科目名稱：計(jì)算機(jī)專業(yè)基礎(chǔ)滿分： 150 分考試內(nèi)容包括：操作系統(tǒng)和數(shù)據(jù)結(jié)構(gòu)一、操作系統(tǒng)1、操作系統(tǒng)引論（ 1）設(shè)計(jì)操作系統(tǒng)的目標(biāo)及操作系統(tǒng)的作用。（2）操作系統(tǒng)的基本特征和操作系統(tǒng)的主要功能。2、進(jìn)程的描述與控制（1）進(jìn)程的概念、進(jìn)程的特征及操作系統(tǒng)中引入進(jìn)程的原因。（ 2）進(jìn)程與程序的區(qū)別。（3）進(jìn)程控制：進(jìn)程的三種基本狀態(tài)及引起進(jìn)程狀態(tài)轉(zhuǎn)換的事件。（4）進(jìn)程同步：使用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥、描述前趨圖。（ 5）經(jīng)典進(jìn)程的同步問題：生產(chǎn)者 -消費(fèi)者、哲學(xué)家進(jìn)餐、讀者 -寫者問 題。3、處理機(jī)調(diào)度與死鎖（1）

2、高級(jí)、中級(jí)及初級(jí)調(diào)度的功能。（ 2）調(diào)度算法：先來先服務(wù)、短作業(yè) /進(jìn)程優(yōu)先、高優(yōu)先權(quán)優(yōu)先、高響應(yīng) 比優(yōu)先及多級(jí)反饋隊(duì)列調(diào)度算法的原理及應(yīng)用。當(dāng)調(diào)度算法應(yīng)用于進(jìn)程調(diào)度 時(shí)，需要考慮系統(tǒng)是否采用搶占式的調(diào)度方式。（ 3）死鎖的定義及死鎖產(chǎn)生的必要條件。（ 4）預(yù)防死鎖的方法及具體措 施。（ 5）避免死鎖：掌握銀行家算法的基本思想，并能夠應(yīng)用銀行家算法判定 是否滿足某進(jìn)程的資源請求，從而避免系統(tǒng)進(jìn)入不安全狀態(tài)。4、存儲(chǔ)器管理 （1）連續(xù)分配存儲(chǔ)管理方式：重點(diǎn)掌握動(dòng)態(tài)分區(qū)分配方式。（ 2）分頁存儲(chǔ)管理方式：實(shí)現(xiàn)的基本原理及將給定的邏輯地址轉(zhuǎn)換成相應(yīng) 的物理地址。（ 3）分段存儲(chǔ)管理方式：實(shí)現(xiàn)的基本原

3、理及將給定的邏輯地址轉(zhuǎn)換成相應(yīng) 的物理地址。5、虛擬存儲(chǔ)器（ 1）請求分頁存儲(chǔ)管理方式：實(shí)現(xiàn)的基本原理及將給定的邏輯地址轉(zhuǎn)換成 相應(yīng)的物理地址。（2）頁面置換算法：最佳置換、先進(jìn)先出、最近最久未使用、簡單的 Clock、改進(jìn)型Clock等置換算法實(shí)現(xiàn)的基本原理及應(yīng)用。6、輸入輸出系統(tǒng)（1） Spooling系統(tǒng)的組成、特點(diǎn)及假脫機(jī)打印機(jī)系統(tǒng)的實(shí)現(xiàn)（2）磁盤存儲(chǔ) 器的性能和調(diào)度：掌握先來先服務(wù)、最短尋道時(shí)間優(yōu)先、掃描算法及循環(huán)掃描 算法的原理與應(yīng)用。7、文件管理（ 1）文件系統(tǒng)的層次結(jié)構(gòu)（ 2）文件系統(tǒng)中使用打開和關(guān)閉文件操作的目的（ 3）文件的邏輯結(jié)構(gòu)（ 4）文件目錄8、磁盤存儲(chǔ)器的管理1）外

4、存的組織方式：掌握鏈接組織方式及索引組織方式（ 2）文件存儲(chǔ)空間的管理：掌握位示圖法和成組鏈接法。二、數(shù)據(jù)結(jié)構(gòu)1、緒論（ 1）基本概念和術(shù)語（2）數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的區(qū)別（ 3）抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)（ 4）算法的相關(guān)概念（ 5）時(shí)間復(fù)雜度和空間復(fù)雜度的概念和分析2、線性表（ 1）線性表的類型定義（ 2）順序表，主要包括：順序表的特點(diǎn)、順序表的存儲(chǔ)結(jié)構(gòu)的定義、順序 表的常見操作、順序表的合并、利用順序表解決簡單的應(yīng)用問題。（ 3）鏈表，主要包括：鏈表的定義、鏈表的存儲(chǔ)結(jié)構(gòu)的定義、鏈表的常見 操作、鏈表的合并、順序表和鏈表的比較、利用鏈表解決簡單的應(yīng)用問題。3、棧和隊(duì)列（ 1）棧，主要包括：棧

5、的定義、棧的存儲(chǔ)結(jié)構(gòu)、棧的基本操作、棧的應(yīng) 用。（ 2）棧與遞歸，主要包括：遞歸的定義、遞歸算法、遞歸的應(yīng)用。（3）隊(duì)列，主要包括：隊(duì)列的定義、隊(duì)列的存儲(chǔ)結(jié)構(gòu)、隊(duì)列的常見操作。4、樹（ 1）樹的定義和術(shù)語。（ 2）二叉樹，主要包括：二叉樹的定義、二叉樹的性質(zhì)、二叉樹的遍歷、 二叉樹的建立和應(yīng)用。（ 3）樹和森林，主要包括：樹的存儲(chǔ)結(jié)構(gòu)、樹和森林與二叉樹之間轉(zhuǎn)換、 樹和森林的遍歷、樹和森林與二叉樹之間轉(zhuǎn)換。（ 4）赫夫曼樹，主要包括：赫夫曼樹的定義、赫夫曼算法、赫夫曼樹編 碼、赫夫曼樹應(yīng)用。5、圖（ 1）圖的定義和基本概念（ 2）圖的存儲(chǔ)，主要包括：數(shù)組表示法、鄰接表、圖的存儲(chǔ)結(jié)構(gòu)的對(duì)比。（3）圖的常見操作，主要包括：圖的建立、度的計(jì)算、深度優(yōu)先遍歷、廣 度優(yōu)先遍歷等。（ 4）圖的連通性問題，主要包括：用 Prim 求最小生成樹、用 Kruskal 求最 小生成樹。（ 5）有向無環(huán)圖，主要包括：拓?fù)渑判蛩惴?、關(guān)鍵路徑。（6）最短路徑，主要包括：最短路徑定義和算法。6、查找（ 1）靜態(tài)查找，主要包括：相關(guān)概念、順序查找、二分查找。（ 2）動(dòng)態(tài) 查找，主要包括：二叉排序樹、 B 樹。（ 3）哈希查找，主要包括：哈希表定義、哈希表的構(gòu)造、哈希查找的分 析。7、排序（ 1）排序的定義與相關(guān)