2023年北京化工大學計算機科學與技術(shù)考研844考試大綱

考試大綱的內(nèi)容一般包括當年全國研究生入學考試相應(yīng)科目的考試范圍、考試要求、考試形式、試卷結(jié)構(gòu)等信息，對考生備考至關(guān)重要。希賽網(wǎng)整理了2023年北京化工大學計算機科學與技術(shù)（081200）考研844計算機學科專業(yè)基礎(chǔ)綜合考試大綱信息，希望對考生備考有所幫助。

相關(guān)閱讀推薦>>>2021-2022年全國考研復試線丨2023年全國考試科目匯總丨2023年全國研究方向匯總

（注：以下信息來自學院官網(wǎng)，僅供參考，具體內(nèi)容以院校發(fā)布為準）

844 計算機學科專業(yè)基礎(chǔ)綜合一初試考試大綱

1 考查目標

?

計算機學科專業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)結(jié)構(gòu)、計算機組成原理、操作系統(tǒng)等學科專業(yè)基礎(chǔ)課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實際問題。

2 考試形式和試卷結(jié)構(gòu) 

2.1 試卷滿分及考試時間

本試卷滿分為 150 分，考試時間為 180 分鐘。

2.2 答題方式

答題方式為閉卷、筆試。

2.3 試卷結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)約占 80 分

計算機組成原理約占 35 分

操作系統(tǒng)原理約占 35 分 

2.4 試卷題型

單項選擇題 44 分(每題 2 分)，綜合應(yīng)用題 106 分 

3 考試大綱與主要參考書 

3.1 《數(shù)據(jù)結(jié)構(gòu)》 

3.1.1 考試的基本要求 

1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。 

2.掌握基本數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行基本的時間復雜度與空間復雜度分析。 

3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進問題求解，具備采用C 或C++或JAVA語言設(shè)計與實現(xiàn)算法的能力。 

3.1.2 考試的主要內(nèi)容與要求 

1、數(shù)據(jù)結(jié)構(gòu)和算法的基本概念

了解數(shù)據(jù)結(jié)構(gòu)的基本概念，包括邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的基本概念、兩者之間的區(qū)別與聯(lián)系。

了解算法的基本概念和性質(zhì)。了解算法復雜度的基本概念，掌握對非遞歸代碼的復雜度的計算基本方法。

2、線性表

了解線性表的邏輯結(jié)構(gòu)定義。

掌握線性表的順序結(jié)構(gòu)實現(xiàn)，以及順序結(jié)構(gòu)下基本操作的實現(xiàn)，能寫出操作代碼。掌握線性表的鏈式結(jié)構(gòu)實現(xiàn)，以及鏈式結(jié)構(gòu)下基本操作的實現(xiàn)，能寫出操作代碼。能夠設(shè)計針對順序結(jié)構(gòu)和鏈式結(jié)構(gòu)線性表的一般應(yīng)用問題的算法，能寫出算法代碼。掌握棧的基本概念、棧的性質(zhì)。

掌握棧的順序結(jié)構(gòu)和鏈式結(jié)構(gòu)實現(xiàn)，以及相應(yīng)操作的實現(xiàn)，能夠?qū)懗霾僮鞔a。了解棧與遞歸的關(guān)系，能夠編寫遞歸算法，能夠?qū)⑦f歸算法轉(zhuǎn)換為非遞歸形式。掌握隊列的基本概念和性質(zhì)。

掌握隊列的順序結(jié)構(gòu)和鏈式結(jié)構(gòu)實現(xiàn)，以及相應(yīng)操作的實現(xiàn)，能寫出操作代碼。掌握棧和隊列的應(yīng)用方法，能夠運用棧和隊列解決相關(guān)問題，能寫出算法代碼。掌握串的基本操作實現(xiàn)，能寫出算法代碼。掌握串的樸素模式匹配算法和 KMP 模式匹配算法，能手工計算KMP 算法中的nextval向量，能寫出算法代碼。掌握稀疏矩陣的三元組表存儲方法以及基于三元組表結(jié)構(gòu)的快遞轉(zhuǎn)置算法，能寫出算法代碼。 

 3、樹和二叉樹

了解樹的定義和性質(zhì)。

了解二叉樹的概念。

掌握二叉樹的基本性質(zhì)，并能夠進行描述和證明。(包括深度與最大結(jié)點數(shù)的關(guān)系性質(zhì)、每層最大結(jié)點數(shù)性質(zhì)、結(jié)點數(shù)與最小深度的關(guān)系性質(zhì)、n2=n0-1 性質(zhì)、完全二叉樹序號與結(jié)點關(guān)系性質(zhì)等)

掌握二叉樹的二叉鏈結(jié)構(gòu)的實現(xiàn)。

掌握二叉樹的前序遍歷、中序遍歷、后序遍歷和層次遍歷規(guī)則，能夠手工計算二叉樹的遍歷序。

