北京交通大學(xué)

自2022研究生招生年度起，原自命題業(yè)務(wù)課科目923“操作系統(tǒng)原理”、925“數(shù)據(jù)結(jié)構(gòu)”合并為“計算機(jī)專業(yè)基礎(chǔ)”。新科目“計算機(jī)專業(yè)基礎(chǔ)”適用于081200計算機(jī)科學(xué)與技術(shù)、083500軟件工程、083900網(wǎng)絡(luò)空間安全、081000信息與通信工程、081100控制科學(xué)與工程、085400電子信息等專業(yè)。905“信號與系統(tǒng)”科目保留，不做調(diào)整。我院自命題(業(yè)務(wù)課2)適用專業(yè)詳見下表。

我院自命題(業(yè)務(wù)課2)適用專業(yè)一覽表

注：招生專業(yè)、方向及科目設(shè)置以北京交通大學(xué)2022年碩士招生專業(yè)目錄實際公布為準(zhǔn)。

2022年碩士研究生招生預(yù)計2021年10月份開始網(wǎng)上報名，為指導(dǎo)廣大考生復(fù)習(xí)備考，現(xiàn)將“計算機(jī)專業(yè)基礎(chǔ)”科目的考試大綱公布如下：

計算機(jī)專業(yè)基礎(chǔ)考試大綱：

一、數(shù)據(jù)結(jié)構(gòu)(90分)

1、緒論。(1)掌握相關(guān)的基本概念，如數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型等;(2)掌握算法設(shè)計的原則，掌握計算語句頻度和估算算法時間復(fù)雜度和空間復(fù)雜度的方法;(3)了解使用類C語言描述算法的方法。

2、線性表。(1)掌握線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu);(2)掌握線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)基本操作的方法;(3)理解線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合，會針對需求選用合適的存儲結(jié)構(gòu)解決實際問題;(4)了解一元多項式的表示方法和基本運算的實現(xiàn)方法。

3、棧和隊列。(1)了解棧和隊列的特點;(2)掌握在兩種存儲結(jié)構(gòu)上棧的基本操作的實現(xiàn);(3)掌握棧的各種應(yīng)用，理解遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程;(4)掌握循環(huán)隊列和鏈隊列的基本運算;(5)會應(yīng)用隊列結(jié)構(gòu)解決實際問題。

4、串。(1)掌握串的基本運算的定義，了解利用基本運算來實現(xiàn)串的其它運算的方法;(2)了解在順序存儲結(jié)構(gòu)和在堆存儲結(jié)構(gòu)以及塊鏈存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法;(3)理解KMP算法，掌握NEXT函數(shù)和改進(jìn)NEXT函數(shù)的定義和計算。

5、數(shù)組和廣義表。(1)掌握數(shù)組在以行為主和以列為主的存儲結(jié)構(gòu)中的地址計算方法;(2)掌握矩陣壓縮存儲時的下標(biāo)變換方法，了解以三元組表示稀疏矩陣的方法;(3)理解廣義表的定義及其存儲結(jié)構(gòu)，理解廣義表的頭尾和子表兩種分析方法。

6、樹和二叉樹。(1)熟練掌握二叉樹的結(jié)構(gòu)特點和性質(zhì)，掌握二叉樹各種存儲結(jié)構(gòu)及構(gòu)建方法;(2)掌握按先序、中序、后序和層次次序遍歷二叉樹的算法，理解二叉樹的線索化實質(zhì)和方法;(3)利用二叉樹的遍歷求解實際問題;(3)掌握樹的各種存儲結(jié)構(gòu)及其特點，掌握樹的各種運算的實現(xiàn)算法;(4)掌握建立最優(yōu)二叉樹和哈夫曼編碼的方法。

7、圖。(1)熟練掌握圖的基本概念，會構(gòu)建各種圖的存儲結(jié)構(gòu);(2)掌握深度優(yōu)先搜索遍歷圖和廣度優(yōu)先搜索遍歷圖的算法;(3)靈活運用圖的遍歷算法求解各種路徑問題，包括最小生成樹﹑最短路徑﹑拓?fù)渑判颟p關(guān)鍵路徑等。

8、查找。(1)熟練掌握各種靜態(tài)查找和動態(tài)查找算法，會計算查找成功時和失敗時的平均查找長度;(2)掌握二叉排序樹的建立、插入和刪除過程，掌握二叉平衡樹的建立和旋轉(zhuǎn)平衡方法;(3)掌握B-樹的建立、插入和刪除結(jié)點的過程;(4)熟練掌握哈希表的構(gòu)造方法和處理沖突的方法。

