2020年硕士研究生入学考试自命题科目考试大纲

科目代码：821科目名称：计算机专业基础综合

一、考试要求

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

二、考试内容

（一）数据结构与算法部分

1．数据结构与算法基本概念

线性表、栈与队列、树与二叉树、B-树、B+-树、图、稀疏矩阵、贪心法、动态规划法、递归与分治、回溯法、分支限界法。

2．基本数据结构的应用

栈与队列的应用、内排序算法、线性表的查找方法、二叉排序树的应用、堆排序、Huffman算法、图的搜索、最小代价生成树、最短路径、AOV网的拓扑排序、AOE网的关键路径。

3．算法设计与分析

能运用数据结构与算法的知识解决非数值问题的数据抽象、算法设计、C（或C++）语言算法实现。

（二）计算机原理部分

1．计算机系统概述

计算机系统层次结构，包括计算机硬件的基本组成、计算机软件的分类；性能指标，包括主频（CPU时钟周期）、运算速度（CPI、CPU执行时间、MIPS、MFLOPS）等。

2．指令系统

计算机中的数据表示，包括定点数和浮点数的表示、校验码；计算机的指令格式，包括指令的基本格式、扩展操作码的指令格式；指令的寻址方式，包括数据寻址和指令寻址、常用寻址方式等。

3．计算机中的运算

计算机中的基本运算，包括逻辑及移位运算；定点数的加（减）、乘、除法运算；浮点数的加（减）、乘、除法运算；运算器的设计，包括算术逻辑单元ALU、串/并行加法器、浮点运算器等。

4．中央处理器

流水线的基本概念；硬连线控制器的基本概念及设计；微程序控制器的基本概念及实现方法。

5．存储层次结构

主存储器的基本概念及设计使用；高速缓冲存储器(Cache)、虚拟存储器的基本概念和性能评估。

6．输入输出（I/O）系统

输入输出系统的基本概念；I/O设备和I/O接口；三种I/O控制方式，包括程序查询、中断驱动和DMA方式。

7．总线

总线的基本概念及性能指标；总线的设计，包括总线仲裁、总线的操作和定时方式等。

三、考试形式

考试形式：闭卷、笔试。

考试时间：3小时。

满分：150分。

试卷内容：数据结构与算法、计算机原理各75分。

题型：选择题、填空题、简答题、综合应用题等。

四、参考书目

1．《数据结构与算法》，熊岳山著，清华大学出版社，2016，第二版

2.《ComputerOrganizationandDesign(4thEdition)》，DavidA.Patterson，MKPress2011，4thEdition

3．《计算机原理和设计》，王保恒等编，高等教育出版社，2005，第一版

2020年硕士研究生入学考试自命题科目考试大纲

科目代码：F0201科目名称：操作系统

一.考试要求

主要考查学生对操作系统基本概念、结构、策略，以及一些基本的算法、处理过程的理解与掌握；对并发程序设计技术的掌握，对构成系统的进程管理、存储管理、设备管理、文件系统及命令解释器等各模块的工作机理及设计方法的掌握。学生应具备一定的设计能力。

二、考试内容

第一章绪论

主要内容：

1．操作系统的功能、地位、组成及特征，多道程序设计；

2．操作系统的形成、发展、分类；

3．流行操作系统简介。

第二章操作系统运行机制

主要内容：

1．中断和陷入机制；

2．操作系统内核程序嵌入进程运行模型；

3．操作系统系统调用实现方法；

4．命令界面实现方法。

第三章进程管理

主要内容：

1．进程的描述和组成、进程的创建和结束处理、进程的状态和状态转换；

2．进程调度与切换概念与实现；

3．调度的层次、调度算法选择的准则、进程调度典型算法；

4．线程概念、进程与线程区别。

第四章并发进程

主要内容：

1．进程的并发性、进程的同步与互斥；

2．实现互斥的硬件机制、信号量机制及应用；

3．进程间通信概念及实现；

4．死锁防止、死锁避免、死锁检测和解除。

第五章存储管理

主要内容：

1．存储管理的功能、地址变换、固定分区存储管理、可变分区存储管理、分页存储管理；

2．虚拟存储器的概念、请求分页虚拟存储管理原理与实现技术；

3．典型页面淘汰策略。

第六章设备管理

主要内容：

1．设备分类及管理、I/O控制方式及控制接口、I/O软件层次及主要功能、字符设备与块设备接口、驱动程序组成；

2．缓冲技术、磁盘请求调度及算法；

3．独占设备虚拟化技术。

第七章文件系统

主要内容：

1．文件概念、文件访问方法；

2．文件逻辑结构；文件物理结构；

3．文件控制块FCB（索引节点）、文件目录与目录项；

4．各种目录结构的组织、特性；目录项检索与操作；

5．文件类系统调用、mmap文件访问、文件共享、保护和保密；文件存储空间管理、文件系统层次结构与设计；

第八章并行与分布式系统

主要内容：

1．对称多处理机、多核系统、进程与线程、线程应用、线程状态、用户级和核心级线程的实现技术、多处理器环境下线程调度算法；

2．分布式系统特性、分布式应用模型、分布式系统实现模型。

三、考试形式

考试形式为闭卷、笔试，考试时间为1.5-2.0小时，满分100分。

题型包括：选择题、简答题、分析题、设计应用题等。

四、参考书目

《操作系统》第五版,罗宇,电子工业出版社,2019.