天津工程师范学院2008年《数据结构》考试大纲

　　一、考试组成

　　数据结构占100分。

　　二、数据结构部分的考试大纲

　　(一)参考书
　　严蔚敏．数据结构(C语言版)．北京：清华大学出版社

　　(二)复习内容及基本要求
　　1、绪论
　　(1)数据的逻辑结构与存储结构的概念。
　　(2)算法的定义、算法的基本特性以及算法分析的基本概念，包括了解几种常见的时间复杂度的含义。
　　2、线性表
　　(1)线性关系、线性表的定义，线性表的基本操作。
　　(2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。
　　(3)在以上两种存储结构的基础上对线性表实施的基本操作(包括链表的建立、插入和删除、检索、复制等操作)对应的算法设计(包括某些递归算法的设计)。
　　(4)一元多项式的表示与实现。
　　3、堆栈与队列
　　(1)堆栈与队列的基本概念、基本操作。
　　(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理。
　　(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作。
　　4、树与二叉树
　　(1)树与二叉树的基本概念，包括树形结构的基本特征、名词术语以及基本操作。
　　(2)二叉树的基本性质、二叉树的二叉链表存储结构、二叉树前序、中序、后序和按层次遍历方法以及利用遍历操作解决一些关于二叉树的其它操作。
　　(3)完成线索二叉树、最优二叉树、哈夫曼编码的实现与应用。
　　5、图
　　(1)图的基本概念，包括定义、分类、名词术语。
　　(2)邻接矩阵存储方法和邻接表存储方法的构造原理与特点。
　　(3)深度优先搜索和广度优先搜索。
　　(4)最小生成树及其特点、最短路径及其特点，掌握它们的求解过程及其算法思想。
　　6、查找
　　(1)静态表的概念和折半查找算法。
　　(2)散列表的基本概念，散列函数的基本设计技巧。
　　(3)二叉排序树的概念，以及二叉排序树上的查找、插入、删除算法。
　　(4)平衡二叉树的概念，以及平衡二叉树的插入和调整算法。
　　7、内排序
　　(1)排序的基本概念，基数排序的实现，各种排序方法比较。
　　(2)插入排序、选择排序、快速排序、堆积排序(包括大顶堆积的定义)等排序方法的算法思想和步骤，能够写出排序过程。