计算机专业课考研大纲-学术学位

计算机考研专业课大纲一一学术学位

第一部分概述

一、考查目标

计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、

操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌

握上述专业基础课程的概念，理论、技能和方法，能够运用所学的知

识判断和解决相关的理论问题和实际问题。

二、考试形式和试卷结构

试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟

答题方式：闭卷、笔试

三、试卷内容结构

数据结构45分

计算机组成原理35分

操作系统35分

计算机网络35分

四、试卷题型结构

第二部分《数据结构》

第三部分《计算机组成原理》

第四部分《操作系统》

第五部分《计算机网络》

第二部分《数据结构》

考查目标

1.熟悉数据结构的相关概念及其分类，数据结构与算法的关系。掌握

线性表、堆栈和队列，数组和字符串等数据结构的存储、操作和应用，

树与二叉树的性质与应用算法，图的存储结构和相关算法，排序与查

找的典型算法。

2.掌握算法时空复杂性分析和正确性验证的基本方法。

3.能够综合运用数据结构、算法、数学等多种知识，对问题进行分

析、建模，选择或构建合适的数据结构，设计较优算法。

题型结构：包括问答题与算法设计题

具体内容：

一、绪论

(1)数据、数据元素、数据逻辑结构和存储结构的定义及其关系；

(2)数据逻辑结构及其分类；

(3)算法的定义和特征；

(4)算法的正确性证明方法；

(5)算法的时间和空间复杂性分析方法及复杂性函数的渐进表示。

二、线性表、堆栈和队列

(1)线性结构的概念和特点；

(2)顺序存储和链式存储线性表的基本操作；

(3)堆栈的定义和两种存储结构下堆栈的基本操作；

(4)堆栈在括号匹配和递归中的应用；

(5)队列的定义和两种存储结构下队列的基本操作；

(6)队列的应用。

三、数组和字符串

(1)二维及多维数组的存储原理及寻址方式；

(2)矩阵的存储及基本操作；

(3)三元组表和十字链表存储的稀疏矩阵的基本操作;

(4)字符串的存储及基本操作；

(5)模式匹配算法。

四、树与二叉树

(1)树的概念、相关术语和表示方法；

(2)二叉树的定义和性质；

(3)二叉树的顺序存储结构和链接存储结构；

(4)二叉树遍历的递归与非递归算法；

(5)线索二叉树的定义和操作；

(6)树与二叉树的转换；

(7)树的链接存储结构，树和森林的遍历算法；

(8)树的顺序存储结构；

(9)树在并查集实现中的应用。

五、图

(1)图的基本概念；

(2)图的邻接矩阵和邻接表存储结构；

(3)图的遍历算法；

(4)拓扑排序和关键路径算法；

(5)无权最短路径算法、正权最短路径算法、每对顶点之间的最短

路径算法，满足约束的最短路径问题；

(6)最小支撑树算法；

(7)图的可及性及传递闭包算法、连通分量算法。

六、排序

(1)直接插入排序和Shell排序；

(2)冒泡排序和快速排序；

(3)直接选择排序；

(4)堆的概念与性质，堆排序算法；

(5)合并排序算法；

(6)分治排序的一般方法，基于关键词比较的排序算法下界分析。

七、查找

(1)顺序查找算法；

(2)对半查找、一致对半查找、斐波那契查找和插值查找算法；

(3)对半查找算法的二叉判定树；

(4)二叉查找树的概念和性质，二叉查找树的查找、插入和删除算

法；

(5)高度平衡树的概念和性质，高度平衡树的查找和插入过程；

(6)B树及B+树的概念和基本操作；

(7)散列的基本概念，散列函数的构造方法；

(8)散列函数的冲突调节方法，拉链法和线性探查法。

第三部分《计算机组成原理》

考查目标

1.了解计算机硬件的发展史，技术的发展对计算机组成与体系结

构变迁的影响。理解计算机系统的基本架构、核心构成部分的功能与

相互联系，围绕CPU建立起整机的概念。

