5、已知二叉树T的数据域均为正数，写一个算法求数据域的最大值。Int maxdata(Bitree T) 6、已知非空二叉树T的数据域均为字符型数据，数据域的值是?A?只有一个结点，写一个算法求这个结点的双亲。
Char Parent(Bitree T)；
7、已知非空二叉树T，写一个算法求两度点的个数。
8、用递归方法写一个算法求二叉树的叶子数int Leafnum( BiTree T),先写出基本项和归纳项，然后写算法
9、写一个算法求二叉树的深度 int Depth( BiTree T)
10、写一个算法交换二叉树所有结点的左右子树 Status Changchild( BiTree T)
11、试分别画出具有3个结点的有序树和3个结点的二叉树的所有不同形态。
12、已知一棵度为m的树中，有n1个度为1的结点，n2个度为2的结点，……nm个度为m的结点，问该树中有多少片叶子？
13、一棵有11个结点的二叉树的静态链表存储结构如下表。 Lift[i]
6 7 8 5 2 Data[i]
m f a k b l c r d Right[i]
9 10 4 11 1
画出该二叉树，将此二叉树转化为树或森林。
s e 14、已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。
15、对于n个结点的完全二叉树，用1~n的连续整数顺序编号，试回答下列问题：
（1） 它共有多少层？各层的结点数分别是多少？
（2） 各层最左边的结点的编号分别是多少？各层最右边的结点的编号分别是多少？
（3） 对于编号为i(1?i?n)的结点，它的层是多少？它的双亲（若存在）的编号是多少？它的左孩（若存在）和右孩（若存在）的编号分别是多少？
16、下图所示的森林：
(1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树；
ABD(a)CEFIGHJ(b)K
17、对于如下所示的图，试写出其先序、中序和后序以及按层遍历的结果，并画出其顺序存储结构和二叉链表存储结构。
16
124758369 18、试画出上题所示的二叉树的先序线索二叉树和后序线索二叉树。
19、分别画出下图所示各棵树所对应的二叉树，然后将这些二叉树连接成一棵树。
ABCEDFGIHJK
20、欲传输一段电文如下：CATE AT DATA CAE CATS AEA AE
请你设计出这段电文中的每个字符的哈夫曼二进制编码。并计算整段电文的编码长度． 21、给定叶子结点的权值集合{15，3，14，2，6，9，16，17}，构造相应的哈夫曼树，并计算它的带权路径长度。
17
第七章 图
班级： 学号： 姓名：
一、选择题
1、一个具有n个顶点的无向连通图最多有（ ）边，最少有（ ）边。
A)n2； B)n(n-1)； C)n(n-1)/2； D)n； E)n-1； F)n+1。 2、一个具有n个顶点的有向强连通图最多有（ ）边，最少有（ ）边。
A)n2； B)n(n-1) ； C)n(n-1)/2； D)n； E)n-1； F)n+1。
３、图1给出一个无向图。从顶点1出发，DFS遍历的输出序列是（ ），BFS遍历的输出序列是（ ）。
A)1354267； B)1347625； C)1534276； D)1247653。
4、已知有8个顶点A、B、C、D、E、F、G、H的无向图，其邻接矩阵存储结构如下表。从A点开始， DFS遍历的输出序列是（ ）。
A)ABCDGHFE； B)ABCDGFHE； C)ABGHFECD； D)ABFHEGDC。
A B C D E F G H A 0 1 0 1 0 0 0 0 B 1 0 1 0 1 1 1 0 C 0 1 0 1 0 0 0 0 D 1 0 1 0 0 0 1 0 E 0 1 0 0 0 0 0 1 F 0 1 0 0 0 0 1 1 G 0 1 0 1 0 1 0 1 H 0 0 0 0 1 1 1 0 5、以下哪个算法可以判断出一个有向图中是否有回路（ ）。
A)广度优先遍历； B)拓扑排序； C)求最短路径； D)求关键路径。
6、已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是（ 1 ），BFS遍历的输出序列是（ 2 ）。
（1）A)12354； B)12345； C)13452； D)14352。 （2）A)12345； B)13245； C)12354； D)14352。
18
二、填空题
1、在一个图中,所有顶点的度数之和等于所有边数的（ ）倍。
2、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 3、具有4个顶点的无向完全图有（ ）条边。
4、具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 5、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（ ）。 6、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（ ），．．．所有邻接表中的结点总数是（ ）。
7、图的深度优先遍历算法类似于二叉树的（ ）遍历；图的宽度优先遍历算法类似于二叉树的（ ）遍历
8、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（ ）度优先遍历算法。
9、在一个无向图的邻接表中，若表结点的个数是m， 则图中边的条数是( )条。 10、具有n条边的图，求最小生成树的Prim算法时间复杂度是（ ）。它适用 （ ）图。
11、具有n条边的图，求最小生成树的Kuruscal算法时间复杂度是（ ）。它适用 （ ）图。
12、具有n个顶点和ｍ条边的图，采用邻接表存储结构。则深度优先搜索算法DFS、广度优先搜索算法BFS、求拓扑排序、求关键路径的时间复杂度是都是（ ）。 13、求n个顶点的有向图某顶点到其他各顶点的最短路径的Dijkstra算法时间复杂度是（ ）。14、n个顶点的有向图每对顶点间最短路径的Floyd算法时间复杂度是____________ 。 15、如果含n个顶点的无向图成一个环，则该图有多少棵生成树。____________ 。 16、G是一个非连通的无向图，共有28条边，则该图至少有多少顶点。__________ 。 17、一个含n个顶点的无向连通图的每条边的权重都是a(a>0),则它的最小生成树的权重等于（ ）。 18、已知有向图的邻接6?6型矩阵为A，试问该矩阵的第3行的非零元素之和表示（ ），第3列的非零元素之和表示（ ）。
三、问答题与算法题
１、在下图所示的各无向图中：
(１)哪些图是连通图?对非连通图给出其连通分量。 (２)哪些图是森林?
２、在下图所示的有向图中：
(1) 请给出每个顶点的度，入度和出度。
(2) 请给出其邻接矩阵、邻接表及逆邻接表。
19
1 ３、已知下图所示的有向图，求：
（1）邻接表；
5 （2）逆邻接表； 2
４、已知如下图所示的无向图，求：
1 （1）邻接矩阵； （2）邻接表； 4
5、对下图所示的连通图，请分别用Prim算法构造其最小生成树。
3 4 2 3 5
6、用Kruskal算法求下图的最小生成树(写出步骤)。
12
① ② 8 5 15 20 ③ 6 ④ 10 ⑤ 4 8 9 ⑥
7、已知AOE网如图5：顶点表示活动，弧及权重表示活动持续的时间（单位为天）。找出所有关键路径；求出活动V3的最早开始时间。
20