考研专业课大纲#2020年北京邮电大学803计算机学科基础综合考研究生大纲

803计算机学科基础综合

一、考查目标

计算机学科基础综合考试涵盖数据结构 、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念
、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题 。

二 、考试形式和试卷结构

1
、试卷满分及考试时间

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

2、答题方式

答题方式为闭卷 、笔试
。

3
、试卷内容结构

数据结构45分

计算机组成原理45分

操作系统35分

计算机网络25分

4、试卷题型结构

单项选择题80分(40小题，每小题2分)

综合应用题70分

三 、考查内容

数据结构

[考查目标]

1
、掌握数据结构的基本概念、基本原理和基本方法。

2 、掌握数据的逻辑结构
、存储结构及基本操作的实现
，能够对算法进行基本的时间复杂度与空间复杂度的分析 。

3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力
。

一 、线性表

(一)线性表的定义和基本操作

(二)线性表的实现

1、顺序存储

2
、链式存储

3、线性表的应用

二 、栈
、队列和数组

(一)栈和队列的基本概念

(二)栈和队列的顺序存储结构

(三)栈和队列的链式存储结构

(四)栈和队列的应用

(五)特殊矩阵的压缩存储

三、树与二叉树

(一)树的基本概念

(二)二叉树

1 、二叉树的定义及其主要特征

2
、二叉树的顺序存储结构和链式存储结构

3、二叉树的遍历

4 、线索二叉树的基本概念和构造

(三)树
、森林

1、树的存储结构

2 、森林与二叉树的转换

3
、树和森林的遍历

(四)树与二叉树的应用

1、二叉排序树

2 、平衡二叉树

3、哈夫曼(Huffman)树和哈夫曼编码

四
、图

(一)图的基本概念

(二)图的存储及基本操作

1、邻接矩阵法

2 、邻接表法

3
、邻接多重表、十字链表

(三)图的遍历

1 、深度优先搜索

2
、广度优先搜索

(四)图的基本应用

1、最小(代价)生成树

2 、最短路径

3
、拓扑排序

4、关键路径

五 、查找

(一)查找的基本概念

(二)顺序查找法

(三)分块查找法

(四)折半查找法

(五)B树及其基本操作
、B+树的基本概念

(六)散列(Hash)表

(七)字符串模式匹配

(八)查找算法的分析及应用

六、排序

(一)排序的基本概念

(二)插入排序

1 、直接插入排序

2、折半插入排序

(三)气泡排序(bubblesort)

(四)简单选择排序

(五)希尔排序(shellsort)

(六)快速排序

(七)堆排序

(八)二路归并排序(mergesort)

(九)基数排序

(十)外部排序

(十一)各种内部排序算法的比较

(十二)排序算法的应用

计算机组成原理

[考查目标]

1
、理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式 ，具有完整的计算机系统的整机概念。

2 、理解计算机系统层次化结构概念
，熟悉硬件与软件之间的界面，掌握指令集体系结构的基本知识和基本实现方法 。

3
、能够综合运用计算机组成的基本原理和基本方法 ，对有关计算机硬件系统中的理论和实际问题进行计算、分析
，对一些基本部件进行简单设计;并能对高级程序设计语言(如C语言)中的相关问题进行分析
。

一 、计算机系统概述

(一)计算机发展历程

(二)计算机系统层次结构

1
、计算机系统的基本组成

2、计算机硬件的基本组成

3 、计算机软件和硬件的关系

4
、计算机的工作过程

(三)计算机性能指标

吞吐量、响应时间;CPU时钟周期 、主频
、CPI、CPU执行时间;MIPS 、MFLOPS、GFLOPS
、TFLOPS、PFLOPS。

二 、数据的表示和运算

(一)数制与编码

1
、进位计数制及其相互转换

2、真值和机器数

3 、BCD码

4
、字符与字符串

5、校验码

(二)定点数的表示和运算

1 、定点数的表示

无符号数的表示;有符号整数的表示 。

2
、定点数的运算

定点数的位移运算;原码定点数的加减运算;补码定点数的加/减运算;定点数的乘/除运算;溢出概念和判别方法
。

(三)浮点数的表示和运算

1、浮点数的表示

IEEE754标准

2 、浮点数的加/减运算

(四)算术逻辑单元ALU

1
、串行加法器和并行加法器

2、算术逻辑单元ALU的功能和结构

三 、存储器层次结构

(一)存储器的分类

(二)存储器的层次化结构

(三)半导体随机存取存储器

1、SRAM存储器

2
、DRAM存储器

3、只读存储器

4 、Flash存储器

