山東大學2024年考研初試大綱：832計算機綜合

考研專業課大綱對備考具有重要價值。大綱可以幫助考生了解考試的整體結構和考查重點，在備考過程中起到明確方向的作用。大綱所列出的考試范圍和知識要點，可以幫助考生建立知識體系，明確重難點，有針對性地進行備考。同時，弄清大綱要求可以讓考生事先了解復習的時間分配和備考要求，避免在備考過程中盲目浪費時間和精力。以下是山東大學2024年碩士研究生招生考試《832計算機綜合》考試大綱具體內容，報考該校計算機專業相關方向的考生可以根據考試大綱備考。

山東大學碩士研究生招生考試初試科目考試大綱

832-計算機綜合

計算機綜合包括數據結構、計算機組成原理兩部分內容，每部分內容各占1/2。

i 數據結構

一、考試基本要求

要求考生系統地理解線性結構（線性表、數組和矩陣、棧、隊列、跳表和散列表）、樹型結構（森林（樹）、二叉樹、優先隊列、搜索樹）、圖結構等各種主要數據結構的基本概念，掌握各種數據結構的定義、實現算法和應用；掌握基本算法設計方法（遞歸、貪婪算法、分而治之、動態規劃）及應用；掌握程序性能分析方法。要求考生具有抽象思維能力，邏輯推理能力，和綜合運用所學的知識分析問題和解決問題的能力。

二、考試范圍

(一) 預備知識

1. c++基本語法結構和應用

2. 遞歸思想和方法

(二) 程序性能分析

1. 復雜性（時間復雜性和空間復雜性）的表示和計算方法

2. 插入排序、選擇排序、冒泡排序、按名次排序方法

3. 順序搜索、折半搜索方法

(三) 線性表

1. 線性表的數組描述、鏈表描述等存儲方法

2. 線性表的插入、刪除、合并等基本操作實現方法

3. 遍歷器的作用、實現方法和應用

4. 線性表結構應用：箱子排序、基數排序、并查集（在線等價類）等

(四) 數組和矩陣

1. 一般矩陣存儲方法和基本運算實現

2. 特殊矩陣的特征、存儲方法和基本運算實現

3. 稀疏矩陣的存儲方法和基本運算實現

(五) 棧

1. 棧的基本概念、基本操作和實現方法

2. 棧結構應用：括號匹配、列車車廂重排、迷宮老鼠、離線等價類等

(六) 隊列

1. 隊列的基本概念、基本操作和實現方法

2. 隊列結構應用：列車車廂重排、電路布線、圖元識別等

(七) 跳表和散列

1. 字典結構基本概念和表示結構

2. 跳表的基本概念、基本操作和實現方法

3. 散列表的基本概念、基本操作和實現方法

4. lzw壓縮思想

(八) 二叉樹和其他樹

1. 樹（以及森林）和二叉樹的基本概念、存儲方法、常用操作和特性

2. 二叉樹的前序、中序、后序、層次遍歷方法及應用

3. 樹（以及森林）的存儲方法

4. 樹和二叉樹結構的應用：基于樹存儲的并查集（在線等價類）等

(九) 優先隊列

1. 優先隊列基本概念和表示結構

2. 堆結構基本概念，堆的插入、刪除和初始化等操作實現方法

3. 堆結構應用：堆排序、霍夫曼樹、霍夫曼編碼

4. 左高樹基本概念和插入、刪除、合并、初始化等操作的實現思想

(十) 搜索樹

1. 二叉搜索樹(排序樹)基本概念和插入、刪除、搜索等操作的實現方法

2. 二叉平衡樹（avl樹）基本概念和插入、刪除、搜索等操作的實現方法

3. m叉搜索樹和b-樹基本概念以及插入、刪除、搜索等操作的實現方法

(十一) 圖

1. 圖基本概念和特性

2. 圖的鄰接矩陣和鄰接鏈表存儲方法及各種基本操作和實現方法

3. 圖的深度優先搜索（dfs）和廣度優先搜索（bfs）算法

4. dfs/bfs應用：尋找路徑、連通圖及連通構件、生成樹等

(十二) 貪婪算法

1. 貪婪算法基本思想

2.  aov網的拓撲排序算法

3. 單源最短路徑dijkstra算法

4. 最小成本生成樹的概念、prim算法和kruskal算法

5.  aoe網的關鍵路徑算法

(十三) 分而治之

1. 分而治之思想

2. 歸并排序、快速排序方法

3. 選擇問題實現方法

(十四) 動態規劃

1. 動態規劃思想

2. 所有頂點對之間的最短路徑算法

三、參考文獻

(一) 《數據結構，算法與應用----c++語言描述》（原書第2版），sartaj sahni 著  王立柱，劉志紅譯 ，機械工業出版社 2015年出版

(二) 《數據結構》（用面向對象方法與c++語言描述 第二版） 殷人昆 著 清華大學出版社

