一、考试要求 

    计算机学科专业基础考试大纲适用于北京工业大学信息学部计算机学院（0812）计算机科学与技术、（0839）网络空间安全、（0854）电子信息（专业学位）的硕士研究生招生考试。考试内容主要包括四部分：数据结构、计算机组成原理、操作系统与计算机网络，这四门课程是计算机科学与技术学科的重要基础课程。计算机学科专业基础考试科目满分 150分，其中《数据结构》部分占 100分，《计算机组成原理》部分占 20分，《操作系统》部分占 20分，《计算机网络》部分占 10分。 数据结构的考试内容主要包括基本数据结构、排序、索引、检索、高级数据结构等内容，从逻辑结构的角度包括线性表、栈、队列、二叉树、树和图等各种基本数据结构；从算法的角度包括各类排序、检索和索引算法。要求考生对其中的基本概念有很深入的理解，掌握数据结构与算法的基本概念、合理组织数据的基本方法、高效处理数据的基本算法、并具备面对实际问题选择恰当数据结构与相应算法的能力。 

        二、考试内容

        （一）数据结构部分 

        1．数据结构的相关概念、算法概念、算法性质及算法分析（时间复杂度与空间 复杂度）；

        2．线性表逻辑结构定义、存储结构的表示，以及在特定存储结构下线性表基本 运算的算法实现； 

        3．栈与队列的逻辑结构定义、存储结构的表示，基本操作特点，栈与队列的基 本应用； 

        4．串的逻辑结构定义，基本操作的含义与实现； 

        5．数组定义及其顺序存储，矩阵的压缩存储，广义表定义及存储结构； 

        6．树的定义与存储结构，二叉树的定义与性质、存储结构，二叉树遍历算法 （三序遍历与按层遍历），赫夫曼树与赫夫曼编码以及二叉树基本算法的实 现与应用； 

        7．图的定义与术语，图的存储结构，图的遍历（深度优先搜索与广度优先搜 索），最小生成树、拓扑排序以及最短路径的求解； 

        8．查找的相关概念，静态查找表（顺序表的查找与有序表的查找），动态查找 表（二叉排序树），B-树，B+树，AVL树，哈希表的相关概念； 

        9．排序的相关概念，掌握插入排序、冒泡排序、快速排序、简单选择排序、堆 排序、归并排序、基数排序算法的执行过程、时空复杂度、稳定性以及使用 场合。

        1．计算机系统概述：存储程序概念，计算机系统的基本组成与层次结构，计算 机系统的性能指标； 

        2．数据的表示和运算：数制与编码，定点数和浮点数的表示与运算，算术逻辑 单元 ALU； 

        3．指令系统：指令格式，指令的寻址方式，CISC和 RISC的基本概念； 

        4．中央处理器（CPU）：CPU 的功能和基本结构，指令执行过程，数据通路的 功能和基本结构，控制器的功能和工作原理，指令流水线；         

        5．存储器层次结构：存储器的分类，存储器的层次化结构，主存储器的连接与 控制，高速缓冲存储器（Cache）； 

        6．输入输出（I/O）系统：I/O 系统基本概念，I/O 接口的功能和基本结构，I/O 方式。

        （三）操作系统部分 

        1．操作系统的功能，操作系统的结构，操作系统的执行； 

        2．系统调用，操作系统的设计与实现，操作系统的结构； 

        3．进程的概念，进程状态及转换，进程控制块，进程运行，进程间通信； 

        4．线程； 

        5．进程调度原理及算法； 

        6．临界资源，临界区，进程同步机制应遵循的准则，信号量机制，解决进程同 步与互斥问题；  

        7．死锁，死锁的必要条件，死锁的预防、避免、检测、恢复； 

        8．连续内存分配方法，分页，分段； 

        9．虚拟存储器的概念，请求调页，页面置换，系统抖动； 

        10．文件，文件系统，访问方法，目录，文件分配方法，空闲空间管理；。 

        11．I/O硬件，应用程序 I/O接口，内核 I/O子系统； 

        12．磁盘结构，磁盘调度算法。

        1．计算机网络概述：计算机网络定义、分类及应用，计算机网络体系结构，网 络标准化工作及相关组织； 

        2．物理层：数据通信的基础知识，传输介质及其特性，数字调制与复用技术， 数字传输系统； 

        3．数据链路层：数据链路层的功能与服务，差错处理技术，数据链路层协议的 基本原理和典型协议； 

        4．介质访问控制子层：多路访问协议，以太网，无线局域网，数据链路层交换 技术；

        5．网络层：网络层的功能与服务，路由算法及协议，网络组网方式，Internet 的 网络层协议； 

        6．传输层：传输层的功能与服务，UDP协议、TCP协议； 

        7．应用层：应用层的功能与服务，域名系统 DNS，电子邮件系统构成与协议， 万维网 WWW原理与协议。

        三、参考书目 

        1．严蔚敏, 吴伟民.《数据结构》(C 语言版). 清华大学出版社, 2011. 

        2．唐朔飞.《计算机组成原理》(第 2版). 高等教育出版社, 2013.
        3．西尔伯沙茨（Abraham Silberschatz）, 高尔文（Peter B. Galvin）, 加涅（Greg Gagne）著，郑扣根, 唐杰, 李善平译. 《操作系统概念（原书第 9 版）》（翻 译版）. 机械工业出版社. 2018. 

        4．Andrew S. Tanenbaum, David J. Wetherall 著，严伟, 潘爱民译. 《计算机网络》 (第 5版). 清华大学出版社, 2012.