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

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

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

832-計(jì)算機(jī)綜合

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

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

一、考試基本要求

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

二、考試范圍

(一) 預(yù)備知識

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

2. 遞歸思想和方法

(二) 程序性能分析

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

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

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

(三) 線性表

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

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

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

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

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

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

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

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

(五) 棧

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

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

(六) 隊(duì)列

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

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

(七) 跳表和散列

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

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

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

4. lzw壓縮思想

(八) 二叉樹和其他樹

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

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

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

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

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

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

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

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

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

(十) 搜索樹

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

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

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

(十一) 圖

1. 圖基本概念和特性

2. 圖的鄰接矩陣和鄰接鏈表存儲方法及各種基本操作和實(shí)現(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. 選擇問題實(shí)現(xiàn)方法

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

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

2. 所有頂點(diǎn)對之間的最短路徑算法

三、參考文獻(xiàn)

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

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

ii 計(jì)算機(jī)組成原理

一、 課程基本要求

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

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

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

(四)

二、 考試范圍

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

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

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

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

（2）計(jì)算機(jī)硬件的基本組成

（3）計(jì)算機(jī)軟件的分類

（4）計(jì)算機(jī)的工作過程

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

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

（2）字長

（3）容量

（4）總線寬度

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

1.數(shù)制與編碼

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

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

（3）bcd碼

（4）字符與字符串

（5）校驗(yàn)碼

2.定點(diǎn)數(shù)的表示和運(yùn)算

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

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

（2）定點(diǎn)數(shù)的運(yùn)算

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

3.浮點(diǎn)數(shù)的表示和運(yùn)算

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

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

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

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

（1）并行加法器

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

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

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

1.存儲器的分類

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

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

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

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

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

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

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

4.存儲器的擴(kuò)展方式及存儲器與cpu的連接

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

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

（1）cache的基本工作原理

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

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

（4）cache讀、寫策略

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

1.指令格式

（1）指令的基本格式

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

（3）擴(kuò)展操作碼指令格式

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è)計(jì)步驟。

（3）微程序控制器

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

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

微指令的編碼方式；

微地址的形式方式。

5.指令流水線

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

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

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

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

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

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

(六) 總線

1.總線概述

（1）總線的基本概念

（2）總線的分類

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

2.總線仲裁

（1）集中仲裁方式

（2）分布仲裁方式

3.總線操作和定時(shí)

（1）同步定時(shí)方式

（2）異步定時(shí)方式

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）

三、參考書目

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

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

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