一、考试基本要求及适用范围概述

　　计算机基础理论考试主要包括数据结构和操作系统两部分。

　　数据结构部分要求考生掌握数据结构的基本概念和术语。掌握包括线性表、栈和队列、串、数组和特殊矩阵、树和二叉树以及图在内的各种数据结构的基本概念、逻辑结构与存储结构，以及在这些结构的基础上的相关算法实现。能够针对具体问题选择合适的数据结构抽象建模，设计合适的存储结构，并采用C/C++、Java、Python或类C语言描述等程序设计语言基本运算的算法实现。掌握各种查找、排序算法。能够对基本算法进行复杂度分析。

　　操作系统部分主要考察学生对操作系统基本概念、结构、策略，以及一些基本的算法、处理过程的理解与掌握。对构成系统的进程管理、存储管理、设备管理、文件系统等各模块的工作机理及设计方法的掌握。重点考察操作系统的设计方法与实现技术，要求学生能够运用操作系统原理、方法与技术分析问题和解决问题。

　　本考试大纲适用于计算机科学与技术、农业信息化技术专业。

　　二、考试形式

　　闭卷笔试

　　三、考试内容和要求

　　数据结构和操作系统各占约50%，具体考试内容和要求如下：

　　第一部分数据结构

　　1.数据结构概述

　　掌握数据结构的基本概念和术语，包括数据、数据元素、数据项、数据对象、数据结构、数据的逻辑结构、数据的存储结构、数据类型、抽象数据类型。

　　掌握算法特性、算法的时间复杂度分析、算法的空间复杂度分析。

　　2.线性表

　　理解线性表的基本概念。

　　掌握线性表的顺序存储结构及其算法实现。

　　掌握线性表的链式存储结构及其算法实现，包括单链表、双向链表、循环链表。

　　3.栈和队列

　　掌握栈及其特性，理解栈的抽象数据类型。

　　掌握顺序栈及其基本算法实现、链栈及其基本算法实现。

　　理解函数调用、递归的实现过程、能够利用栈解决表达式求值、括号匹配等问题。

　　掌握队列及其特性，理解队列的抽象数据类型。

　　掌握循环队列及其基本运算实现、链队列及其基本运算实现。

　　能够利用队列解决银行排队、二叉树层序遍历、图的广度优先遍历等问题。

　　4.串、数组和广义表

　　掌握串的基本概念及操作、串的定长顺序存储及基本运算。

　　掌握数组的定义及操作、数组的顺序存储、特殊矩阵的压缩存储、随机稀疏矩阵的压缩存储。

　　理解广义表的基本概念

　　5.树和二叉树

　　掌握树的定义及基本术语。

　　掌握二叉树的定义、二叉树的性质以及二叉树的存储结构。

　　掌握二叉树遍历方法，包括二叉树的递归遍历、二叉树的非递归遍历，并能够应用二叉树遍历算法解决问题。

　　掌握线索二叉树的定义和存储结构、二叉树的线索化、线索二叉树中结点的前驱和后继查找方法。

　　掌握树的存储、森林的存储结构、树和森林的遍历、树、森林和二叉树的相互转换。

　　掌握哈夫曼树的定义及特性，并能应用哈夫曼树解决实际问题。

　　6.图

　　掌握图的基本概念，包括图、无向图、有向图、完全图、图的连通性等。

　　掌握图的邻接矩阵和邻接表等存储结构。

　　掌握图的深度优先和图的广度优先搜索遍历算法。

　　掌握最小生成树算法(Kruska算法和Prim算法)、求某个顶点(单源点)到其余各顶点的最短路径(Dijkstra算法)、拓扑排序、关键路径。

　　7.排序

　　理解排序的基本概念。

　　掌握插入排序(包括直接插入排序、希尔排序)、交换排序(包冒泡排序、快速排序)、选择排序(包括简单选择排序、堆排序)、归并排序、基数排序等基本排序算法及其复杂度分析。

　　8.查找

　　理解查找的基本概念、查找成功和查找失败的平均查找长度。

　　掌握顺序表的查找、有序表的折半查找。

　　掌握二叉排序树(包括二次排序树的定义和特点、二叉排序树的创建、插入、删除结点)，掌握平衡二叉树的定义。

