数据结构期末复习范围
第一章 算法与程序
1、 何谓算法？简述算法的基本特性和表示方法。
2、 如何评价一个算法？简述环路复杂度、空间复杂度和时间复杂
度的概念。
3、 简述算法与程序的联系与区别，并列举常用的算法设计方法。 第二章 常用数据结构
1、 数据类型与数据结构的联系与区别是什么？ 2、 数据类型的6个显著特征是什么？
3、 举例说明数据结构的逻辑结构、数据的存储结构和数据的运算
三个方面的内容。
4、 什么是线性结构？什么是非线性结构？举例说明。 第三章 简单数据结构
1、线性表可用顺序表和单链表作为存储结构。问： ? 两种存储表示各有哪些主要优缺点？
? 如果有n个表同时并存，且处理过程中各表的长度会动态发生变化，表的总数也可能自动改变；在此情况下应选用哪种存储表示？为什么？
? 若表的总数基本稳定，且很少插入和删除，但要求以最快速度存取表中元素；这是应采取哪种存储表示？为什么？ 2、设有一个栈，元素的进栈次序依次为A、B、C、D、E，问能否得到下面的出栈序列？若能请写出操作序列，若不能请说明原因？
? C、E、A、B、D ? C、B、A、D、E ? D、C、A、B、E ? A、C、B、E、D` ? A、B、C、D、E ? E、A、B、C、D
3、 已知表达式的中缀表示为(A+B)*D+E/(F+A*D)+C，利用栈把它
改写成为后缀表示，并写出转换过程中栈的变化。
4、 何为队列的上溢现像？解决方法有哪些？各种方法的工作原理
是什么？ 第四章 树与二叉树
1、已知一棵树边的集合为{(I,M),(I,N),(E,I),(B,E),(B,D),(A,B),(G,J), (G,K),(C,G),(C,F),(H,L),(C,H),(A,C)}，请画出这棵树并回答如下问题： ? 那个是根结点？ ? 那些是叶子结点？ ? 那个是结点G的双亲？ ? 那些是结点G的祖先？ ? 哪些是结点G的孩子？ ? 哪些是结点E的子孙？
? 哪些是结点E的兄弟？哪些是结点F的兄弟？ ? 结点B和结点N的层次号分别是多少？ ? 树的深度是多少？树的度是多少？
? 以结点C为根的子树的深度是多少?
2、分别画出有三个结点的树和有三个结点的二叉树的所有不同形态。 3、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，问该树中有多少叶子结点？ 4、一棵深度为h的满k叉树是这样的一棵树，他的第h层上的结点全部是叶子结点，其余各层上的每个结点都有k可非空子树。如果对深度为h的满k叉树按层次自上而下，同层次自左至右的顺序从1开始对所有结点编号，问： ? 各层的结点数目是多少？
? 编号为n的结点的双亲结点若存在，其编号是多少？ ? 编号为n的结点的第i个孩子结点若存在，其编号是多少？ ? 编号为n的结点有右兄弟的条件是什么？其右兄弟编号是多少？
4、 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度
各为多少？
5、 对于下图所示的一棵二叉树，分别写出： ? 前序遍历序列 ? 中序遍历序列 ? 后序遍历序列 ? 层次遍历序列
A B C D E F G H I
6、 已知一棵二叉树的前序序列为EBADCFHGIKJ，中序序列为
ABCDEFGHIJK。请画出该二叉树，并写出它的后序序列和层次序列。
7、 已知一棵二叉树的后序序列为DCEGBFHGIKJ，中序序列为
DCBGEAHFIJK。请画出该二叉树，并写出它的前序序列和层次序列。
8、 已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为
DBGEHJACIF。请画出该二叉树，并写出它的前序序列和后序序列。
9、 把下图所示的两棵树，分别转化为相应的二叉树。 P126
10、 把下图所示的森林转化为相应的一棵二叉树。 P127
11、 把下图所示二叉树转化为相应的树，然后分别写出其先根序列
和后根序列。
P127
12、 给定一个权重集合为W={3,15,17,14,6,16,9,2}，请画出相应的哈
夫曼树，并计算其带权路径长度WPL。
13、 已知二叉树以二叉链表作为存储结构，编写按层次遍历该二叉
树的算法。
14、 已知二叉树以二叉链表作为存储结构，编写按前序遍历该二叉
树的算法。 第五章 图与网
1、 对如下有向图给出其邻接矩阵、邻接表和逆邻接表，并计算每
个顶点的度。 P159 图 5-34（a）
2、 对如下有向图给出其邻接矩阵、邻接表和逆邻接表，并计算每
个顶点的度。 P159 图 5-34 （b） 3、 对下图分别给出：
⑴ 深度优先搜素遍历序列和深度优先生成树； ⑵ 广度优先搜素遍历序列和广度优先生成树； ⑶ 用Prim算法求得最小生成树的过程； ⑷ 用Kruskal算法求得最小生成树的过程。 P159 图 5-35
4、 对下图分别给出： ⑴ 邻接矩阵；