2.理解计算机是软硬件的有机体，掌握指令集体系结构的基本知

识和实现方法，掌握计算机系统结构的核心思想、CPU的组成与工作

机制，指令的执行过程和存储器体系的层次结构。

3.能够深入研究各功能部件的相互连接与相互作用，运用计算机

组成的基本原理和基本方法，进行一些基本功能部件的逻辑设计，解

决所遇到的理论和实际问题。

题型结构：包括简答题与综合应用题

具体内容：

一、计算机概要与技术

1.1计算应用的分类及其特性

1.2计算机系统结构中的8个伟大思想

L3性能的定义和度量

1.3.1CPU性能及其因素

1.3.2指令的性能

1.3.3经典的CPU性能公式

二、指令:计算机的语言

2.1计算机硬件的操作

2.2计算机硬件的操作数

2.2.1存储器操作数

222常数或立即数操作数

2.3有符号数和无符号数

2.4计机中指令的表示

2.5逻辑操作

2.6决策指令

2.6.1循环

2.6.2case/switch语句

2.7计算机硬件对过程的支持

2.7.1使用更多的寄存器

2.7.2嵌套过程

2.7.3在栈中为新数据分配空间

2.7.4在堆中为新数据分配空间

2.8人机交互

2.9MIPS中32位立即数和寻址

2.9.132位立即数

2.9.2分支和跳转中的寻址

2.9.3MIPS寻址模式总结

2.9.4机器语言解码

2.10并行与指令:同步

2.11翻译并执行程序

2.11.1编译器

2.11.2汇编器

2.11.3链接器

2.11.4加载器

2.11.5动态链接库

2.13数组与指针

2.13.1用数组实现clear

2.13.2用指针实现clear

2.13.3比较两个版本的clear

三、计算机的算术运算

3.1加和减法

3.2乘法

32工顺序的乘法算法和硬件

3.2.2有符号乘法

3.2.3更快速的乘法.

3.2.4MIPS中的乘法

3.3除法

3.3.1除法算法及其硬件结.构

3.3.2有符号除法

3.3.3更快速的除法

3.3.4MIPS中的除法

3.4浮点运算

3.4.1浮点表示

3.4.2浮点加法

3.4.3浮点乘法

3.4.4MIPS中的浮点指令

3.4.5算术精确性

四、处理器

4.1逻辑设计的一般方法

4.2建立数据通路

4.3一个简单的实现机制

4.3.1ALU控制

4.3.2主控制单元的设计

4.3.3为什么不使用单周期实现方式

4.4流水线概述

4.4.1面向流水线的指令集

4.4.2流水线冒险

4.4.3对流水线概述的小结

4.5流水线数据通路及其控制

4.5.1图形化表示的流水线

4.5.2流水线控制

4.6数据冒险:旁路与阻塞

4.7控制冒险

4.7.1假定分支不发生

4.7.2缩短分支的延迟

4.7.3动态分支预测

4.7.4流水线小结

4.8异常

4.8.1MIPS体系结构中的异常处理

4.8.2在流水线实现中的异常

4.9指令级并行

491推测的概念

492静态多发射处理器

4.9.3动态多发射处理器

4.9.4能耗效率与高级流水线

五、大容量和高速度:开发存储器层次结构

5.1存储器技术

5.1.1SRAM技术

5.1.2DRAM技术

5.1.3闪存

5.1.4磁盘存储器

5.2cache的基本原理

5.2.1cache访问

5.2.2cache缺失处理

5.2.3写操作处理

5.2.4一个cache的例子:内置FastMATH处理器

5.3.cache性能的评估和改进

5.3.1通过更天活地放置块来减少cache缺失

5.3.2在cache中查找一个块

5.3.3替换块的选择

5.3.4使用多级cache结构减少缺失代价

5.3.5通过分块进行软件优化

5.4可信存储器层次

5.4.1失效的定义

5.5虚拟存储器

5.5.1页的存放和查找

5.5.2缺页故障

5.5.3关于写

5.5.4加快地址转换:TLB.

