河北建筑工程学院
硕士研究生入学考试《计算机专业基础综合》考试大纲
科目代码：806
一、考试的总体要求
计算机科学与技术学科专业基础综合考试是为招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的考试，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，以利于硕士研究生的择优选拔，确保招生质量。
计算机科学与技术学科专业基础综合考试实行自主命题，考试内容：数据结构、（计算机组成原理、操作系统、计算机网络）三选一。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
二、考试的内容及比例
数据结构90分，（计算机组成原理、操作系统、计算机网络）三选一60分。
第一部分：《数据结构》
（一）考查目标
1.掌握数据结构的基本概念、基本原理和基本方法。
2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
（二）考察内容
1.线性表
1）线性表的定义和基本操作
2）线性表的实现
①顺序存储
②链式存储
③线性表的应用
2.栈、队列和数组
1）栈和队列的基本概念
2）栈和队列的顺序存储结构
3）栈和队列的链式存储结构
4）栈和队列的应用
3.树与二叉树
1）树的基本概念
2）二叉树
①二叉树的定义及其主要特征
②二叉树的顺序存储结构和链式存储结构
③二叉树的遍历
④线索二叉树的基本概念和构造
3）树与二叉树的应用
①二叉排序树
②平衡二叉树
③哈夫曼(Huffman)树和哈夫曼编码
4.图
1）图的基本概念
2）图的存储及基本操作
①邻接矩阵法
②邻接表法
③邻接多重表、十字链表
3）图的遍历
①深度优先搜索
②广度优先搜索
4）图的基本应用
①最小(代价)生成树
②最短路径
③拓扑排序
④关键路径
5.查找
1）查找的基本概念
2）顺序查找法
3）分块查找法
4）折半查找法
5）散列(Hash)表
6）查找算法的分析及应用
6.排序
1）排序的基本概念
2）插入排序
①直接插入排序
②折半插入排序
3）冒泡排序(bubblesort)
4）简单选择排序
5）希尔排序(shellsort)
6）快速排序
7）堆排序
8）二路归并排序(MergeSort)
9）各种内部排序算法的比较
10）排序算法的应用
第二部分：《计算机组成原理》、《操作系统》、《计算机网络》三选一
《计算机组成原理》
（一）考查目标
1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。
2.理解计算机系统层次化结构概念，熟悉硬件与软件之间的界面，掌握指令集体系结构的基本知识和基本实现方法。
3.能够运用计算机组成的基本原理和基本方法，对有关计算机硬件系统中的理论和实际问题进行计算、分析，并能对一些基本部件进行简单设计。
（二）考查内容
1.计算机系统概述
1）计算机发展历程
2）计算机系统层次结构
①计算机硬件的基本组成
②计算机软件的分类
③计算机的工作过程
3）计算机性能指标
吞吐量、响应时间、CPU时钟周期、主频、CPI、CPU执行时间、MIPS、MFLOPS
2.数据的表示和运算
1）数制与编码
①进位计数制及其相互转换
②真值和机器数
③BCD码
④字符与字符串
⑤校验码
2）定点数的表示和运算
①定点数的表示，无符号数的表示；有符号整数的表示。
②定点数的运算
定点数的位移运算；原码定点数的加/减运算；补码定点数的加/减运算；定点数的乘/除运算；溢出概念和判别方法。
3）浮点数的表示和运算
IEEE754标准
4）算术逻辑单元ALU
①串行加法器和并行加法器
②算术逻辑单元ALU的功能和结构
3.存储器层次机构
1）存储器的分类
2）存储器的层次化结构
3）半导体随机存取存储器
①SRAM存储器的工作原理
②DRAM存储器的工作原理
4）只读存储器
5）主存储器与CPU的连接
6）高速缓冲存储器（Cache）
①程序访问的局部
②Cache的基本工作原理
③Cache和主存之间的映射方式
④Cache中主存块的替换算法
⑤Cache写策略
4.指令系统
1）指令格式
①指令的基本格式
②定长操作码指令格式
③扩展操作码指令格式
2）指令的寻址方式
①有效地址的概念
②数据寻址和指令寻址
③常见寻址方式
3）CISC和RISC的基本概念
5.中央处理器（CPU）
1）CPU的功能和基本结构
2）指令执行过程
3）数据通路的功能和基本结构
4）控制器的功能和工作原理
①硬布线控制器
②微程序控制器：微程序、微指令和微命令
6.总线
1）总线概述
①总线的基本概念
②总线的分类
③总线的组成及性能指标
2）总线仲裁
①集中仲裁方式
②分布仲裁方式
3）总线操作和定时
①同步定时方式
②异步定时方式
7.输入输出（I/O）系统
1）I/O系统基本概念
2）I/O接口（I/O控制器）
①I/O接口的功能和基本结构
②I/O端口及其编址
3）I/O方式
①程序查询方式
②程序中断方式
中断的基本概念；中断响应过程；中断处理过程；多重中断和中断屏蔽的概念。
③DMA方式
DMA控制器的组成；DMA传送过程。
《操作系统》
（一）考查目标
1.了解操作系统在计算机系统中的作用、地位、发展和特点。
2.理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。
3.能够运用所学的操作系统原理、方法与技术分析问题和解决问题。
（二）考查内容
1.操作系统概述
1）操作系统的概念、特征、功能和提供的服务
2）操作系统的发展与分类
3）操作系统的运行环境
①内核态与用户态
②中断
③系统调用
2.进程管理
1）进程与线程
①进程概念
②进程的状态与转换
③进程控制
④进程组织
⑤进程通信
⑥线程概念
2）处理机调度
①调度的基本概念
②调度时机、切换与过程
③调度的基本准则
④调度方式
⑤典型调度算法
先来先服务调度算法，短作业优先调度算法，时间片轮转调度算法，优先级调度算法，高响应比优先调度算法，多级反馈队列调度算法。
3）同步与互斥
①进程同步的基本概念
②实现临界区互斥的基本方法
③信号量
④管程
⑤经典同步问题
生产者-消费者问题，读者-写者问题，哲学家进餐问题。
4）死锁
①死锁的概念
②死锁处理策略
③死锁预防
④死锁避免
系统安全状态，银行家算法。
⑤死锁检测和解除
3.内存管理
1）内存管理基础
①内存管理概念
程序装入与链接，逻辑地址与物理地址空间，内存保护。
②交换与覆盖
③连续分配管理方式
④非连续分配管理方式
分页管理方式，分段管理方式，段页式管理方式。
2）虚拟内存管理
①虚拟内存基本概念
②请求分页管理方式
③页面置换算法
最佳置换算法(OPT)，先进先出置换算法(FIFO)，最近最少使用置换算法(LRU)，时钟置换算法(CLOCK)。
④页面分配策略
⑤工作集
⑥抖动
4.文件管理
1）文件系统基础
①文件概念
②文件的逻辑结构
顺序文件，索引文件，索引顺序文件。
③目录结构
文件控制块和索引节点，单级目录结构和两级目录结构，树形目录结构
2）磁盘组织与管理
①磁盘的结构
②磁盘调度算法
5.输入输出(I/O)管理
1）I/O控制方式
2）I/O调度概念
3）高速缓存与缓冲区
4）设备分配与回收
5）假脱机技术(SPOOLing)
《计算机网络》
（一）考查目标
1.掌握计算机网络的基本概念、基本原理和基本方法。
2.掌握计算机网络的体系结构和典型网络协议，了解典型网络的组成和特点，理解典型网络设备的工作原理。
3.能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。
（二）考查内容
1.计算机网络体系结构
1）计算机网络概述
①计算机网络的概念、组成与功能
②计算机网络的分类
③计算机网络的标准化工作及相关组织
2）计算机网络体系结构与参考模型
①计算机网络分层结构
②计算机网络协议、接口、服务等概念
③TCP/IP模型及计算机网络五层架构模型
2.物理层
1）通信基础
①信道、信号、宽带、码元、波特、速率、信源与信宿等基本概念
②电路交换、报文交换与分组交换
③数据报与虚电路
2）传输介质
①双绞线、同轴电缆、光纤与无线传输介质
②物理层接口的特性
3）物理层设备
①中继器
②集线器
3.数据链路层
1）数据链路层的功能
2）组帧
3）差错控制
①检错编码
②纠错编码
4）流量控制与可靠传输机制
①流量控制、可靠传输与滑动窗口机制
②停止-等待协议
③选择重传协议(SR)
5）介质访问控制
①信道划分
频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。
②随机访问
CSMA/CD协议，CSMA/CA协议。
6）局域网
①局域网的基本概念与体系结构
②以太网与IEEE 802.3
③IEEE 802.11
7）广域网
①广域网的基本概念
②PPP协议
4．网络层
1）网络层的功能
①网络互联
②路由与转发
③拥塞控制
2）路由算法
①静态路由与动态路由
②距离-向量路由算法
3）IPv4
①IPv4分组
②IPv4地址与NAT
③子网划分、路由聚集、子网掩码与CIDR
④ARP协议、DHCP协议与ICMP协议
4）IPv6
①IPv6的主要特点
②IPv6地址
5）路由协议
①自治系统
②域内路由与域间路由
③RIP路由协议
6）IP组播
①组播的概念
②IP组播地址
7）网络层设备
①路由器的组成和功能
②路由表与路由转发
5.传输层
1）传输层提供的服务
①传输层的功能
②传输层寻址与端口
③无连接服务与面向连接服务
2）UDP协议
①UDP数据报
②UDP校验
3）TCP协议
①TCP段
②TCP连接管理
③TCP可靠传输
④TCP流量控制与拥塞控制
6.应用层
1）网络应用模型
①客户/服务器模型
②P2P模型
2）DNS系统
①层次域名空间
②域名服务器
③域名解析过程
3）FTP
①FTP协议的工作原理
②控制连接与数据连接
4）电子邮件
①电子邮件系统的组成结构
②电子邮件格式与MIME
③SMTP协议与POP3协议
5）WWW
①WWW的概念与组成结构
②HTTP协议
三、试卷题型及比例
试卷采用客观题型和主观题型相结合的形式，主要包括选择题、填空题、简答题和综合应用题。
四、考试形式及时间
本试卷满分为150分，考试时间为180分钟，考试形式为闭卷、笔试。
五、参考书目
1.严蔚敏编著《数据结构》（C语言版），北京：清华大学版社，2012年5月
2.严蔚敏编著《数据结构题集》（C语言版），北京：清华大学出版社，2012年5月
3.李春葆编著《数据结构教程》，北京：清华大学出版社，2013年1月
4.唐朔飞编著《计算机组成原理》，北京：高等教育出版社，1999年
5.唐朔飞编著：《计算机组成原理学习指导与习题解答》，北京：高等教育出版社，2005年9月
6.汤小丹，梁红兵，哲凤屏，汤子瀛编著《计算机操作系统》（第四版），西安：西安电子科技大学出版社，2014年5月
7.梁红兵，汤小丹编著《计算机操作系统》学习指导与题解(第四版)，西安：西安电子科技大学出版社，2014年5月
8.谢希仁主编《计算机网络》（第7版），北京：电子工业出版社，2017年1月
原文标题：河北建筑工程学院2022年硕士研究生初试自命题科目考试大纲
