2023年北京化工大学计算机科学与技术考研844考试大纲

考试大纲的内容一般包括当年全国研究生入学考试相应科目的考试范围、考试要求、考试形式、试卷结构等信息，对考生备考至关重要。希赛网整理了2023年北京化工大学计算机科学与技术（081200）考研844计算机学科专业基础综合考试大纲信息，希望对考生备考有所帮助。

相关阅读推荐>>>2021-2022年全国考研复试线丨2023年全国考试科目汇总丨2023年全国研究方向汇总

（注：以下信息来自学院官网，仅供参考，具体内容以院校发布为准）

844 计算机学科专业基础综合一初试考试大纲

1 考查目标

‍

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

2 考试形式和试卷结构 

2.1 试卷满分及考试时间

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

2.2 答题方式

答题方式为闭卷、笔试。

2.3 试卷结构

数据结构约占 80 分

计算机组成原理约占 35 分

操作系统原理约占 35 分 

2.4 试卷题型

单项选择题 44 分(每题 2 分)，综合应用题 106 分 

3 考试大纲与主要参考书 

3.1 《数据结构》 

3.1.1 考试的基本要求 

1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 

2.掌握基本数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度分析。 

3.能够选择合适的数据结构和方法进问题求解，具备采用C 或C++或JAVA语言设计与实现算法的能力。 

3.1.2 考试的主要内容与要求 

1、数据结构和算法的基本概念

了解数据结构的基本概念，包括逻辑结构、物理结构的基本概念、两者之间的区别与联系。

了解算法的基本概念和性质。了解算法复杂度的基本概念，掌握对非递归代码的复杂度的计算基本方法。

2、线性表

了解线性表的逻辑结构定义。

掌握线性表的顺序结构实现，以及顺序结构下基本操作的实现，能写出操作代码。掌握线性表的链式结构实现，以及链式结构下基本操作的实现，能写出操作代码。能够设计针对顺序结构和链式结构线性表的一般应用问题的算法，能写出算法代码。掌握栈的基本概念、栈的性质。

掌握栈的顺序结构和链式结构实现，以及相应操作的实现，能够写出操作代码。了解栈与递归的关系，能够编写递归算法，能够将递归算法转换为非递归形式。掌握队列的基本概念和性质。

掌握队列的顺序结构和链式结构实现，以及相应操作的实现，能写出操作代码。掌握栈和队列的应用方法，能够运用栈和队列解决相关问题，能写出算法代码。掌握串的基本操作实现，能写出算法代码。掌握串的朴素模式匹配算法和 KMP 模式匹配算法，能手工计算KMP 算法中的nextval向量，能写出算法代码。掌握稀疏矩阵的三元组表存储方法以及基于三元组表结构的快递转置算法，能写出算法代码。 

 3、树和二叉树

了解树的定义和性质。

了解二叉树的概念。

掌握二叉树的基本性质，并能够进行描述和证明。(包括深度与最大结点数的关系性质、每层最大结点数性质、结点数与最小深度的关系性质、n2=n0-1 性质、完全二叉树序号与结点关系性质等)

掌握二叉树的二叉链结构的实现。

掌握二叉树的前序遍历、中序遍历、后序遍历和层次遍历规则，能够手工计算二叉树的遍历序。

掌握二叉树的遍历性质，能够根据前序+中序或中序+后序还原出二叉树，并能写出还原算法代码。

掌握二叉树的前序、中序和后序递归遍历算法，能写出算法代码。了解线索化二叉树的概念。

了解哈夫曼树的概念。掌握哈夫曼算法的思想和步骤，能够手工计算哈夫曼树，能写出算法代码。

了解哈夫曼编码的概念，能够手工计算哈夫曼编码。了解树、森林和二叉树的关系。能够解决一般性的二叉树应用问题，设计算法并写出算法代码。

4、图

了解图的定义。

掌握图的邻接矩阵、邻接表的实现方法。

掌握图的深度优先和广度优先遍历算法，能够手工计算图的深度优先遍历序和广度优先遍历序，能写出算法代码。

掌握最小生成树计算(Prim 算法和 Kruskal 算法)，能够进行手工计算，能写出算法代码。

掌握最小生成树的 MST 性质，能够进行描述和证明。

掌握拓扑排序和关键路径问题的求解算法，能够进行手工计算，能写出算法代码。

掌握单源起点最短路径算法(Dijkstra 算法)和任两点间最短路径算法(Floyd算法)，能够进行手工计算，能写出算法代码。 

 5、查找

掌握静态表的概念和折半查找算法，能够进行手工计算，能写出算法代码。

掌握散列表的基本概念，散列函数的基本设计技巧。掌握二叉排序树的概念，以及二叉排序树上的查找、插入、删除算法，能够进行手工计算，能写出算法代码。

掌握平衡二叉树的概念，以及平衡二叉树的插入和调整算法，能够进行手工计算。了解 B-、B+树的概念，以及 B-树的插入和删除算法。

6、内排序

掌握简单选择排序、直接插入排序、交换排序、希尔排序、快速排序、堆排序、二路归并排序、基数排序的算法思想和步骤，能够写出排序过程，能写出算法代码。

了解各种排序方法的特点，能够针对特定问题背景选择适当的排序方法。

3.1.3 主要参考书

严蔚敏.数据结构(C 语言版).北京：清华大学出版社，2020 

3.2 《计算机组成原理》 

