1、 951“ 数据结构 ” 复习 参考提纲 一、 考察目标 通信、 计算机学科专业基础综合考试涵盖数据结构学科专业基础课程。要求考生比较系统地掌握数据结构专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 二、 考试形式和试卷结构 1、 试卷满分及考试时间：本试卷满分为 150，考试时间为 180 分钟 2、 答题方式：闭卷，笔试 3、 试卷内容结构：数据结构 150 分 三、 总体要求 “数据结构 ”要求学生掌握数据 结构的基本理论和基本方法， 熟悉解决程序设计问题所需的基本数据结构和基础算法，掌握 各种程序设计中常用的数据
2、结构的基本概念、对应的逻辑结构和存储结构及其基本运算，各种数据结构的基本特点和典型应用场景。熟练使用基础数据结构进行算法程序设计。 四、 各章复习要点 （一）数据结构基本概念 1.复习内容 数据结构的 概念 ，数据结构的逻辑结构和物理结构， 程序设计的关键技术 。 2.具体要求 数据结构的 概念 、名词和术语 数据结构的逻辑结构 数据结构的物理结构 （二）线性表 1.复习内容 线性表的 基本概念和运算， 顺序表的基本运算 ， 单链表 、 循环链表 、双向链表的基本运算， 顺序表和链表的应用 实例分析 。 2.具体要求 线性表的概念和基本运算 线性表的顺序存储表示及算法 线性表的链式存储表示及算
3、法 顺序表及链表的应用 （三） 栈 和 队列 1.复习内容 栈和队列的基本概念 、基本操作 、 存储结构 和应用 。 2.具体要求 栈和队列的基本概念 和基本操作 栈和队列的顺序存储结构 栈和队列的链式存储结构 栈和队列的应用 （四）串 和数组 1.复习内容 串的 基本概念 、 运算和 存储结构 ， 模式匹配算法 ，数组的概念、存储结构，矩阵压缩存储。 2.具体要求 串 的基本概念 和基本操作 串 的存储结构 模式匹配算法 数组的概念 数组的存储结构 矩阵压缩存储 （五） 树 1.复习内容 数 、 二叉树 、 森林 、 线索二叉树的基本概念 ， 二叉树的遍历方法 ， 树和森林之间的转换方法 ，
4、 二叉树的应用 。 2.具体要求 树结构的基本概念、术语 二叉树的性质和存储表示。 二叉树的遍历及递归算法的运用 树和森林（存储表示、转化方法、树的遍历） 线索化技术（线索二叉树、线索的应用） 二叉树的应用（哈夫曼树及应用、二叉排序树） （ 六 ）图 1.复习内容 图的基本概念和存储结构 ， 图的遍历 ， 生成树和最小生成树 ， 最短路径 ， 拓扑排序 ， 关键路径 。 2.具体要求 图的基本概念、术语 图的存储方法（邻接矩阵、邻接表） 图的 DFS 和 BFS 搜索算法及相关应用 生成树和最小生成树（ Prime 算法、 Kruskal 算法） 最短路径 拓扑排序 关键路径 （ 七 ） 索引
5、结构与散列技术 1.复习内容 索引和散列技术的应用背景 ， 索引结构 ， 散列表的概念 ， 散列函数的构造方法 ， 解决冲突的方法 。 2.具体要求 索引结构的表示 索引结构的应用 散列表的概念 散列表的构造 散列表的查找 （ 八 ） 缩小规模算法 1.复习内容 分治与递归算法设计 ， 动态规划的基本要素 ， 贪心算法。 2.具体要求 递归与分治算法 动态规划算法 掌握贪心算法 五、 参考书目 1、 荣政等 ，数据结构与算法分析，西安电子科技大学出版 社， 2012. 2、 刘 彦明等 ，计算机软件技术基础（第一版），人民邮电出版社， 2005. 3、 严蔚敏 等 ，数据结构（ C 语言版）（第一版），清华大学出版社， 2002. 4、 王晓东 ，计算机算法设计与分析，（第一版），电子工业出版社， 2001. 5、 M. H. Alsuwaiyel， Algorithms Design Techniques and Analysis， 电子工业出版社影印 ，2003. 6、 Thomas H.Cormen， harles E.Leiserson， Ronald L. Rivest， Clifford Stein， Inroduction to Algorithms， 高等教育出版社影印 ， 2002.