9、排序。(1)掌握各種排序算法，包括插入類、交換類、選擇類、歸并類排序及基數(shù)排序;(2)能夠?qū)Ω鞣N排序方法進(jìn)行比較分析，如穩(wěn)定性、時間和空間性能等，了解各種排序方法的特點和不同并靈活應(yīng)用。

二、操作系統(tǒng)原理(60分)

1、引論。(1)要求理解的內(nèi)容包括：操作系統(tǒng)的概念、設(shè)計目標(biāo)、功能及特征，操作系統(tǒng)運行硬件基礎(chǔ)，操作系統(tǒng)接口分類及組成，操作系統(tǒng)內(nèi)核用典型數(shù)據(jù)結(jié)構(gòu);(2)要求掌握的內(nèi)容包括：系統(tǒng)調(diào)用實現(xiàn)機(jī)制，操作系統(tǒng)啟動引導(dǎo)過程。

2、處理機(jī)管理。(1)要求理解的內(nèi)容包括：多道程序設(shè)計技術(shù)，程序、進(jìn)程、線程的區(qū)別與聯(lián)系，線程實現(xiàn)方式，進(jìn)程狀態(tài)變遷，進(jìn)程控制，處理機(jī)調(diào)度類型與模型，處理機(jī)調(diào)度實現(xiàn)機(jī)理，調(diào)度算法與評價準(zhǔn)則;(2)要求掌握的內(nèi)容包括：處理機(jī)主要調(diào)度算法設(shè)計實現(xiàn)及應(yīng)用。

3、同步通信及死鎖處理。(1)要求理解的內(nèi)容包括：進(jìn)程同步基本準(zhǔn)則，進(jìn)程同步軟硬件解決方案，整型信號量、記錄型信號量、管程，經(jīng)典同步問題，進(jìn)程通信機(jī)制，線程同步機(jī)制，死鎖及處理方法;(2)要求掌握的內(nèi)容包括：利用記錄型信號量解決同步問題，利用銀行家算法給出避免死鎖的資源分配方案，死鎖檢測算法及應(yīng)用。

4、存儲管理。(1)要求理解的內(nèi)容包括：程序處理與內(nèi)存管理，分區(qū)存儲管理及相關(guān)技術(shù)(拼湊、覆蓋、對換、伙伴系統(tǒng))，分頁/分段/段頁式存儲管理，虛擬存儲技術(shù)，請求分頁/分段存儲管理，多級頁表和反置頁表，內(nèi)存保護(hù)機(jī)制;(2)要求掌握的內(nèi)容包括：分頁/分段地址變換，頁面淘汰算法設(shè)計實現(xiàn)及應(yīng)用，請求分頁/分段地址變換，動態(tài)分區(qū)存儲管理設(shè)計與實現(xiàn)。

5、設(shè)備管理。(1)要求理解的內(nèi)容包括：I/O系統(tǒng)組成及I/O控制方式，設(shè)備管理目標(biāo)、功能及層次結(jié)構(gòu)，緩沖管理，設(shè)備分配及假脫機(jī)技術(shù)，設(shè)備驅(qū)動及中斷處理，磁盤存儲器管理方法與技術(shù);(2)要求掌握的內(nèi)容包括：磁盤調(diào)度算法設(shè)計及應(yīng)用，磁盤數(shù)據(jù)訪問過程及時間開銷。

6、文件管理。(1)要求理解的內(nèi)容包括：文件及典型存取操作邏輯流程，文件系統(tǒng)層次模型，文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，外存空間管理方法，文件目錄結(jié)構(gòu)及管理，文件共享與保護(hù)，磁盤容錯技術(shù)，文件系統(tǒng)性能改善策略及數(shù)據(jù)一致性控制;(2)要求掌握的內(nèi)容包括：目錄檢索過程，文件數(shù)據(jù)訪問基本過程，F(xiàn)AT文件系統(tǒng)設(shè)計實現(xiàn)。

7、操作系統(tǒng)發(fā)展與演化。要求理解的內(nèi)容包括：批處理、分時和實時系統(tǒng)的概念，操作系統(tǒng)結(jié)構(gòu)設(shè)計及演化，操作系統(tǒng)發(fā)展趨勢。