3.2.1 考试的基本要求 

1.掌握冯诺依曼架构中主要部件的基本分类、工作原理、组成结构以及相互连接方式。 

2.掌握指令集体系结构的基本知识和工作原理，对指令工作流程和相关硬件结构进行分析。 

3.理解计算机系统的整机概念，能够综合运用计算机组成的基本原理和基本方法，对高级编程语言程序中的相关问题进行分析，具备软硬件协调分析和设计能力。

3.2.2 考试的主要内容与要求 

1、计算机系统概述掌握计算机系统层次结构、基本组成、硬件与软件的关系。掌握计算机性能的评价指标。 

2、运算方法与运算器掌握 IEEE754 的基本概念和表示方法;了解数据与文字的表示方法和编码方式。掌握定点、浮点数的加减运算;了解定点数的乘法运算。掌握 ALU 基本结构与工作原理;理解行波进位加法器、先行进位加法器的基本概念。

3、层次结构存储器理解存储器的层次结构与分类;掌握内存的基本概念和工作原理。掌握半导体存储器的分类、特点、应用场景;理解半导体存储器的基本结构和工作原理。理解磁盘的基本结构与工作原理;了解固态硬盘和光盘的基本结构与工作原理。掌握 Cache 基本概念;理解 Cache 与主存的映射方式、替换算法、写策略。了解虚拟存储器的基本概念和原理。 

 4、指令系统理解指令系统的基本概念、格式、寻址方式;理解 CISC 和RISC 的基本概念和应用场景。 

5、中央处理器掌握 CPU 的主要功能、基本结构、工作原理、主要寄存器。掌握计算机中不同周期的关系与区别;理解 CPU 数据通路的基本结构和指令执行过程。理解微程序控制器的基本结构与工作原理;了解硬布线控制器的基本概念;了解时序信号的基本概念。理解流水线的基本概念、分类、相关问题;了解超标量的基本概念。 

 6、总线掌握总线的基本概念、性能指标和常见总线标准;理解总线的连接方式和仲裁方式。了解总线的同步定时方式和异步定时方式。 

7、输入输出系统掌握 I/O 系统基本概念和 I/O 设备分类;理解 I/O 接口的功能和基本结构。理解基本 I/O 方式的基本概念和工作原理。 

3.2.3 主要参考书

白中英，戴志涛.计算机组成原理(第六版).北京：科学出版社，2019 

3.3 《操作系统原理》 

3.3.1 基本要求 

1、 掌握操作系统相关的基础知识和基本原理，理解操作系统的整体运行过程。

2、 掌握操作系统各关键模块的策略、核心算法、机制及相互关系。

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

3.3.2 考试的主要内容与要求 

1、操作系统概述操作系统的概念、特征、功能和提供的服务;操作系统的发展与分类。理解操作系统的概念及其在计算机系统中的地位。理解现代操作系统的基本组成。了解操作系统的发展历史及分类。了解主流操作系统的各自特征、优缺点及发展趋势。理解操作系统发展中的各典型结构。 

 2、进程管理理解进程的概念，与程序、线程的关系与区别。理解进程和线程模型，能够理解操作系统中的进程实现和管理方式。深刻理解进程的各种状态及状态转换过程。理解进程间通信的原因和主要模式。理解临界区、临界资源和互斥的概念及产生原因。理解同步准则及实现互斥的软硬件方法。理解信号量的概念，理解记录型信号量和信号量集等不同信号量类型。深度理解各种经典同步问题及其变形问题的实现。理解进程调度的概念和层次，熟练掌握典型的调度算法理解实时调度的基本概念和算法。理解死锁的概念、死锁原理、死锁形成的必要条件。以及死锁的预防、避免、检测与解除方法。理解系统安全状态的概念;熟练掌握银行家算法的基本原理及应用。

3、内存管理了解内存管理的概念和功能、程序的装入与链接。理解内存交换与内存覆盖。掌握连续分配内存管理方式，固定分区分配算法等。掌握离散分配内存管理方式，理解内存分页的原理并掌握物理块、页内偏移、地址变换等概念。理解虚拟存储器的概念和工作原理。理解缺页中断的概念和原理。理解页表的作用与组成，多级页表、反置页表的工作原理。理解快表的作用与原理。熟练掌握常见的页面置换算法。理解有效访问时间问题、工作集模型、抖动的概念与产生原因。理解内存分段管理的原理和方法，掌握段页式管理内存的特点。了解存储保护问题：共享和保护的含义和基本方法。

4、文件管理了解文件的概念、文件系统的概念、文件系统的层次结构。掌握文件的逻辑组织。掌握目录的管理，索引结点的概念等。掌握常见的外存分配方法。掌握外存磁盘介质的基本特点、磁盘调度算法等。掌握空闲存储空间管理的方法(位示图、成组链接法等)。了解文件共享和文件保护的基本方法，掌握文件保护域和文件存取控制表的使用及转换。 

 5、输入输出(I/O)管理了解I/O系统基本概念、I/O软件层次结构。了解设备控制器、设备驱动程序、设备无关性等概念。掌握I/O控制方式的演变。掌握缓冲管理基本技术。掌握设备分配与回收的技术。掌握假脱机技术(SPOOLing)。 3.3.3 主要参考书汤小丹，计算机操作系统(第四版)，西安电子科技大学出版社，西安,2018.10

数据来源：北京化工大学研究入学考试计算机学科专业基础综合考试大纲