掌握二叉樹的遍歷性質(zhì)，能夠根據(jù)前序+中序或中序+后序還原出二叉樹，并能寫出還原算法代碼。

掌握二叉樹的前序、中序和后序遞歸遍歷算法，能寫出算法代碼。了解線索化二叉樹的概念。

了解哈夫曼樹的概念。掌握哈夫曼算法的思想和步驟，能夠手工計算哈夫曼樹，能寫出算法代碼。

了解哈夫曼編碼的概念，能夠手工計算哈夫曼編碼。了解樹、森林和二叉樹的關(guān)系。能夠解決一般性的二叉樹應(yīng)用問題，設(shè)計算法并寫出算法代碼。

4、圖

了解圖的定義。

掌握圖的鄰接矩陣、鄰接表的實現(xiàn)方法。

掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，能夠手工計算圖的深度優(yōu)先遍歷序和廣度優(yōu)先遍歷序，能寫出算法代碼。

掌握最小生成樹計算(Prim 算法和 Kruskal 算法)，能夠進行手工計算，能寫出算法代碼。

掌握最小生成樹的 MST 性質(zhì)，能夠進行描述和證明。

掌握拓撲排序和關(guān)鍵路徑問題的求解算法，能夠進行手工計算，能寫出算法代碼。

掌握單源起點最短路徑算法(Dijkstra 算法)和任兩點間最短路徑算法(Floyd算法)，能夠進行手工計算，能寫出算法代碼。 

 5、查找

掌握靜態(tài)表的概念和折半查找算法，能夠進行手工計算，能寫出算法代碼。

掌握散列表的基本概念，散列函數(shù)的基本設(shè)計技巧。掌握二叉排序樹的概念，以及二叉排序樹上的查找、插入、刪除算法，能夠進行手工計算，能寫出算法代碼。

掌握平衡二叉樹的概念，以及平衡二叉樹的插入和調(diào)整算法，能夠進行手工計算。了解 B-、B+樹的概念，以及 B-樹的插入和刪除算法。

6、內(nèi)排序

掌握簡單選擇排序、直接插入排序、交換排序、希爾排序、快速排序、堆排序、二路歸并排序、基數(shù)排序的算法思想和步驟，能夠?qū)懗雠判蜻^程，能寫出算法代碼。

了解各種排序方法的特點，能夠針對特定問題背景選擇適當?shù)呐判蚍椒ā?/p>

3.1.3 主要參考書

嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)(C 語言版).北京：清華大學出版社，2020 

3.2 《計算機組成原理》 

3.2.1 考試的基本要求 

1.掌握馮諾依曼架構(gòu)中主要部件的基本分類、工作原理、組成結(jié)構(gòu)以及相互連接方式。 

2.掌握指令集體系結(jié)構(gòu)的基本知識和工作原理，對指令工作流程和相關(guān)硬件結(jié)構(gòu)進行分析。 

3.理解計算機系統(tǒng)的整機概念，能夠綜合運用計算機組成的基本原理和基本方法，對高級編程語言程序中的相關(guān)問題進行分析，具備軟硬件協(xié)調(diào)分析和設(shè)計能力。

3.2.2 考試的主要內(nèi)容與要求 

1、計算機系統(tǒng)概述掌握計算機系統(tǒng)層次結(jié)構(gòu)、基本組成、硬件與軟件的關(guān)系。掌握計算機性能的評價指標。 

2、運算方法與運算器掌握 IEEE754 的基本概念和表示方法;了解數(shù)據(jù)與文字的表示方法和編碼方式。掌握定點、浮點數(shù)的加減運算;了解定點數(shù)的乘法運算。掌握 ALU 基本結(jié)構(gòu)與工作原理;理解行波進位加法器、先行進位加法器的基本概念。

3、層次結(jié)構(gòu)存儲器理解存儲器的層次結(jié)構(gòu)與分類;掌握內(nèi)存的基本概念和工作原理。掌握半導體存儲器的分類、特點、應(yīng)用場景;理解半導體存儲器的基本結(jié)構(gòu)和工作原理。理解磁盤的基本結(jié)構(gòu)與工作原理;了解固態(tài)硬盤和光盤的基本結(jié)構(gòu)與工作原理。掌握 Cache 基本概念;理解 Cache 與主存的映射方式、替換算法、寫策略。了解虛擬存儲器的基本概念和原理。 

 4、指令系統(tǒng)理解指令系統(tǒng)的基本概念、格式、尋址方式;理解 CISC 和RISC 的基本概念和應(yīng)用場景。 

5、中央處理器掌握 CPU 的主要功能、基本結(jié)構(gòu)、工作原理、主要寄存器。掌握計算機中不同周期的關(guān)系與區(qū)別;理解 CPU 數(shù)據(jù)通路的基本結(jié)構(gòu)和指令執(zhí)行過程。理解微程序控制器的基本結(jié)構(gòu)與工作原理;了解硬布線控制器的基本概念;了解時序信號的基本概念。理解流水線的基本概念、分類、相關(guān)問題;了解超標量的基本概念。 

 6、總線掌握總線的基本概念、性能指標和常見總線標準;理解總線的連接方式和仲裁方式。了解總線的同步定時方式和異步定時方式。 