5.5.5集成虚拟存储器、TLB.和cache

5.5.6虚拟存储器中的保护

5.5.7处理TLB缺失和缺页

5.6存储器层次结构的一般框架

5.6.1问题1:一个块可以被放在何处

5.6.2问题2:如何找到一个块

5.6.3问题3:当cache缺失时替换哪一块

5.6.4问题4:写操作如何处理

第四部分《操作系统》

考查目标

1.掌握操作系统基本概念，认识操作系统的运行机理；深刻理解

进程、线程、作业及其相互关系；理解程序并发与资源共享的控制方

法，能灵活运用PV操作、管程等并发控制机制解决互相斥、同步、

通信问题；理解并熟练掌握死锁与饥饿的概念及其处理方法；掌握处

理机、存储器、文件、设备等各种资源的管理方法与技术。

2.掌握操作系统的各部分构成及计算机系统中各种硬件、软件

资源管理的实现原理和方法，提高解决复杂应用问题的能力。

3.了解UNIX操作系统的数据结构与核心算法。

题型结构：包括简答题与综合应用题

具体内容：

一操作系统概述

1.1操作系统的概念

1.2操作系统的特性

1.3操作系统的硬件环境

1.4操作系统的界面形式

1.5操作系统的运行机理

1.6研究操作系统的几种观点

二进程、线程与作业

2.1多道程序设计

2.2进程的引入

2.3线程与轻进程

2.4作业

三中断与处理器调度

3.1中断与中断系统

3.2处理器调度

3.3调度级别与多级调度

3.4实时调度

四互斥、同步与通信

4.1并发进程

4.2进程互斥

4.3进程同步

4.4进程高级通讯

五死锁与饥饿

5.1死锁的概念

5.2死锁的类型

5.3死锁的条件

5.4死锁的处理

5.5资源分配图

5.6死锁的预防

5.7死锁的避免

5.8死锁的发现

5.9死锁的恢复

5.10鸵鸟算法

5.11饥饿与饿死

5.12可复用资源死锁的静态分析

5.13同种组合资源死锁的必要条件

六存储管理

6.1存储管理的功能

6.2内存资源管理

6.3单一连续区存储管理

6.4页式存储管理.

6.5段式存储管理

6.6段页式存储管理

七虚拟存储管理

7.1外存储器管理技术

7.2虚拟页式存储管理

7.3虚拟段式存储管理

7.4虚拟段页式存储管理

八文件系统

8.1文件与文件系统

8.2文件的访问方式

8.3文件的组织

8.4文件目录

8.5文件的共享

8.6文件的保护和保密

8.7文件存储空间的管理

8.8内存所需的表目

8.9文件系统的界面

8.10日志文件系统

8.11内存映射文件

8.12文件的安全

九设备与输入输出管理

9.1设备管理的功能与目标

9.2设备的分类

9.3设备的物理特性

9.4数据传输方式

9.5I/O软件的层次

9.6同步I/O与异步I/O

9.7设备分配与去配

9.8设备驱动

9.9设备调度

9.10缓冲与缓存

9.11输入输出进程

9.12RAID技术

9.13虚拟设备

十UNIX实例分析

10.1进程管理

10.2存储管理

10.3文件系统

10.4设备管理

10.5系统调用

第五部分《计算机网络》

考查目标

1.理解计算机网络的分层体系结构，特别是TCP/IP网络体系结构。

理解数据通信基本原理，包括信息的编码技术、传输模式、多路复用

技术、以及差错检测和控制。

2.了解物理层接口的机械特性、电气特性、功能特性和规程特性及物

理层网络互连。理解数据链路层的线路规程、差错和流量控制、停止

等待协议和滑动窗口协议的工作过程，数据链路层通信协议，LLC和

MAC、以太网、数据链路层网络互连设备及网桥路由算法。理解网络

层功能和提供的服务、路由选择策略和路由算法、网络层网络互连、

网络层的流量控制和拥塞控制，理解TCP/IP协议族中的IP协议、ICMP

