2014合肥师范学院专升本计算机《数据结构》考试大纲

计算机科学与技术专业《数据结构》考试大纲

专业性质：理工类（非师）
课程性质：《数据结构》是计算机专业的核心基础课程之一。数据是计算机处理的对象，本门课程研究的数据是非数值性、结构性的数据。学习本门课程要求掌握各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法，对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌握。
考核方式：闭卷考试

考核内容:
第一章  绪论
   数据结构的研究范畴；数据、数据元素、数据项、数据对象概念；逻辑结构、物理结构概念；算法分析（时间复杂度）。

第二章  线性表
    顺序表、链表特点；线性表在顺序表及链表中实现基本操作（查找、插入、删除等）的算法；有序表在链表中实现插入、删除、合并等操作的算法。

第三章  栈和队列
    栈的定义；给定入栈序列，如何得到一特定出栈序列；栈的表示；队列的定义；队列的顺序表示和实现—循环队列。

第四章  串
   串的定义和有关基本概念。

第五章  数组和广义表
   数组的定义；数组元素在内存中的地址计算方法。

第六章  树和二叉树
   树的定义及相关术语；二叉树的定义；二叉树的性质；二叉树的先序、中序、后序遍历方法；给出先序（或后序）+中序遍历序列，能画出这棵树，并写出对应后序（或先序）遍历序列；二叉树的先序、中序、后序遍历的递归算法及应用；树、森林与二叉树之间的转换；哈夫曼树的定义、构造及其应用。

第七章  图
    图的定义和术语；图的邻接矩阵表示法和邻接表表示法；深度优先搜索、广度优先搜索遍历；求最小生成树；拓扑排序序列。

第八章  查找
    顺序查找、折半查找、索引顺序查找对表的要求及查找效率；折半查找算法；二叉排序树的查找方法及算法；给出一组关键字、哈希函数和处理冲突的方法，构造哈希表，求平均查找长度。

第九章  内部排序
    直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序时间复杂度 、辅助空间、 稳定性；上述几种内部排序方法的特点；希尔排序、快速排序、堆排序的排序过程。

题型结构：选择题、填空题、判断题、应用题、算法设计。

参考书目：
　　　《数据结构》（C语言版），严蔚敏、吴伟民编著，清华大学出版社
　　　《数据结构》（C语言版），胡学钢编著，高等教育出版社
　　　《数据结构习题与解析》—A级（第3版）,李春葆，清华出版社