7、輸入輸出系統(tǒng)掌握 I/O 系統(tǒng)基本概念和 I/O 設(shè)備分類;理解 I/O 接口的功能和基本結(jié)構(gòu)。理解基本 I/O 方式的基本概念和工作原理。 

3.2.3 主要參考書

白中英，戴志濤.計算機組成原理(第六版).北京：科學出版社，2019 

3.3 《操作系統(tǒng)原理》 

3.3.1 基本要求 

1、 掌握操作系統(tǒng)相關(guān)的基礎(chǔ)知識和基本原理，理解操作系統(tǒng)的整體運行過程。

2、 掌握操作系統(tǒng)各關(guān)鍵模塊的策略、核心算法、機制及相互關(guān)系。

3、 能夠運用所學的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題，并能利用C語言描述相關(guān)算法。 

3.3.2 考試的主要內(nèi)容與要求 

1、操作系統(tǒng)概述操作系統(tǒng)的概念、特征、功能和提供的服務(wù);操作系統(tǒng)的發(fā)展與分類。理解操作系統(tǒng)的概念及其在計算機系統(tǒng)中的地位。理解現(xiàn)代操作系統(tǒng)的基本組成。了解操作系統(tǒng)的發(fā)展歷史及分類。了解主流操作系統(tǒng)的各自特征、優(yōu)缺點及發(fā)展趨勢。理解操作系統(tǒng)發(fā)展中的各典型結(jié)構(gòu)。 

 2、進程管理理解進程的概念，與程序、線程的關(guān)系與區(qū)別。理解進程和線程模型，能夠理解操作系統(tǒng)中的進程實現(xiàn)和管理方式。深刻理解進程的各種狀態(tài)及狀態(tài)轉(zhuǎn)換過程。理解進程間通信的原因和主要模式。理解臨界區(qū)、臨界資源和互斥的概念及產(chǎn)生原因。理解同步準則及實現(xiàn)互斥的軟硬件方法。理解信號量的概念，理解記錄型信號量和信號量集等不同信號量類型。深度理解各種經(jīng)典同步問題及其變形問題的實現(xiàn)。理解進程調(diào)度的概念和層次，熟練掌握典型的調(diào)度算法理解實時調(diào)度的基本概念和算法。理解死鎖的概念、死鎖原理、死鎖形成的必要條件。以及死鎖的預防、避免、檢測與解除方法。理解系統(tǒng)安全狀態(tài)的概念;熟練掌握銀行家算法的基本原理及應(yīng)用。

3、內(nèi)存管理了解內(nèi)存管理的概念和功能、程序的裝入與鏈接。理解內(nèi)存交換與內(nèi)存覆蓋。掌握連續(xù)分配內(nèi)存管理方式，固定分區(qū)分配算法等。掌握離散分配內(nèi)存管理方式，理解內(nèi)存分頁的原理并掌握物理塊、頁內(nèi)偏移、地址變換等概念。理解虛擬存儲器的概念和工作原理。理解缺頁中斷的概念和原理。理解頁表的作用與組成，多級頁表、反置頁表的工作原理。理解快表的作用與原理。熟練掌握常見的頁面置換算法。理解有效訪問時間問題、工作集模型、抖動的概念與產(chǎn)生原因。理解內(nèi)存分段管理的原理和方法，掌握段頁式管理內(nèi)存的特點。了解存儲保護問題：共享和保護的含義和基本方法。

4、文件管理了解文件的概念、文件系統(tǒng)的概念、文件系統(tǒng)的層次結(jié)構(gòu)。掌握文件的邏輯組織。掌握目錄的管理，索引結(jié)點的概念等。掌握常見的外存分配方法。掌握外存磁盤介質(zhì)的基本特點、磁盤調(diào)度算法等。掌握空閑存儲空間管理的方法(位示圖、成組鏈接法等)。了解文件共享和文件保護的基本方法，掌握文件保護域和文件存取控制表的使用及轉(zhuǎn)換。 

 5、輸入輸出(I/O)管理了解I/O系統(tǒng)基本概念、I/O軟件層次結(jié)構(gòu)。了解設(shè)備控制器、設(shè)備驅(qū)動程序、設(shè)備無關(guān)性等概念。掌握I/O控制方式的演變。掌握緩沖管理基本技術(shù)。掌握設(shè)備分配與回收的技術(shù)。掌握假脫機技術(shù)(SPOOLing)。 3.3.3 主要參考書湯小丹，計算機操作系統(tǒng)(第四版)，西安電子科技大學出版社，西安,2018.10

數(shù)據(jù)來源：北京化工大學研究入學考試計算機學科專業(yè)基礎(chǔ)綜合考試大綱