青岛科技大学2007年硕士招生《433数据结构》考试大纲

　　一、 本《数据结构》考试大纲适用于报考青岛科技大学计算机应用技术和计算机软件与理论专业的硕士研究生入学考试。

　　二、考试内容：

　　第一章 绪论

　　1、基本概念和术语

　　数据、数据元素、数据项、数据结构、数据的四种逻辑结构

　　2、算法和算法分析

　　算法的重要特性、算法的要求、算法效率的度量

　　第二章 线性表

　　1、线性表的类型定义

　　2、线性表的顺序表示和实现

　　顺序表的插入算法、删除算法、查找算法

　　3、线性表的链式表示和实现

　　单链表的查找算法、单链表的插入算法、单链表的删除算法、循环链表、双向链表

　　4、一元多项式的表示和相加

　　一元多项式的表示、建立一元多项式的算法、两个多项式相加的算法

　　第三章 栈和队列

　　1、栈

　　栈的定义、栈的表示和实现

　　2、栈的应用举例

　　数制转换、括号匹配的检验、行编辑程序、迷宫求解、表达式求值

　　3、栈与递归的实现

　　4、队列

　　队列的定义、队列的表示和实现、循环队列

　　第四章 串

　　1、串的定义

　　2、串的表示和实现

　　定长顺序存储表示、堆分配存储表示、串的块链存储表示

　　3、串的模式匹配算法

　　第五章 数组和广义表

　　1、数组的定义

　　2、数组的顺序表示和实现

　　3、矩阵的压缩存储

　　特殊矩阵、稀疏矩阵

　　4、广义表的定义

　　5、广义表的存储结构

　　6、m元多项式的表示

　　7广义表的递归算法

　　求广义表的深度、复制广义表、建立广义表的存储结构

　　第六章 树和二叉树

　　1、树的定义和基本术语

　　2、二叉树

　　二叉树的定义、二叉树的性质、二叉树的存储结构

　　3、遍历二叉树和线索二叉树

　　遍历二叉树、线索二叉树、

　　4、树和森林

　　树的存储结构、森林与二叉树的转换、树和森林的遍历

　　5、赫夫曼树及其应用

　　最优二叉树、赫夫曼编码

　　6、树的计数

　　第七章 图

　　1、图的定义和术语

　　2、图的存储结构

　　数组表示法、邻接表、十字链表、邻接多重表

　　3、图的遍历

　　深度优先搜索、广度优先搜索

　　4、图的连通性问题

　　无向图的连通分量和生成树、有向图的强连通分量、最小生成树、关节点和重连通分量

　　5、有向无环图及其应用

　　拓扑排序、关键路径

　　6、最短路径

　　第九章 查找

　　1、静态查找表

　　有序表的查找、静态树表的查找、索引顺序表的查找

　　2、动态查找表

　　二叉排序树和平衡二叉树、B-树和B+树

　　3、键树

　　4、哈希表

　　哈希表的含义、哈希表的构造方法、处理冲突的方法、哈希表的查找

　　第十章 内部排序

　　1、插入排序

　　2、快速排序

　　3、选择排序

　　4、归并排序

　　5、各种内部排序方法的比较

　　三、考试要求：

　　1、线性表

　　理解线性表的抽象数据类型，掌握顺序表的插入算法、删除算法、查找算法，单链表的查找算法、单链表的插入算法、单链表的删除算法，会自己设计算法解决实际问题。

　　2、栈和队列

　　理解栈和队列的定义，掌握栈的应用举例的算法，理解栈与递归的实现算法。

　　3、串

　　理解串的定义、串的表示和实现、串的模式匹配算法

　　4、数组和广义表

　　理解数组的定义、数组的顺序表示和实现、广义表的定义、广义表的存储结构、m元多项式的表示，弄懂广义表的递归算法，掌握稀疏矩阵的压缩存储。

　　5、树和二叉树

　　掌握二叉树的定义、二叉树的性质以及证明方法；理解遍历二叉树和线索二叉树；掌握森林与二叉树的转换方法；会画最优二叉树，会设计赫夫曼编码；掌握树的计数。

　　6、图

　　理解图的定义和术语；给你一个图能画出对应的存储结构；掌握深度优先搜索和广度优先搜索遍历的算法；掌握无向图的连通分量和生成树；掌握拓扑排序算法和关键路径算法，理解本章中的其他算法。

　　7、查找

　　掌握顺序查找、折半查找算法；掌握二叉排序树、平衡二叉树算法；理解哈希表的概念、构造方法，掌握哈希表处理冲突的方法；理解本章内其他算法。

　　8、内部排序

　　掌握直接插入算法、希尔排序算法、快速排序算法、简单选择排序算法、堆排序算法、归并排序算法；理解其他算法。

　　四、主要参考书：

　　严蔚民、吴伟民，数据结构（C语言版），北京：清华大学出版社，1997

　　五、主要题型：

　　主要可能的题型有：选择题、填空题、简答题、算法设计题