考试科目名称: 计算机专业基础综合
数据结构部分
考试内容范围:
一、绪论
1. 了解有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。
二、线性表
1. 了解线性表的逻辑结构特性是数据元素之间存在线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。
2. 熟练掌握顺序存储结构和链式存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。
3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
三、栈和队列
1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
2. 熟练掌握栈类型的两种实现方法。
3. 熟练掌握循环队列和链队列的基本操作实现算法。
4. 理解递归算法执行过程中栈的状态变化过程。
四、串
1. 理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。
2. 理解串类型的各种存储表示方法。
五、 数组和广义表
1. 理解多维数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”和“以列为主”的存储表示中的地址计算方法。
2. 掌握特殊矩阵的压缩存储表示方法。
3. 理解稀疏矩阵的压缩存储方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。
六、 树和二叉树
1. 领会树和二叉树的类型定义，理解树和二叉树的结构差别。
2. 熟记二叉树的主要特性，并掌握它们的证明方法。
3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。
4. 理解二叉树的线索化过程以及在线索化树上找给定结点的前驱和后继的方法。
5. 熟练掌握二叉树和树的各种存储结构及其建立的算法。
6. 学会编写实现树的各种操作的算法。
7. 了解哈夫曼树的特性，掌握建立哈夫曼树和哈夫曼编码的方法。
七、 图
1. 领会图的类型定义。
2. 熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。
3. 熟练掌握图的两种遍历算法。
4. 理解各种图的应用问题的算法及其应用场合。
八、 查找
1. 理解查找表的结构特点以及各种表示方法的适用性。
2. 熟练掌握以顺序表或有序表表示静态查找表时的查找方法。
3. 熟练掌握二叉排序树的构造和查找方法。
4. 理解平衡二叉排序树的构造过程。
5. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的查找表的实质性的差别。
6. 掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
九、 内部排序
1. 理解排序的定义和各种排序方法的特点，并能加以灵活应用。
2. 掌握各种排序方法的时间复杂度和空间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。
3. 理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。
十、 文件
1. 熟悉各类文件的特点、构造方法以及如何实现检索、插入和删除等操作。
2. 了解各种文件的适用场合。
考试总分：90分 考试时间：1.8小时 考试方式：笔试
考试题型：选择题（30分）
判断题（10分）
填空题（10分）
计算题（30分）
算法题（10分）
参考书目（材料）
严蔚敏 吴伟民编著，数据结构（C语言版），北京：清华大学出版社
计算机组成原理部分
考试内容范围:
一、计算机硬件系统组成的基本概念
1. 要求考生理解计算机系统的层次结构。
2. 要求考生掌握计算机硬件系统的组成、冯·诺依曼计算机的要素和“存储程序”工作原理。
3. 要求考生了解信息的数字化表示所需的主要步骤及优点。
4. 要求考生了解计算机系统的主要性能指标。
二、计算机中的信息表示
1．要求考生熟练掌握进位计数制、机器数以及定点和浮点表示法。
2．要求考生掌握指令格式及可扩展操作码指令系统设计方法。
3．要求考生熟练掌握常见寻址方式并能够正确计算操作数地址，掌握外设端口编址方式。
4．要求考生了解常见指令类型，理解RISC和CISC两种指令集的各自特点。
三、CPU子系统
1．要求考生熟练掌握定点数的四则运算的算法、运算规则及“溢出”判断方法。
2．要求考生理解浮点数四则运算流程并能正确实现计算，掌握浮点数对阶及规格化的含义。
3．要求考生理解CPU的逻辑组成及CPU内部的数据通路结构。
4．要求考生掌握指令执行的流程（寄存器传输级微操作序列），了解微命令序列。
5．要求考生理解组合逻辑控制器和微程序控制器的基本思想、逻辑组成及各自优缺点。
6．要求考生掌握微指令格式、微命令编码方式以及常见的微地址形成方式。
四、存储子系统
1．要求考生理解存储子系统的层次结构，能对Cache-主存存储层次和主存-辅存存储层次的异同点进行比较分析。
2. 要求考生理解半导体静态存储器和动态存储器存储信息的原理，了解磁表面存储器的存储原理和常用磁记录编码方式。
3. 要求考生掌握主存储器的逻辑结构设计方法、动态存储器的刷新以及常见差错控制编码（奇偶校验码、海明码、循环冗余码）。
4. 要求考生理解磁盘信息分布、寻址信息以及磁盘主要性能指标。
5. 要求考生理解Cache-主存地址映像方式并能正确进行地址变换计算。
五、I/O子系统及输入输出设备
1. 要求考生掌握总线定义，了解总线分类及常用总线标准。
2. 要求考生掌握程序查询、中断、DMA传送方式的基本概念及各自优缺点和适用场合。
3. 要求考生理解中断全过程及CPU进入中断响应阶段的必要条件。
4. 要求考生理解DMA传输的三个阶段及DMA与中断的关系。
考试总分：60分 考试时间：1.2小时 考试方式：笔试
考试题型： 选择题（10分）
简答题（20分）
综合设计题（30分）
参考书目（材料）
纪禄平 刘辉 罗克露 等编著，计算机组成原理（第3版），北京：电子工业出版社
考试科目名称: 软件工程专业基础综合
数据结构部分
考试内容范围:
一、绪论
1. 了解有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。
二、线性表
1. 了解线性表的逻辑结构特性是数据元素之间存在线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。
2. 熟练掌握顺序存储结构和链式存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。
3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
三、栈和队列
1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
2. 熟练掌握栈类型的两种实现方法。
3. 熟练掌握循环队列和链队列的基本操作实现算法。
4. 理解递归算法执行过程中栈的状态变化过程。
四、串
1. 理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。
2. 理解串类型的各种存储表示方法。
五、 数组和广义表
1. 理解多维数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”和“以列为主”的存储表示中的地址计算方法。
2. 掌握特殊矩阵的压缩存储表示方法。
3. 理解稀疏矩阵的压缩存储方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。
六、 树和二叉树
1. 领会树和二叉树的类型定义，理解树和二叉树的结构差别。
2. 熟记二叉树的主要特性，并掌握它们的证明方法。
3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。
4. 理解二叉树的线索化过程以及在线索化树上找给定结点的前驱和后继的方法。
5. 熟练掌握二叉树和树的各种存储结构及其建立的算法。
6. 学会编写实现树的各种操作的算法。
7. 了解哈夫曼树的特性，掌握建立哈夫曼树和哈夫曼编码的方法。
七、 图
1. 领会图的类型定义。
2. 熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。
3. 熟练掌握图的两种遍历算法。
4. 理解各种图的应用问题的算法及其应用场合。
八、 查找
1. 理解查找表的结构特点以及各种表示方法的适用性。
2. 熟练掌握以顺序表或有序表表示静态查找表时的查找方法。
3. 熟练掌握二叉排序树的构造和查找方法。
4. 理解平衡二叉排序树的构造过程。
5. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的查找表的实质性的差别。
6. 掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
九、 内部排序
1. 理解排序的定义和各种排序方法的特点，并能加以灵活应用。
2. 掌握各种排序方法的时间复杂度和空间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。
3. 理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。
十、 文件
1. 熟悉各类文件的特点、构造方法以及如何实现检索、插入和删除等操作。
2. 了解各种文件的适用场合。
考试总分：90分 考试时间：1.8小时 考试方式：笔试
考试题型：选择题（30分）
判断题（10分）
填空题（10分）
计算题（30分）
算法题（10分）
参考书目（材料）
严蔚敏 吴伟民编著，数据结构（C语言版），北京：清华大学出版社
操作系统部分
考试内容范围:
一、操作系统概述
1．理解操作系统的概念、特征、功能和提供的服务。
2．了解操作系统的发展与分类。
3．了解操作系统的运行环境。
二、进程管理
1．理解进程概念、进程的状态与转换、进程控制、进程组织、进程通信、线程概念与多线程模型。
2．掌握处理机调度的基本概念、调度时机、切换与过程、调度的基本准则、调度方式。
3．熟练掌握典型调度算法：先来先服务调度算法；短作业（短进程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。
4．理解进程同步的基本概念、实现临界区互斥的基本方法、信号量、管程、经典同步问题。
5．熟练掌握死锁的概念、死锁处理策略、死锁预防、死锁避免（系统安全状态、银行家算法）、死锁检测和解除。
三、内存管理
1．理解内存管理概念、程序装入与链接、逻辑地址与物理地址空间、内存保护。
2．熟练掌握交换与覆盖、连续分配管理方式、非连续分配管理方式。
3．理解分页管理方式、分段管理方式、段页式管理方式。
4．理解虚拟内存基本概念、请求分页管理方式，并熟练掌握页面置换算法（OPT、FIFO、LRU、CLOCK）。
5．理解页面分配策略、抖动、工作集。
6． 理解请求分段管理方式、请求段页式管理方式。
四、文件管理
1．理解并熟悉文件概念、文件的逻辑结构、目录结构、文件控制块和索引节点、文件共享、文件保护。
2．理解并熟悉文件系统层次结构、目录实现、文件实现。
3． 熟练掌握磁盘的结构、磁盘调度算法、磁盘的管理。
五、输入输出（I/O）管理
1．理解I/O管理，I/O 设备、I/O 管理目标、I/O 管理功能、I/O 应用接口、I/O 控制方式。
2．熟练掌握I/O调度，高速缓存与缓冲区、设备分配与回收、假脱机技术（SPOOLing）、出错处理。
考试总分：60分 考试时间：1.2小时 考试方式：笔试
考试题型： 选择题（10分）
填空题（10分）
应用题（40分）
参考书目（材料）
汤小丹 梁红兵 哲凤屏 汤子瀛编著，计算机操作系统（第四版），西安：西安电子科技大学出版社