(四)主存储器与CPU的连接

(五)双口RAM和多模块存储器

(六)高速缓冲存储器(Cache)

1
、Cache的基本工作原理

2、Cach和主存之间的映射方式

3 、Cache中主存块的替换算法

4
、Cache写策略

(七)虚拟存储器

1、虚拟存储器的基本概念

2 、页式虚拟存储器

3
、段式虚拟存储器

4、段页式虚拟存储器

5 、TLB(快表)

四
、指令系统

(一)指令格式

1、指令的基本格式

2 、定长操作码指令格式

3、扩展操作码指令格式

(二)指令的寻址方式

1
、有效地址的概念

2、数据寻址和指令寻址

3 、常见寻址方式

(三)CISC和RISC的基本概念

五
、中央处理器(CPU)

(一)CPU的功能和基本结构

(二)指令执行过程

(三)数据通路的功能和基本结构

(四)控制器的功能和工作原理

1、硬布线控制器

2 、微程序控制器

微程序
、微指令和微命令;微指令的编码方式;微地址的形式方式。

(五)指令流水线

1、指令流水线的基本概念

2 、指令流水线的基本实现

3
、超标量和动态流水线的基本概念

(六)多核处理器的基本概念

六、总线

(一)总线概述

1 、总线的基本概念

2
、总线的分类

3、总线的组成及性能指标

(二)总线仲裁

1 、集中仲裁方式

2、分布仲裁方式

(三)总线操作和定时

1
、同步定时方式

2、异步定时方式

(四)总线标准

七 、输入输出(I/O)系统

(一)I/O系统基本概念

(二)外部设备

1
、输入设备：键盘、鼠标

2 、输出设备：显示器
、打印机

3、外存储器：硬盘存储器 、磁盘阵列
、光盘存储器

(三)I/O接口(I/O控制器)

1、I/O接口的功能和基本结构

2 、I/O端口及其编址

(四)I/O方式

1
、程序查询方式

2、程序中断方式

中断的基本概念;中断响应过程;中断处理过程;多重中断和中断屏蔽的概念 。

3 、DMA方式

DMA控制器的组成，DMA传送过程
。

操作系统

[考查目标]

1、掌握操作系统的基本概念
、基本原理和基本功能 ，理解操作系统的整体运行过程。

2、掌握操作系统进程 、内存
、文件和I/O管理的策略、算法 、机制以及相互关系 。

3
、能够运用所学的操作系统原理、方法与技术分析问题和解决问题
，并能利用C语言描述相关算法。

一 、操作系统概述

(一)操作系统的概念
、特征、功能和提供的服务

(二)操作系统的发展与分类

(三)操作系统的运行环境

1 、内核态与用户态

2
、中断、异常

3 、系统调用

(四)操作系统体系结构

二、进程管理

(一)进程与线程

1
、进程概念

2、进程的状态与转换

3 、进程控制

4
、进程组织

5、进程通信

共享存储系统;消息传递系统;管道通信
。

6 、线程概念与多线程模型

(二)处理机调度

1
、调度的基本概念

2、调度时机 、切换与过程

3
、调度的基本准则

4、调度方式

5 、典型调度算法

先来先服务调度算法;短作业(短进程
、短线程)优先调度算法;时间片轮转

调度算法;优先级调度算法;高响应比优先调度算法;多级反馈队列调度算法。

(三)同步与互斥

1、进程同步的基本概念

2 、实现临界区互斥的基本方法

软件实现方法;硬件实现方法 。

3、信号量

4
、管程

5、经典同步问题

生产者-消费者问题;读者-写者问题;哲学家进餐问题
。

(四)死锁

1 、死锁的概念

2
、死锁处理策略

3、死锁预防

4 、死锁避免

系统安全状态，银行家算法。

5
、死锁检测和解除

三、内存管理

(一)内存管理基础

1 、内存管理概念

程序装入与链接;逻辑地址与物理地址空间;内存保护 。

2
、交换与覆盖

3、连续分配管理方式

4 、非连续分配管理方式

分页管理方式;分段管理方式;段页式管理方式
。

(二)虚拟内存管理

1
、虚拟内存基本概念

2、请求分页管理方式

3 、页面置换算法

最佳置换算法(OPT);先进先出置换算法(FIFO);最近最少使用置换算法(LRU);时钟置换算法(CLOCK)。

4、页面分配策略

5
、工作集

6.、抖动

四 、文件管理

(一)文件系统基础

1
、文件概念

2、文件的逻辑结构

顺序文件;索引文件;索引顺序文件 。

3 、目录结构

