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