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

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

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

832-計算機綜合

計算機綜合包括數(shù)據(jù)結(jié)構(gòu)、計算機組成原理兩部分內(nèi)容，每部分內(nèi)容各占1/2。

i 數(shù)據(jù)結(jié)構(gòu)

一、考試基本要求

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

二、考試范圍

(一) 預(yù)備知識

1. c++基本語法結(jié)構(gòu)和應(yīng)用

2. 遞歸思想和方法

(二) 程序性能分析

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

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

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

(三) 線性表

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

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

3. 遍歷器的作用、實現(xiàn)方法和應(yīng)用

4. 線性表結(jié)構(gòu)應(yīng)用：箱子排序、基數(shù)排序、并查集（在線等價類）等

(四) 數(shù)組和矩陣

1. 一般矩陣存儲方法和基本運算實現(xiàn)

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

3. 稀疏矩陣的存儲方法和基本運算實現(xiàn)

(五) 棧

1. 棧的基本概念、基本操作和實現(xiàn)方法

2. 棧結(jié)構(gòu)應(yīng)用：括號匹配、列車車廂重排、迷宮老鼠、離線等價類等

(六) 隊列

1. 隊列的基本概念、基本操作和實現(xiàn)方法

2. 隊列結(jié)構(gòu)應(yīng)用：列車車廂重排、電路布線、圖元識別等

(七) 跳表和散列

1. 字典結(jié)構(gòu)基本概念和表示結(jié)構(gòu)

2. 跳表的基本概念、基本操作和實現(xiàn)方法

3. 散列表的基本概念、基本操作和實現(xiàn)方法

4. lzw壓縮思想

(八) 二叉樹和其他樹

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

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

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

4. 樹和二叉樹結(jié)構(gòu)的應(yīng)用：基于樹存儲的并查集（在線等價類）等

(九) 優(yōu)先隊列

1. 優(yōu)先隊列基本概念和表示結(jié)構(gòu)

2. 堆結(jié)構(gòu)基本概念，堆的插入、刪除和初始化等操作實現(xiàn)方法

3. 堆結(jié)構(gòu)應(yīng)用：堆排序、霍夫曼樹、霍夫曼編碼

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

(十) 搜索樹

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

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

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

(十一) 圖

1. 圖基本概念和特性

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

3. 圖的深度優(yōu)先搜索（dfs）和廣度優(yōu)先搜索（bfs）算法

4. dfs/bfs應(yīng)用：尋找路徑、連通圖及連通構(gòu)件、生成樹等

(十二) 貪婪算法

1. 貪婪算法基本思想

2.  aov網(wǎng)的拓?fù)渑判蛩惴?/p>

3. 單源最短路徑dijkstra算法

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

5.  aoe網(wǎng)的關(guān)鍵路徑算法

(十三) 分而治之

1. 分而治之思想

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

3. 選擇問題實現(xiàn)方法

(十四) 動態(tài)規(guī)劃

1. 動態(tài)規(guī)劃思想

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

三、參考文獻(xiàn)

(一) 《數(shù)據(jù)結(jié)構(gòu)，算法與應(yīng)用----c++語言描述》（原書第2版），sartaj sahni 著  王立柱，劉志紅譯 ，機械工業(yè)出版社 2015年出版

(二) 《數(shù)據(jù)結(jié)構(gòu)》（用面向?qū)ο蠓椒ㄅcc++語言描述 第二版） 殷人昆 著 清華大學(xué)出版社

ii 計算機組成原理

一、 課程基本要求

(一)理解單處理器計算機系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計算機系統(tǒng)的整機概念；

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

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

(四)

二、 考試范圍

(一) 計算機系統(tǒng)概述

1.計算機發(fā)展歷程

2.計算機系統(tǒng)層次結(jié)構(gòu)

（1）計算機系統(tǒng)的基本組成

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

（3）計算機軟件的分類

（4）計算機的工作過程

3.計算機性能指標(biāo)

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

（2）字長

（3）容量

（4）總線寬度

(二) 數(shù)據(jù)的表示和運算

1.數(shù)制與編碼

（1）進(jìn)位計數(shù)制及其相互轉(zhuǎn)換

（2）真值和機器數(shù)

（3）bcd碼

（4）字符與字符串

（5）校驗碼

2.定點數(shù)的表示和運算

（1）定點數(shù)的表示

無符號數(shù)的表示及范圍；有符號數(shù)的表示及其相互轉(zhuǎn)換。

（2）定點數(shù)的運算

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

3.浮點數(shù)的表示和運算

（1）浮點數(shù)的表示

浮點數(shù)的表示范圍；浮點機器數(shù)與真值間的相互轉(zhuǎn)換。

（2）浮點數(shù)的加/減運算

4.算術(shù)邏輯單元alu

（1）并行加法器

（2）算術(shù)邏輯單元alu的功能和結(jié)構(gòu)

（3）快速進(jìn)位鏈設(shè)計原理

(三) 存儲器層次機構(gòu)

1.存儲器的分類

2.存儲器的層次化結(jié)構(gòu)

3.半導(dǎo)體隨機存取存儲器

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

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

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

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

（5）存儲器的技術(shù)指標(biāo)

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

5.多體并行存儲器系統(tǒng)

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

（1）cache的基本工作原理

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

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

（4）cache讀、寫策略

(四) 指令系統(tǒng)

1.指令格式

（1）指令的基本格式

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

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

2.指令的尋址方式

（1）有效地址的概念

（2）數(shù)據(jù)尋址和指令尋址

（3）常見尋址方式

3.cisc和risc的基本概念

(五) 中央處理器（cpu）

1.cpu的功能和基本結(jié)構(gòu)

2.指令執(zhí)行過程

3.數(shù)據(jù)通路的功能和基本結(jié)構(gòu)

基于數(shù)據(jù)通路，指令周期流程及取指、間址、執(zhí)行和中斷周期的數(shù)據(jù)流。

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

（1）微操作命令的分析

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

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

組合邏輯控制器的組成結(jié)構(gòu)、設(shè)計步驟。

（3）微程序控制器

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

微程序控制器的設(shè)計思想、組成結(jié)構(gòu)、工作原理；

微指令的編碼方式；

微地址的形式方式。

5.指令流水線

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

（2）指令流水線的基本實現(xiàn)

影響指令流水線性能的因素：結(jié)構(gòu)相關(guān)、數(shù)據(jù)相關(guān)、控制相關(guān)；

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

（3）流水線的多發(fā)技術(shù)

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

(六) 總線

1.總線概述

（1）總線的基本概念

（2）總線的分類

（3）總線的組成及性能指標(biāo)

2.總線仲裁

（1）集中仲裁方式

（2）分布仲裁方式

3.總線操作和定時

（1）同步定時方式

（2）異步定時方式

4.總線標(biāo)準(zhǔn)

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

1.i/o系統(tǒng)基本概念

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

（1）i/o接口的功能和基本結(jié)構(gòu)

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

3.i/o方式

（1）程序查詢方式

（2）程序中斷方式

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

（3）dma方式

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

（4）通道方式

（5）

三、參考書目

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

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

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