考试科目 820 计算机专业基础 考试形式 笔试（闭卷） 考试时间 180 分钟 考试总分 150 分 本科目包括数据结构和计算机操作系统两门课程，总分 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. 填空题（ 10 分） 2. 单选 题（ 20 分） 3. 简答题（ 30 分） 4. 算法题（ 15 分） 其中算法题分为阅读、修改和编写算法三类： (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) 文件存储空间的管理 技术 ： 位示图、空闲链表、索引 三、题型及分值比例 1. 填空题（ 10 分） 2. 单选 题（ 10 分） 3. 简答题（ 20 分） 4. 应用题（ 35 分）