ii 計算機組成原理

一、 課程基本要求

(一)理解單處理器計算機系統中各部件的內部工作原理、組成結構以及相互連接方式，具有完整的計算機系統的整機概念；

(二)理解計算機系統層次化結構概念，熟悉硬件與軟件之間的界面，掌握指令集體系結構的基本知識和基本實現方法；

(三)能夠綜合運用計算機組成的基本原理和基本方法，對有關計算機硬件系統中的理論和實際問題進行計算、分析，對一些基本部件進行簡單設計，并能對高級程序設計語言(如c語言)中的相關問題進行分析。

(四)

二、 考試范圍

(一) 計算機系統概述

1.計算機發展歷程

2.計算機系統層次結構

（1）計算機系統的基本組成

（2）計算機硬件的基本組成

（3）計算機軟件的分類

（4）計算機的工作過程

3.計算機性能指標

（1）cpu時鐘周期、主頻、cpi、cpu執行時間、mips、mflops

（2）字長

（3）容量

（4）總線寬度

(二) 數據的表示和運算

1.數制與編碼

（1）進位計數制及其相互轉換

（2）真值和機器數

（3）bcd碼

（4）字符與字符串

（5）校驗碼

2.定點數的表示和運算

（1）定點數的表示

無符號數的表示及范圍；有符號數的表示及其相互轉換。

（2）定點數的運算

定點數的移位運算；補碼定點數的加/減運算；定點數的乘/除運算；溢出概念和判別方法。

3.浮點數的表示和運算

（1）浮點數的表示

浮點數的表示范圍；浮點機器數與真值間的相互轉換。

（2）浮點數的加/減運算

4.算術邏輯單元alu

（1）并行加法器

（2）算術邏輯單元alu的功能和結構

（3）快速進位鏈設計原理

(三) 存儲器層次機構

1.存儲器的分類

2.存儲器的層次化結構

3.半導體隨機存取存儲器

（1）sram存儲器的工作原理

（2）dram存儲器的工作原理；刷新方式。

（3）只讀存儲器、flash存儲器

（4）主存儲器的基本組成、存儲單元的屬性、數據的存放模式

（5）存儲器的技術指標

4.存儲器的擴展方式及存儲器與cpu的連接

5.多體并行存儲器系統

6.高速緩沖存儲器（cache）

（1）cache的基本工作原理

（2）cache和主存之間的映射方式及其地址轉換

（3）cache中主存塊的替換算法

（4）cache讀、寫策略

(四) 指令系統

1.指令格式

（1）指令的基本格式

（2）定長操作碼指令格式

（3）擴展操作碼指令格式

2.指令的尋址方式

（1）有效地址的概念

（2）數據尋址和指令尋址

（3）常見尋址方式

3.cisc和risc的基本概念

(五) 中央處理器（cpu）

1.cpu的功能和基本結構

2.指令執行過程

3.數據通路的功能和基本結構

基于數據通路，指令周期流程及取指、間址、執行和中斷周期的數據流。

4.控制器的功能和工作原理

（1）微操作命令的分析

取指周期、間址周期、執行周期和中斷周期的微操作命令及其節拍安排。

（2）組合邏輯（硬布線）控制器

組合邏輯控制器的組成結構、設計步驟。

（3）微程序控制器

微程序、微指令、微命令、微操作、控制存儲器的基本概念；

微程序控制器的設計思想、組成結構、工作原理；

微指令的編碼方式；

微地址的形式方式。

5.指令流水線

（1）指令流水線的基本概念

（2）指令流水線的基本實現

影響指令流水線性能的因素：結構相關、數據相關、控制相關；

流水線的主要性能：吞吐率、加速比、效率。

（3）流水線的多發技術

超標量處理機、超流水線處理機、超長指令字處理機的基本概念。

(六) 總線

1.總線概述

（1）總線的基本概念

（2）總線的分類

（3）總線的組成及性能指標

2.總線仲裁

（1）集中仲裁方式

（2）分布仲裁方式

3.總線操作和定時

（1）同步定時方式

（2）異步定時方式

4.總線標準

(七) 輸入輸出（i/o）系統

1.i/o系統基本概念

2.i/o接口（i/o控制器）

（1）i/o接口的功能和基本結構

（2）i/o端口及其編址

3.i/o方式

（1）程序查詢方式

（2）程序中斷方式

中斷的基本概念；中斷響應過程；中斷處理過程；多重中斷和中斷屏蔽的概念；中斷處理順序。

（3）dma方式

dma控制器的組成；dma傳送過程。

（4）通道方式

（5）

三、參考書目

計算機組成原理（第3版），高等教育出版社，2020.10，十二五”普通高等教育本科國家級規劃教材。

計算機組成原理（第6版），科學出版社，2019.8，十二五”普通高等教育本科國家級規劃教材。

原文鏈接：https://www.yz.sdu.edu.cn/info/1024/5678.htm