2018年沈阳建筑大学信息学院同等学力加试《数据结构》科目考试大纲

同等学力加试数据结构科目考试大纲

一、考查目标

考查学生掌握数值计算问题在计算机中进行处理的基本原理和方法，掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，能够在不同存储结构上实现不同逻辑结构的运算，并能解决相关的实际问题，对算法设计的方式和技巧有所体会，有较好的分析处理数据的能力。

二、考试形式与试卷结构

（一）试卷满分及考试时间

满分为100分，考试时间为2小时。

（二）答题方式

闭卷、笔试。

（三）试卷内容结构

内容结构为各部分知识点在试卷中所占的比例。

1 数据结构基本概念（10%左右）

2 线性结构（25%左右）

3 树状结构（25%左右）

4 图（15%左右）

5 查找（10%左右）

6 内部排序（15%左右）

（四）试卷题型结构

客观题：选择题20%左右，判断题20%左右；

算法设计30%左右；

算法综合应用30%左右

三、考查内容

（一）绪论

   1 掌握数据、数据元素、数据对象、数据结构、存储结构和数据类型的概念和术语的含义；

   2 理解算法五要素的确切含义；

   3 掌握算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。

  （二）线性表

1 掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系；

2 熟练掌握线性表的顺序存储结构和链式存储结构的描述方法及循环链表, 双向链表的特点；

3 熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；

4 能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点及其适用的场合。

  （三）栈和队列

1 熟练掌握栈和队列的结构特性----操作受限的线性表；

2 熟练掌握栈类型在两种存储结构表示时的基本操作实现方法；

3 熟练掌握循环队列和链队列的基本操作实现算法；

4 熟练掌握栈和队列的满和空的条件和它们的描述方法；

5 熟悉栈和队列的典型应用，如：数制转换、表达式求值等。

  （四）串

1 掌握串的结构特性----数据元素为字符的线性表；

2 熟悉串的七种基本操作;

  （五）数组

1 掌握高维数组存在一维数组中的两种存储表示方法及以行为主(低下标优先)的存储结构中的地址计算, 特别注意下标是从0开始或从1开始；

2 掌握对特殊矩阵(对称矩阵,下三角矩阵等) 进行压缩存储时的下标变换公式；

3 了解稀疏矩阵的三元组压缩存储表示方法及适用范围。

  （六）树和二叉树

1 熟悉树的基本定义及其相关的术语的含义（如孩子、兄弟,深度、度等概念）；

2 熟练掌握二叉树的结构特性，了解相应的证明方法, 理解常见的二叉树（如满二叉树，完全二叉树，Huffman树，平衡二叉树，排序二叉树和判定树）有关理论结论；

3 熟悉二叉树的二叉链和线索二叉树存储结构特点及适用范围；

4 熟悉三种遍历二叉树的递归算法（先序, 中序和后序）；

5 掌握二叉树线索化的实质及线索化的过程；

6 掌握树和森林与二叉树的转换, 及其各自遍历的对应关系；

7 了解实现树的各种操作的算法；

8 掌握优树的特性，掌握Huffman树及其应用。

  （七）图

1 掌握图的定义和术语（如顶点，边，度及其相互之间的数量关系,连通性与生成树等）；

2 掌握图的两种存储结构：数组表示法（邻接矩阵）、邻接表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系；

3 掌握图的两种遍历策略：深度优先搜索和广度优先搜索；图的遍历和树的遍历之间的类似与差异；

4 熟悉图的小生成树的生成方法（Prim方法和Kruskal方法）；

  （八）查找

1 熟练掌握顺序表和有序表的查找方法（顺序查找和二分查找）；

2 掌握查找效率的计算方法-----平均查找长度；

3 熟练掌握二叉排序树的构造和查找方法；

4 了解平衡二叉树的维护平衡的方法。

 （九）内部排序

1 掌握排序的定义和各种排序方法的基本思想及其特点；

2 了解各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的方法可以分为插入排序、交换排序、选择排序、归并排序和基数排序；

3 熟练掌握快速排序和堆排序等方法的实例排序过程；

4 能够进行各种排序方法的时间复杂性(平均情况与坏情况)估计或分析；

5 一般了解排序方法“稳定”的含义。

四、考试用具说明

黑色笔答题，无需携带计算器、直尺、三角板、量角器、圆规等特殊用具。