2024年电子科技大学非全日制研究生招生考试《计算机专业基础》考试大纲

　　本科目包括《数据结构》和《计算机操作系统》两门课程，总分 150 分，两门课程各占 75 分

　　《数据结构》

　　一、总体要求

　　《数据结构》是计算机程序设计的重要理论技术基础，是计算机科学与技术学科的核心课程要求：

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

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

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

　　二、内容

　　1. 数据结构及算法的相关概念和术语

　　(1) 数据结构及算法的概念

　　(2) 数据的逻辑结构和存储结构

　　(3) 算法的定义及特性

　　(4) 算法时间复杂度和空间复杂度的分析方法2.线性表

　　(1) 线性表的定义

　　(2) 线性表的基本操作及在顺序存储及链式存储上的实现

　　(3) 各种变形链表(循环链表、双向链表、带头结点的链表等)的表示和基本操作的实现

　　(4) 递归过程的特点及实现方法

　　(5) 栈和队列的基本概念;栈和队列的顺序存储结构、链式储存结构及其存储特点

　　(6) 栈和队列的应用

　　(7) 循环队列的判满、判空方法

　　(8) 特殊矩阵的压缩储存

　　3. 广义表的基本概念、存储结构和基本操作

　　4. 树和二叉树

　　(1) 树与森林的基本概念

　　(2) 树与森林的存储结构及遍历

　　(3) 二叉树的定义及 6 大性质

　　(4) 二叉树的顺序储存与链式储存结构

　　(5) 二叉树的先序、中序、后序三种遍历方式的关系以及实现;层序遍历的实现

　　(6) 线索二叉树的基本概念与构造方法

　　(7) 树与二叉树的应用：二叉排序树;二叉平衡树;哈夫曼树与哈夫曼编码 5.图

　　(1) 图的基本概念和术语

　　(2) 图的存储结构：邻接矩阵、邻接表、逆邻接表

　　(3) 遍历算法：深度优先搜索算法和广度优先搜索算法

　　(4) 应用：最小生成树;最短路径，拓扑排序和关键路径6.查找

　　(1) 查找的基本概念;静态查找与动态查找

　　(2) 顺序查找、折半查找、索引查找

　　(3) 哈希查找

　　哈希函数的基本构造方法，解决地址冲突的基本策略

　　(4) 各种查找算法的时间复杂度和空间复杂度7.排序

　　(1) 排序的基本概念

　　(2) 插入排序

　　(3) 简单选择排序

　　(4) 希尔排序

　　(5) 快速排序

　　(6) 堆排序

　　(7) 归并排序

　　(8) 基数排序

　　(9) 排序算法的比较

　　其中算法题分为阅读、修改和编写算法三类：

　　(1) 阅读算法：阅读指定算法，回答使用的数据结构、算法实现的功能或执行的结果;

　　(2) 修改算法：阅读指定算法，指出算法的错误并修正;指出算法的不足并改进;按给定功能填写 算法空缺部分;

　　(3) 编写算法：根据算法功能要求，选择或者设计合适的数据结构，用程序设计语言编写算法，实 现指定功能。

　　以上皆可分析给定或者设计的算法时空复杂度。

　　操作系统部分

　　一、总体要求

　　主要考察学生对操作系统基本概念、原理的理解程度，重点考察操作系统的设计方法与实现技术，

　　同时能够具备运用所学的操作系统原理、方法与技术分析问题和解决问题的能力。 二、内容

　　1. 操作系统的基本概念

　　1) 批处理与多道程序设计

　　2) 分时系统与实时系统

　　3) 操作系统的基本类型与特征

　　4) 并发与并行的概念

　　5) 操作系统的层次结构与功能模块

　　6) 程序的并发执行与顺序执行

　　2. 进程管理

　　1) 进程: 进程控制块、进程的几种基本状态与状态转换(进程的创建、进程的终止、进程的阻塞与唤醒、进程的挂起与激活等)

　　2) 进程的同步与互斥：临界资源、临界区、进程同步与互斥问题、信号量机制以及 P、V 操作、管程机制

　　3) 进程间通信：进程通信的类型(直接通信和间接通信方式)、消息传递系统中的几个问题、 消息缓冲队列通信机制

　　4) 线程与进程的调度:线程与进程的基本概念，调度的类型、调度队列模型、调度方式、进 程调度算法(先来先服务、短进程优先、时间片轮转、基于优先级的调度算法等)

　　5) 死锁:死锁的基本概念，死锁定理、死锁预防、死锁避免与处理死锁的基本方法、银行家

　　算法

　　6) 综合应用：生产者消费者问题、读者和写者问题、哲学家进餐问题等

　　3. 内存管理

　　1) 内存管理的需求：重定位、内存保护、内存共享

　　2) 程序的装入和链接：静态装入和可重定位装入、静态链接、动态链接、运行时动态链接。

　　3) 分区存储管理：分区方式(单一连续分区、固定分区、可变式分区)、分区分配算法(首 次适应算法、循环首次适应算法、最佳适应法、最坏适应法等)

　　4) 段式管理与页式管理：段、页、碎片等基本概念、段式管理与页式管理机制

　　5) 虚拟内存：局部性原理、虚拟内存概念、请求分段与请求分页、段页式管理、段页式地址 结构与地址转换、页面置换算法(OPT、先进先出、LRU、Clock、改进型 Clock 置换)、抖动

　　4. 设备管理

　　1) I/O 系统的：基本概念、I/O 控制方式(程序 I/0、中断、DMA、通道)、相关数据结构、缓冲管理(单缓冲、双缓冲、循环缓冲、缓冲池)

　　2) 磁盘管理与磁盘调度算法：SSTF 算法，SCAN 算法，CSCAN 算法，N-STEP-SCAN 算法，FSCAN 算法

　　3) 设备分配、设备处理、虚拟设备，Spooling 系统

　　5. 文件系统

　　1) 基本概念：文件和文件系统、目录、文件结构的物理结构和逻辑结构(顺序文件、索引顺序文件、索引文件、HASH 文件)、文件共享(基于索引节点、基于符号链接实现文件共享)

　　2) 外存分配方法：连续分配、链接分配、索引分配

　　3) 目录管理：单级目录、二级目录、多级目录

　　4) 文件存储空间的管理技术：位示图、空闲链表、索引