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