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