协议、IGMP协议等网络层协议及Internet路由问题及IPv6。理解传

输层的功能和服务、传输层地址和传输层复用、传输层流量控制和拥

塞控制、掌握TCP/IP协议族中的UDP协议和TCP协议。了解域名服

务（DNS）、文件传输（FTP）、Email以及Web服务等具有代表性的

Internet服务。

3.掌握计算机网络的基本知识，具有协议分析能力。

题型结构：简答题或基础知识题，综合分析题

参考教材：《计算机网络》（第三版），胡亮、徐高潮、魏晓辉、车

喜龙编著，高等教育出版社，2018年9月出版。

具体内容

一、概论

1.1计算机网络的发展

1.2计算机网络的功能、组成及拓扑结构

1.2.1计算机网络的功能

1.2.2计算机网络的组成

1.2.3计算机网络的拓扑结构

1.3计算机网络体系结构

1.3.1网络协议和分层

1.3.2ISOOSI参考模型

1.3.3层间通信与对等层间通信

1.3.4服务和数据单元

1.3.5面向连接和无连接的服务

1.4TCP/IP网络体系结构

141TCP/IP协议栈

1.4.2TCP/IP的物理层和数据链路层

1.4.3TCP/IP的网络层

1.4.4TCP/IP的传输层

1.4.5TCP/IP的应用层

二、数据通信基础

2.1数据通信系统

2.1.1数据通信系统的组成

2.1.2数据通信系统应解决的主要问题

2.1.3数据通信的主要技术指标

2.2信号和数据编码

2.2.1模拟与数字信号

2.2.2数字一数字编码

2.2.3数字一模拟编码

2.2.4奈奎斯特准则

2.2.5香农定理

2.3线路配置和传输方式

2.3.1线路配置

2.3.2传输模式

2.4多路复用技术

2.4.1频分多路复用

2.4.2时分多路复用

2.4.3波分多路复用

2.4.4码分多路复用

2.5错误检测编码

2.5.1奇偶校验码

2.5.2循环冗余校验(CRC)码

2.5.3检查和

三、物理层

3.1物理层功能

3.2物理接口

3.2.1RJ45接口标准

322USB接口标准

3.2.3EIA-232接口标准

3.3传输介质

3.3.1双绞线

3.3.2同轴电缆

3.3.3光缆

3.3.4无线传输介质

3.4物理层互连设备

四、数据链路层

4.1线路规程

4.1.1询问/应答模式

4.1.2轮询/选择模式

4.2流量控制与差错控制

4.2.1停止等待协议

4.2.2滑动窗口协议

4.3HDLC通信协议

4.3.1HDLC支持的站点类型、链路配置和通信方式

4.3.2HDLC帧格式

4.3.3S-帧的使用方式

4.3.4U-帧的种类

4.3.5HDLC协议通信实例

4.4IEEE局域网通信协议

4.4.1IEEE局域网标准

4.4.2IEEE局域网参考模型

4.4.3逻辑链路控制LLC

4.5以太网

4.5.1以太网访问模式：CSMA/CD

4.5.2以太网MAC帧格式

4.5.3以太网种类

4.6无线局域网

4.6.1无线局域网标准

4.6.2802.11协、议族MAC帧格式

4.6.3CSMA/CA协议

4.6.4802.11b标准

4.7数据链路层网络互连

4.7.1网桥

4.7.2网桥路由算法

4.7.3二层交换机

4.7.4帧中继

五、网络层

5.1网络层的功能和服务

5.1.1网络层的功能

5.1.2面向连接的网络服务

5.1.3面向非连接的网络服务

5.2网络层互连

5.2.1路由器

5.2.2三层交换机

5.2.3网关

5.3路由选择原理

5.3.1距离向量路由算法

5.3.2链路状态路由算法

5.4拥塞控制和流量控制

5.4.1拥塞控制

5.4.2流量控制

5.5IP协议

5.5.1IP地址

5.5.2IPv4报文格式

5.5.3子网编址与子网掩码

5.5.4IP路由选择

5.6ICMP：Intern