文件控制块和索引节点;单级目录结构和两级目录结构;树形目录结构;图形目录结构
。

4
、文件共享

5、文件保护

访问类型;访问控制。

(二)文件系统实现

1 、文件系统层次结构

2
、目录实现

3、文件实现

(三)磁盘组织与管理

1 、磁盘的结构

2
、磁盘调度算法

3、磁盘的管理

五 、输入输出(I/O)管理

(一)I/O管理概述

1、I/O控制方式

2.
、I/O软件层次结构

(二)I/O核心子系统

1、I/O调度概念

2 、高速缓存与缓冲区

3
、设备分配与回收

4、假脱机技术(SPOOLing)

计算机网络

[考查目标]

1 、掌握计算机网络的基本概念
、基本原理和基本方法 。

2、掌握计算机网络的体系结构和典型网络协议 ，了解典型网络设备的组成和特点
，理解典型网络设备的工作原理
。

3 、能够运用计算机网络的基本概念
、基本原理和基本方法进行网络系统的分析、设计和应用。

一 、计算机网络体系结构

(一)计算机网络概述

1
、计算机网络的概念、组成与功能

2 、计算机网络的分类

3、计算机网络的标准化工作及相关组织

(二)计算机网络体系结构与参考模型

1
、计算机网络分层结构

2、计算机网络协议 、接口
、服务等概念

3、ISO/OSI参考模型和TCP/IP模型

二 、物理层

(一)通信基础

1
、信道、信号 、宽带
、码元、波特 、速率
、信源与信宿等基本概念

2、奈奎斯特定理与香农定理

3 、编码与调制

4、电路交换
、报文交换与分组交换

5、数据报与虚电路

(二)传输介质

1 、双绞线
、同轴电缆、光纤与无线传输介质

2 、物理层接口的特性

(三)物理层设备

1
、中继器

2、集线器

三 、数据链路层

(一)数据链路层的功能

(二)组帧

(三)差错控制

1
、检错编码

2、纠错编码

(四)流量控制与可靠传输机制

1 、流量控制
、可靠传输与滑轮窗口机制

2、停止-等待协议

3 、后退N帧协议(GBN)

4、选择重传协议(SR)

(五)介质访问控制

1
、信道划分

频分多路复用、时分多路复用 、波分多路复用
、码分多路复用的概念和基本原理 。

2、随即访问

ALOHA协议;CSMA协议;CSMA/CD协议;CSMA/CA协议。

3 、轮询访问：令牌传递协议

(六)局域网

1
、局域网的基本概念与体系结构

2、以太网与IEEE802.3

3 、IEEE802.11

4
、令牌环网的基本原理

(七)广域网

1.广域网的基本概念

2、PPP协议

3 、HDLC协议

(八)数据链路层设备

1
、网桥的概念和基本原理

2、局域网交换机及其工作原理
。

四 、网络层

(一)网络层的功能

1、异构网络互联

2
、路由与转发

3、拥塞控制

(二)路由算法

1 、静态路由与动态路由

2
、距离-向量路由算法

3、链路状态路由算法

4 、层次路由

(三)IPv4

1
、IPv4分组

2、IPv4地址与NAT

3 、子网划分与子网掩码
、CIDR

4、ARP协议 、DHCP协议与ICMP协议

(四)IPv6

1
、IPv6的主要特点　　2、IPv6地址

(五)路由协议

1 、自治系统

2、域内路由与域间路由

3
、RIP路由协议

4、OSPF路由协议

5 、BGP路由协议

(六)IP组播

1
、组播的概念

2、IP组播地址

(七)移动IP

1 、移动IP的概念

2
、移动IP的通信过程

(八)网络层设备

1、路由器的组成和功能

2 、路由表与路由转发

五
、传输层

(一)传输层提供的服务

1、传输层的功能

2 、传输层寻址与端口

3
、无连接服务与面向连接服务

(二)UDP协议

1.UDP数据报

2.UDP校验

(三)TCP协议

1、TCP段

2 、TCP连接管理

3、TCP可靠传输

4
、TCP流量控制与拥塞控制

六、应用层

(一)网络应用模型

1 、客户/服务器模型

2
、P2P模型

(二)DNS系统

1、层次域名空间

2 、域名服务器

3
、域名解析过程

(三)FTP

1、FTP协议的工作原理

2 、控制连接与数据连接

(四)电子邮件

1
、电子邮件系统的组成结构

2、电子邮件格式与MIME

3 、SMTP协议与POP3协议

(五)WWW

1
、WWW的概念与组成结构

2、HTTP协议