2021西南石油大學(xué)計算機(jī)學(xué)科綜合專業(yè)研究生參考及考試大綱 正文
西南石油大學(xué)
碩士研究生招生專業(yè)課考試大綱
考試科目名稱：計算機(jī)學(xué)科綜合
一、考試性質(zhì)
計算機(jī)學(xué)科綜合是碩士研究生入學(xué)考試科目之一，是碩士研究生招生院校自
行命題的選拔性考試。本考試大綱的制定力求反映招生類型的特點，科學(xué)、公平、
準(zhǔn)確、規(guī)范地測評考生的相關(guān)基礎(chǔ)知識掌握水平，考生分析問題和解決問題及綜
合知識運用能力。應(yīng)考人員應(yīng)根據(jù)本大綱的內(nèi)容和要求自行組織學(xué)習(xí)內(nèi)容和掌握
有關(guān)知識。
本科目包含數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)兩門課程?？荚嚂r間共 180 分鐘。兩門課
程各 75 分。
數(shù)據(jù)結(jié)構(gòu)主要包括三大常用數(shù)據(jù)結(jié)構(gòu)的邏輯、物理表示與基本操作算法實現(xiàn)
部分的知識，各種結(jié)構(gòu)的經(jīng)典應(yīng)用和具體問題求解?？忌鷳?yīng)掌握各種數(shù)據(jù)結(jié)構(gòu)及
其操作，具備一定的算法設(shè)計與分析能力，能夠根據(jù)實際問題選擇合適的數(shù)據(jù)結(jié)
構(gòu)并設(shè)計算法實現(xiàn)。
操作系統(tǒng)主要包括其對各種計算機(jī)硬、軟件資源的管理方法的理論與應(yīng)用學(xué)
習(xí)?？忌鷳?yīng)掌握操作系統(tǒng)的基本概念、原理和基本功能，掌握操作系統(tǒng)中進(jìn)程、
內(nèi)存、文件和 I/O 管理的策略、算法、機(jī)制以及相互關(guān)系，并能夠運用所學(xué)的原
理、方法與技術(shù)分析和解決實際問題以及代碼實現(xiàn)。
二、考試主要內(nèi)容
第一部分：數(shù)據(jù)結(jié)構(gòu)
（一）緒論
1、基本概念和術(shù)語
1）基本要求
了解課程的研究內(nèi)容，理解數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念。
2）考試范圍
掌握數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容、基本概念和相關(guān)術(shù)語；理解抽象數(shù)據(jù)類型的表示與實
現(xiàn)。
2、算法和算法分析
1）基本要求
理解算法的含義，熟悉算法描述語言，掌握算法的性能評價指標(biāo)及評價方法,并能
分析常用算法的時間復(fù)雜度。
2）考試范圍
算法的概念與特征；算法效率的度量指標(biāo)；時間復(fù)雜度與空間復(fù)雜度的計算方法；
常見時間復(fù)雜度類型與性能優(yōu)劣比較。
（二）線性表
1、線性表的類型定義
1）基本要求
掌握線性表的邏輯結(jié)構(gòu)及相關(guān)概念；理解線性表的抽象數(shù)據(jù)類型。
2）考試范圍
線性表的概念及文件、數(shù)據(jù)項及記錄的相關(guān)概念；線性表的抽象數(shù)據(jù)類型；用線
性表表示集合合并的算法；合并有序線性表的算法。
2、線性表的表示和實現(xiàn)
1）基本要求
掌握線性表的順序與鏈?zhǔn)絻煞N存儲結(jié)構(gòu)及其各種基本運算的的實現(xiàn)過程；掌握兩
種存儲方式之間的差異及各自優(yōu)缺點；能夠靈活運用順序表和鏈表解決實際問題。
2）考試范圍
順序存儲結(jié)構(gòu)的概念及計算第 i 個元素存儲地址的公式；用類 C 描述線性表的順
序存儲結(jié)構(gòu)；順序表的初始化、插入、刪除、定位和有序表合并算法；線性鏈表
及相關(guān)概念；用 C 語言描述線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)；鏈表的訪問、插入、刪除和
有序合并算法；線性表的靜態(tài)鏈表表示基本定義；循環(huán)鏈表的定義以及與單鏈表
的區(qū)別；雙向鏈表的定義和存儲表示；雙向鏈表的插入與刪除算法；一元多項式
的表示及相加算法實現(xiàn)。
（三）棧和隊列
1、棧
1）基本要求
理解棧的定義、特性和運算；掌握棧的順序存儲實現(xiàn)及其性能分析；理解和掌握
用棧實現(xiàn)表達(dá)式求解的過程；了解棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)。
2）考試范圍
棧的抽象數(shù)據(jù)類型定義；棧的先進(jìn)后出特性；棧的存儲表示與基本操作實現(xiàn)；棧
的應(yīng)用。
2、隊列
1）基本要求
理解隊列的定義、特性和運算；理解隊列的順序存儲實現(xiàn)及其性能分析；理解循
環(huán)隊列的背景和實現(xiàn)方法；理解隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)及其性能分析。
2）考試范圍
隊列的抽象數(shù)據(jù)類型定義；隊列的先進(jìn)先出特性；隊列的存儲表示與基本操作實
現(xiàn)。
（四）串
1）基本要求
掌握串的相關(guān)概念、串的存儲結(jié)構(gòu)（順序串和鏈?zhǔn)酱┘盎具\算的實現(xiàn)；掌握
KMP 算法的基本思想及模式匹配過程；能靈活運用串的特點解決復(fù)雜的應(yīng)用問
題。
2）考試范圍
串類型的定義；串的定長順序存儲、堆分配存儲、塊鏈存儲表示和實現(xiàn)；串的模
式匹配算法；串的應(yīng)用。
（五）數(shù)組和廣義表
1）基本要求
理解數(shù)組結(jié)構(gòu)及其存儲，理解矩陣的壓縮存儲方式及其映射關(guān)系；理解廣義表以
及子表、原子和長度等概念；理解廣義表的基本運算及其存儲。
2）考試范圍
數(shù)組的定義；二維數(shù)組的兩種存儲方式（以行序為主、以列序為主）及其數(shù)組元
素存儲位置計算公式；特殊矩陣與稀疏矩陣的壓縮存儲方式；廣義表的定義和存
儲結(jié)構(gòu)。
（六）樹和二叉樹
1）基本要求
理解樹和二叉樹的定義及相關(guān)術(shù)語；理解二叉樹的五個性質(zhì)及相關(guān)概念；理解二
叉樹的兩種存儲結(jié)構(gòu)的形式、描述及特點，理解二叉樹的遍歷運算，并能綜合應(yīng)
用；理解線索二叉樹及其存儲結(jié)構(gòu)，線索化方法和算法，以及在指定線索二叉樹
中求解指定次序的前趨和后繼的算法；理解樹和森林的存儲結(jié)構(gòu)及其描述，樹（森
林）與二叉樹的相互轉(zhuǎn)換，樹（森林）的遍歷算法；理解樹模型在軟件設(shè)計中的
作用；理解赫夫曼樹的有關(guān)概念、應(yīng)用及構(gòu)造。
2）考試范圍
樹的定義和基本術(shù)語；二叉樹的定義；二叉樹的性質(zhì)；二叉樹的存儲結(jié)構(gòu)；遍歷
二叉樹；線索二叉樹；樹的存儲結(jié)構(gòu)；森林與二叉樹的轉(zhuǎn)換；樹和森林的遍歷；
最優(yōu)二叉樹（赫夫曼樹）；赫夫曼編碼。
（七）圖
1）基本要求
理解圖的相關(guān)概念、圖的存儲結(jié)構(gòu)；熟練掌握圖的兩種遍歷算法（深度優(yōu)先搜索
遍歷和廣度優(yōu)先搜索遍歷），并能靈活應(yīng)用；熟練掌握求解最小生成樹的算法；
熟練掌握拓?fù)渑判蛩惴ê完P(guān)鍵路徑算法，并能靈活應(yīng)用；熟練掌握最短路徑算法
并能靈活應(yīng)用。
2）考試范圍
圖的定義和術(shù)語；圖的數(shù)組表示法與鄰接表存儲結(jié)構(gòu)；圖的深度優(yōu)先搜索與廣度
優(yōu)先搜索；最小生成樹；拓?fù)渑判?；關(guān)鍵路徑；最短路徑。
（八）查找
1）基本要求
理解查找的相關(guān)概念，理解簡單順序查找、折半查找算法及性能分析；理解二叉
排序樹的定義、特性和查找算法，二叉排序樹的構(gòu)造、插入結(jié)點的算法和刪除結(jié)
點的實現(xiàn)方法；理解平衡二叉樹的定義及構(gòu)造平衡二叉樹的方法；理解Ｂ-樹的
定義、特性和查找方法，理解在Ｂ-樹中插入和刪除關(guān)鍵字的運算實現(xiàn)；理解散
列表結(jié)構(gòu)的相關(guān)概念和構(gòu)造散列函數(shù)的基本方法；理解沖突及其處理的基本方法；
理解哈希查找過程；掌握上述各種查找算法的時間性能分析。
2）考試范圍
順序表的查找；有序表的查找；索引順序表的查找；二叉排序樹和平衡二叉樹；
B-樹和 B+樹；什么是哈希表；哈希函數(shù)的構(gòu)造方法；處理沖突的方法；哈希表
的查找及分析。
（九）內(nèi)部排序
1）基本要求
理解排序的相關(guān)概念；理解直接插入排序、Shell 排序、冒泡排序、快速排序、
簡單選擇排序、堆排序和歸并排序等算法的基本思想、算法實現(xiàn)、時間復(fù)雜度和
空間占用情況，并能根據(jù)具體問題選擇合適的算法。
2）考試范圍
排序概述；插入排序；交換排序；選擇排序；歸并排序；各種內(nèi)部排序方法的分
析比較。
第二部分：操作系統(tǒng)
（一）操作系統(tǒng)引論
1、操作系統(tǒng)的基本概念
1）基本要求
理解操作系統(tǒng)的基本概念、作用和常見操作系統(tǒng)。
2）考試范圍
操作系統(tǒng)的定義、目標(biāo)、在計算機(jī)系統(tǒng)中的地位與作用，主流操作系統(tǒng)概況。
2、操作系統(tǒng)的發(fā)展過程
1）基本要求
理解操作系統(tǒng)的發(fā)展特點，掌握發(fā)展過程中基本操作系統(tǒng)類型特點和其中的一些
關(guān)鍵技術(shù)，理解現(xiàn)代多種操作系統(tǒng)類型特點。
2）考試范圍
脫機(jī)/聯(lián)機(jī) I/O 技術(shù)、多道程序設(shè)計技術(shù)、多道批處理系統(tǒng)、分時系統(tǒng)、實時系
統(tǒng)、微機(jī)操作系統(tǒng)、分布式系統(tǒng)、嵌入式系統(tǒng)。
3、操作系統(tǒng)的功能與結(jié)構(gòu)
1）基本要求
理解操作系統(tǒng)的主要功能及概念，掌握操作系統(tǒng)的特征及其含義，理解操作系統(tǒng)
的各種結(jié)構(gòu)特征。
2）考試范圍
操作系統(tǒng)的主要功能及同步、地址映射、邏輯擴(kuò)充內(nèi)存等基本概念；操作系統(tǒng)的
基本特征；操作系統(tǒng)的結(jié)構(gòu)設(shè)計，微內(nèi)核技術(shù)、內(nèi)核態(tài)與用戶態(tài)。
（二）進(jìn)程管理
1、進(jìn)程的基本概念
1）基本要求
掌握進(jìn)程引入的原因和基本概念，掌握進(jìn)程與程序的不同與特性；掌握進(jìn)程的三
狀態(tài)轉(zhuǎn)換模型，理解掛起狀態(tài)的含義；掌握進(jìn)程控制塊 PCB 的作用和組成，理
解 PCB 的組織方法。
2）考試范圍
程序的順序與并發(fā)執(zhí)行的特點、進(jìn)程的引入、進(jìn)程的概念與特性、進(jìn)程與程序的
比較、進(jìn)程的三狀態(tài)模型、五狀態(tài)模型、掛起狀態(tài)、進(jìn)程控制塊的作用、內(nèi)容與
組織
2、進(jìn)程的控制
1）基本要求
理解和掌握原語的含義、進(jìn)程創(chuàng)建與撤銷的主要工作；了解常見操作系統(tǒng)的進(jìn)程
控制方法
2）考試范圍
原語、進(jìn)程控制方法與過程
3、進(jìn)程同步
1）基本要求
理解進(jìn)程同步要解決的制約關(guān)系，掌握同步處理的基本概念與原則，理解硬件同
步方案的特點，掌握信號量機(jī)制及其解決實際同步問題的方法與實現(xiàn)，掌握管程
機(jī)制的思想與基本概念。
2）考試范圍
進(jìn)程的制約類型、臨界資源、臨界區(qū)、進(jìn)程同步設(shè)計的原則，進(jìn)程同步的硬件方
法、信號量機(jī)制及其應(yīng)用、管程機(jī)制、經(jīng)典進(jìn)程同步問題（生產(chǎn)者消費者問題、
讀者寫者問題、哲學(xué)家就餐問題）。
4、進(jìn)程通信
1）基本要求
掌握進(jìn)程通信的基本概念，理解進(jìn)程通信的基本類型及其特點。
2）考試范圍
進(jìn)程通信的基本概念、進(jìn)程通信的類型、基本進(jìn)程通信類型（共享存儲器、消息
傳遞系統(tǒng)、管道）的實現(xiàn)原理與特點。
5、線程技術(shù)
1）基本要求
掌握線程引入的原因，掌握線程相比進(jìn)程的不同與優(yōu)勢，理解多線程實現(xiàn)的幾種
模型特點，理解多線程技術(shù)的應(yīng)用領(lǐng)域。
2）考試范圍
線程的引入、線程與進(jìn)程的比較、多線程模型、線程技術(shù)的應(yīng)用
（三）處理機(jī)調(diào)度與死鎖
1、處理機(jī)調(diào)度及算法
1）基本要求
掌握處理機(jī)調(diào)度三個層次的主要任務(wù)，掌握調(diào)度算法與方式選擇的原則；掌握多
種調(diào)度算法的 FCFS、SJB、HPF、HRRN、RR、MLFQ 的調(diào)度思想與特點，能熟
練運用上述算法對實際調(diào)度問題進(jìn)行調(diào)度與分析性能。
2）考試范圍
處理機(jī)調(diào)度的層次及任務(wù)、各級調(diào)度算法選擇的準(zhǔn)則，作業(yè)調(diào)度的過程，作業(yè)調(diào)
度算法 FCFS、SJB、HPF（HRRN）的調(diào)度思想與特點，進(jìn)程調(diào)度實現(xiàn)方法，調(diào)
度方式，調(diào)度算法 RR/多級反饋隊列 MLFQ 等的思想與特點。
2、死鎖
1）基本要求
理解和掌握死鎖的基本概念，包括定義、產(chǎn)生原因與必要條件；掌握死鎖預(yù)防的
思想，區(qū)別破壞不同必要條件的資源分配方法；掌握死鎖避免的思想，并熟練使
用銀行家算法進(jìn)行系統(tǒng)安全狀態(tài)判斷與進(jìn)程推進(jìn)控制；理解死鎖檢測與解除的思
想。
2）考試范圍
死鎖的定義、產(chǎn)生原因、必要條件，死鎖的幾種預(yù)防方法，死鎖的避免思想與銀
行家算法，死鎖的檢測和解除方法。
（四）存儲器管理
1、存儲器管理概述
1）基本要求
掌握存儲器管理實現(xiàn)的基本功能，了解程序鏈接與裝入各種方式的特點。
2）考試范圍
存儲器管理的功能、地址重定位、內(nèi)存保護(hù)，程序的鏈接與裝入方式。
2、連續(xù)分配方式
1）基本要求
理解連續(xù)分配方式的思想，了解單一分區(qū)與固定分區(qū)分配的思想與特點；掌握動
態(tài)分區(qū)分配的思想以及功能實現(xiàn)方法，掌握分區(qū)分配出現(xiàn)的碎片問題以及解決方
案。
2）考試范圍
連續(xù)分配方式思想以及單一分區(qū)、固定分區(qū)、動態(tài)分區(qū)分配思想、分配與回收過
程、分配算法、碎片問題及其處理、可重定位分區(qū)分配。
3、離散分配方式
1）基本要求
掌握基本分頁技術(shù)的思想，掌握頁表的內(nèi)容與作用，熟練掌握分頁系統(tǒng)下地址映
射的基本方法；理解分頁技術(shù)下越界與越權(quán)的判定方法，掌握 TLB 的作用以及
性能分析方法；初步掌握多級頁表的思想與基本特點；掌握分段技術(shù)的基本思想，
理解和掌握分段技術(shù)與分頁技術(shù)的異同；初步掌握段頁式存儲管理方案的思想與
地址映射方法。
2）考試范圍
基本分頁技術(shù)的思想、數(shù)據(jù)結(jié)構(gòu)、地址映射方法、存儲保護(hù)、TLB 的引入、多級
頁表及其特點；基本分段技術(shù)的思想、數(shù)據(jù)結(jié)構(gòu)、地址映射方法、存儲保護(hù)；分
段與分頁技術(shù)的對比，段頁式存儲管理方案的思想與實現(xiàn)方法、地址映射過程等。
4、邏輯擴(kuò)充內(nèi)存技術(shù)
1）基本要求
了解覆蓋和交換技術(shù)的思想，掌握程序局部性原理，掌握虛擬存儲技術(shù)的思想與
特點。
2）考試范圍
覆蓋技術(shù)、交換技術(shù)、虛擬存儲技術(shù)。
5、虛擬存儲管理方案
1）基本要求
掌握請求分頁技術(shù)的基本思想，掌握請求分頁方案的頁表設(shè)計，理解缺頁處理方
法與特點，理解請求分頁方案下分配策略、調(diào)入策略的設(shè)計；掌握請求分段技術(shù)
的思想。
2）考試范圍
請求分頁技術(shù)的思想、實現(xiàn)的硬件支持（頁表、缺頁中斷機(jī)構(gòu)、地址映射機(jī)構(gòu)）
和軟件策略設(shè)計（分配策略、調(diào)入策略、調(diào)入時機(jī)）、請求分段技術(shù)的思想。
6、頁面置換算法
1）基本要求
理解頁面置換策略的用途，掌握 OPT、FIFO、CLOCK、LRU、工作集等頁面置
換算法的思想與特點；理解置換性能與抖動現(xiàn)象的影響因素；能熟練運用 OPT、
FIFO、CLOCK、LRU 算法進(jìn)行實際頁面置換問題的解決與性能分析。
2）考試范圍
頁面置換算法概述、OPT、FIFO、CLOCK、LRU、工作集等頁面置換算法思想、
效率與置換性能分析、缺頁率的影響因素、抖動現(xiàn)象及其影響因素。
（五）I/O 系統(tǒng)
1、I/O 系統(tǒng)概述
1）基本要求
理解 I/O 系統(tǒng)的基本功能，理解并掌握 I/O 系統(tǒng)軟件層次的設(shè)計方法；掌握 IO
設(shè)備的范疇與分類，掌握通道的含義與作用。
2）考試范圍
I/O 系統(tǒng)的管理對象、I/O 系統(tǒng)功能、I/O 系統(tǒng)軟件設(shè)計的層次、I/O 設(shè)備基本情
況、分類與特點，設(shè)備控制器的功能與組成、管理方法，通道的基本概念與類型。
2、I/O 中斷與設(shè)備驅(qū)動
1）基本要求
理解中斷技術(shù)的意義，理解中斷技術(shù)的基本概念，掌握中斷處理的方式與過程；
掌握設(shè)備驅(qū)動程序的功能，理解設(shè)備四種 IO 控制方式及特點。
2）考試范圍
中斷技術(shù)的意義、中斷向量表、中斷優(yōu)先級、中斷處理方式、中斷處理過程、設(shè)
備驅(qū)動程序功能與特點、I/O 控制方式及其特點。
3、設(shè)備獨立性與用戶 I/O 層軟件
1）基本要求
掌握設(shè)備獨立性的含義；理解與初步掌握設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)與分配過程；掌握
緩沖技術(shù)的引入原因、思想，理解常見緩沖技術(shù)的思想與特點；掌握 SPOOLing
系統(tǒng)的組成與特點。
2）考試范圍
設(shè)備獨立性層功能，邏輯設(shè)備名與物理設(shè)備名、設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)、分配算法、
方式與分配過程，緩沖技術(shù)的引入原因、常見的軟件緩沖技術(shù)及特點，用戶 I/O
層軟件功能，SPOOLing 技術(shù)。
（六）磁盤
1、磁盤管理
1）基本要求
掌握磁盤的結(jié)構(gòu)和物理地址組成，理解磁盤的訪問過程，掌握四類磁盤調(diào)度算法
的思想與特點；了解提高磁盤可靠性的方法。
2）考試范圍
磁盤結(jié)構(gòu)、磁盤物理地址，磁盤的訪問過程與訪問時間組成，磁盤調(diào)度算法（FCFS、
SSTF、SCAN、CSCAN），磁盤可靠性的 3 級容錯技術(shù)、磁盤陣列。
（七）文件系統(tǒng)
1、文件與文件系統(tǒng)
1）基本要求
理解文件與文件系統(tǒng)的基本概念；掌握文件邏輯結(jié)構(gòu)的類型與特點；掌握文件的
存取方法及其特點；掌握文件的三種物理結(jié)構(gòu)類型與特點；理解目錄結(jié)構(gòu)的功能，
與基本概念，掌握目錄結(jié)構(gòu)的類型與特點，理解目錄結(jié)構(gòu)的改進(jìn)方法。掌握文件
空間管理的位示圖法和成組鏈接法的思想與特點。
2）考試范圍
文件的引入/定義、文件系統(tǒng)的功能及結(jié)構(gòu)、文件的邏輯結(jié)構(gòu)類型及特點、文件
的存取方法及特點、文件的連續(xù)/鏈接（顯式/隱式）/索引結(jié)構(gòu)及其特點，目錄管
理的目標(biāo)、基本概念、目錄結(jié)構(gòu)、目錄的改進(jìn)、索引節(jié)點、基于索引節(jié)點的文件
共享方法、文件空間管理的位示圖法和成組鏈接法的思想與特點。
三、考試形式和試卷結(jié)構(gòu)
1、考試時間和分值
閉卷筆試，考試時間為 180 分鐘，試卷滿分為 150 分。兩門課程各占 75 分。
2、考試題型結(jié)構(gòu)
（1）單項選擇題（27％）：每個問題都只有一個選擇，根據(jù)題目內(nèi)容選擇正確答
案。
（2）填空題（13％）：根據(jù)題目要求，填充對應(yīng)位置的內(nèi)容。
（3）判斷題（7％）：根據(jù)題目內(nèi)容判斷其描述問題的正確性。
（4）應(yīng)用及算法設(shè)計題（53％）：根據(jù)題目內(nèi)容完成相應(yīng)問題的求解，要求給出
具體求解過程。
四、參考書目
《數(shù)據(jù)結(jié)構(gòu)》（C 語言版），嚴(yán)蔚敏，吳偉民主編，清華大學(xué)出版社，2018
《計算機(jī)操作系統(tǒng)》第四版，湯小丹等編著，電子科技大學(xué)出版社，2018
西南石油大學(xué)
添加西南石油大學(xué)學(xué)姐微信，或微信搜索公眾號“考研派小站”，關(guān)注[考研派小站]微信公眾號，在考研派小站微信號輸入[西南石油大學(xué)考研分?jǐn)?shù)線、西南石油大學(xué)報錄比、西南石油大學(xué)考研群、西南石油大學(xué)學(xué)姐微信、西南石油大學(xué)考研真題、西南石油大學(xué)專業(yè)目錄、西南石油大學(xué)排名、西南石油大學(xué)保研、西南石油大學(xué)公眾號、西南石油大學(xué)研究生招生）]即可在手機(jī)上查看相對應(yīng)西南石油大學(xué)考研信息或資源。
.png)
本文來源：
http://alternativeofficeassistance.com/xinanshiyoudaxue/cankaoshumu_374719.html /1.png)
/6.jpg "2021西南石油大學(xué)計算機(jī)學(xué)科綜合專業(yè)研究生參考及考試大綱")