　　掌握哈希函数的确定方法、处理冲突的方法。

　　第二部分操作系统

　　1.操作系统概述

　　掌握操作系统的计算机体系中的地位和作用。

　　计算机的发展过程中出现的各种不同类型的操作系统以及它们的特点，了解常用的操作系统以及操作系统的现状。

　　掌握操作系统的并发、共享、虚拟、异步等基本特征以及在操作系统中的一些重要的概念，如并行、并发、时间片等。

　　掌握操作系统为用户和应用程序所提供的各种服务、接口和系统调用等功能。

　　掌握操作系统结构设计以及它们的特征和优缺点。

　　2.进程的描述与控制

　　掌握进程的基本概念，包括进程的结构特征、PCB、作业、任务等，掌握进程的状态以及转换时机。

　　掌握进程控制的机制，包括创建、终止、阻塞、唤醒等。

　　掌握进程同步的意义、概念和方法。掌握临界区的概念以及进程同步的四个准则。

　　掌握生产者-消费者问题、哲学家进餐问题、读者-写者问题等经典进程同步问题以及用信号量机制来解决进程同步问题的方法，能熟练应用同步信号量和互斥信号量。

　　理解管程机制。

　　掌握进程通信的方法，包括共享存储系统、消息传递系统、管道。

　　掌握线程的概念以及线程和进程的区别。掌握用户和内核线程的定义、区别。掌握多线程模式下用户和内核线程的关系。

　　3.处理机调度与死锁

　　掌握处理机调度的基本类型、基本概念以及调度准则、衡量调度算法的指标。

　　掌握先来先服务、短作业(进程)优先、高响应比优先、时间片轮转等基本的调度算法以及抢占式调度和非抢占式调度的区别。

　　理解多级队列调度和多级反馈队列调度的算法。

　　掌握死锁的产生原因、定义和四个必要条件。

　　掌握处理死锁的基本方法。掌握用银行家算法来避免死锁。

　　理解资源分配图以及死锁的检测和解除机制。

　　4.存储器管理

　　理解存储管理中的基本概念，包括存储器的层次结构、地址绑定、逻辑与物理地址空间、动态重定位、动态装入、动态链接、交换、碎片等。

　　掌握存储管理的三种主要的方法：连续分配、分页和分段存

　　储管理，并掌握这三种机制的方法、算法、区别和联系，其中重点掌握分页存储管理。

　　理解虚拟存储器的概念以及实现方法。

　　掌握请求式分页系统的原理。

　　掌握FIFO、最佳、LRU、Clock、最少使用、页面缓冲等页面置换算法。

　　掌握抖动的原因以及检测解决的方法。

　　理解提高虚拟存储器效率的多种方法。

　　理解请求分段系统的原理。

　　5.输入输出系统

　　掌握现代I/O系统的两个基本思想：设备驱动和与设备无关性。

　　掌握I/O系统的结构、I/O系统的功能、模型。

　　理解I/O设备的分类、控制器、DMA、通道等内容。

　　熟悉中断机构运行机制。

　　掌握I/O控制方式、设备独立性软件。

　　掌握SPOOLing系统运行机制。

　　理解磁盘的结构和管理机制。

　　掌握磁盘的性能和磁盘调度算法。

　　6.文件管理

　　理解文件和文件系统的概念、结构、类型，文件的基本操作等内容。

　　掌握文件的逻辑结构及访问方式。

　　理解文件控制块、索引节点等概念。

　　掌握常用目录结构及其优缺点。掌握目录查询技术。

　　理解文件的共享和保护方式。

　　7.磁盘存储器管理

　　掌握三种外存组织方式：连续、链接和索引，以及它们的优缺点。

　　掌握文件存储空间的管理方法，特别是位示图和成组链接法。

　　理解提高磁盘I/O速度的途径和提高磁盘可靠性的技术。

　　了解存储新技术和数据一致性控制方法。

　　四、主要参考教材

　　1.周桂红等编，《数据结构》，天津：南开大学出版社，2016年

　　2.汤小丹等编，《计算机操作系统(慕课版)》，北京：人民邮电出版社，2021年

　　　注：本文文字转载自河北农业大学研究生院，如有侵权，请联系删除。