初试《数据结构和软件工程》科目考试大纲

一、考查目标

理解数据结构和软件工程的基本概念及如何利用抽象数据类型进行程序设计；掌握线性表、栈和队列、串、数组和广义表、树、图等典型数据结构及相关算法，以及排序、查找等重要算法；掌握算法的时间分析和空间分析的技术；软件工程基本思想和基本方法。具备分析和解决现实世界问题在计算机中如何表示和处理的能力，具有软件开发的基本能力。

二、考试形式与试卷结构

（一）试卷满分及考试时间
满分为150分，考试时间为3小时。
（二）答题方式
闭卷、笔试。
（三）试卷内容结构
算法及其分析(5%)、线性表及其应用(10%)、栈和队列及应用(20%)、树及应用(20%)、图及应用(20%)、查找排序(20%)、其他内容(10%)。
（四）试卷题型结构
作图题、计算题（150分）。

三、考查内容

（一）算法及分析
掌握算法的时间复杂度及空间复杂度计算方法,从而分析算法优劣。
（二）线性表及其应用
主要内容为：
（1）线性表的逻辑结构定义及ADT。
（2）线性表的顺序存储结构及操作的实现。
（3）线性表的链式存储结构及操作的实现。
（4）线性表的基本应用。
（三）栈和队列及其应用
主要内容为：
（1）栈的逻辑结构及特点。
（2）栈的顺序存储结构及其基本操作的实现。
（3）栈的应用。
（4）队列的逻辑结构及特点。
（5）队列的链式存储及其基本操作的实现。
（6）循环队列的特点及操作的实现。
（7）队列的应用。
（四）树及应用
主要内容为：
（1）树的基本概念及术语。
（2）二叉树的定义、特性及二叉树存储。
（3）二叉树遍历的递归算法及非递归算法。
（4）树的存储。
（5）最优二叉树——赫夫曼树。
（五）图及应用
主要内容为：
（1）图的基本概念。
（2）图的存储——邻接矩阵和邻接表。
（3）图的遍历算法——深度优先算法，广度优先算法。
（4）图的应用——拓扑排序，关键路径，最小生成树，最短路径。
（六）查找排序
主要内容为：
（1）静态查找表——顺序表的查找及折半查找。
（2）动态查找表——二叉排序树和平衡二叉树的构造、插入、删除及查找过程。
（3）哈希表——哈希表的构造和查找，并计算平均查找长度。
（4）常见的内部排序过程及算法——直接插入排序、希尔排序、快速排序、队排序、归并排序。分析各算法优劣。
（七）其他内容
根据具体应用，能够选择合适的逻辑结构及存储结构，并实现算法。
软件工程基本思想和基本方法。

四、考试用具说明

考试使用黑色笔作答,允许在考试中使用直尺、三角板、计算器。