数据结构部分

考试内容范围:

绪论

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. 要求考生了解计算机系统的主要性能指标。

二、 计算机中的信息表示

要求考生熟练掌握进位计数制、机器数以及定点和浮点表示法。

要求考生掌握指令格式及可扩展操作码指令系统设计方法。

要求考生熟练掌握常见寻址方式并能够正确计算操作数地址，掌握外设端口编址方式。

要求考生了解常见指令类型，理解RISC和CISC两种指令集的各自特点。

三、 CPU子系统

要求考生熟练掌握定点数的四则运算的算法、运算规则及“溢出”判断方法。

要求考生理解浮点数四则运算流程并能正确实现计算，掌握浮点数对阶及规格化的含义。

要求考生理解CPU的逻辑组成及CPU内部的数据通路结构。

要求考生掌握指令执行的流程（寄存器传输级微操作序列），了解微命令序列。

要求考生理解组合逻辑控制器和微程序控制器的基本思想、逻辑组成及各自优缺点。

要求考生掌握微指令格式、微命令编码方式以及常见的微地址形成方式。

四、 存储子系统

要求考生理解存储子系统的层次结构，能对Cache-主存存储层次和主存-辅存存储层次的异同点进行比较分析。

要求考生理解半导体静态存储器和动态存储器存储信息的原理，了解磁表面存储器的存储原理和常用磁记录编码方式。

要求考生掌握主存储器的逻辑结构设计方法、动态存储器的刷新以及常见差错控制编码（奇偶校验码、海明码、循环冗余码）。

要求考生理解磁盘信息分布、寻址信息以及磁盘主要性能指标。

要求考生理解Cache-主存地址映像方式并能正确进行地址变换计算。

五、I/O子系统及输入输出设备

要求考生掌握总线定义，了解总线分类及常用总线标准。

要求考生掌握程序查询、中断、DMA传送方式的基本概念及各自优缺点和适用场合。

要求考生理解中断全过程及CPU进入中断响应阶段的必要条件。

要求考生理解DMA传输的三个阶段及DMA与中断的关系。

考试总分：60分     考试时间：1.2小时    考试方式：笔试

考试题型：选择题（10分）

简答题（20分）

综合设计题（30分）

参考书目（材料）

纪禄平 刘辉 罗克露 等编著，计算机组成原理（第3版），北京：电子工业出版社