19 23 28 30 8 11
14 16
3 5 7 9
（2）该树的带权路径长度为
（5+3+7+8）*4+（11+14）*3+（23+29）*2=271 ————3分
5、读程序写结果
已知二叉树的结点结构如下： struct Node {
int data;
Node *lchild,*rchild; };
某棵二叉树的形态如右图：
根据要求解答下题： 1、 (共5分) int fun1(Node *root) {
if(root==0) return 0; int l,r;
l=fun1(root->lchild); r=fun1(root->rchild); if(l>=r) return l+1; else return r+1; }
A B C D E
（1）当root是指向结点A的指针时，函数fun1的返回值是多少？(2分) 函数fun1的返回值是3。
（2）函数fun1的功能是什么？(3分) 函数fun1的功能是求二叉树的高度。 2、 (共6分) int fun2(Node *root) {
if(root==0) return 0; int l=fun2(root->lchild ); int r=fun2(root->rchild ); return l+r+1; }
（1）当root是指向结点A的指针时，函数fun1的返回值是多少？(2分) 函数fun1的返回值是5。
（2）函数fun1的功能是什么？(4分)
函数fun1的功能是求二叉树中所有结点的个数
第7章 图
1、填空题
1. 有n个顶点的有向连通图最多有 条边，最少有 条边。 2.具有n个顶点的完全无向图有________条边，完全有向图有________条边。
2、选择题
1. __________方法可以判断出一个有向图中是否有环（回路）。 (A)深度优先遍历 (B)拓扑排序
(C)求最短路径 (D)求关键路径 2.关键路径是指__________。
(A)从开始事件到终止事件路径长度最短的路径 (B)从开始事件到终止事件路径长度最长的路径 (C)从开始事件到终止事件活动最少的路径 (D)从开始事件到终止事件活动最多的路径
5. 方法 可以判断出一个有向图中是否有环（回路）。 (A)深度优先遍历 (B)拓扑排序 (C)求最短路径 (D)求关键路径
3、判断题
1.具有n个顶点的有向图最多有n*(n-1)条边。 （ ） 2.在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件。（ ）
4、应用题
1、已知某图的存储结构如下，试写出该图从顶点A开始的深度优先遍历序列。(11分)
A B C D E F G H I J K A 0 1 1 1 1 1 0 0 0 0 0 B 0 0 0 0 0 0 1 0 0 0 0 C 0 0 0 0 0 0 0 1 0 0 0 D 0 0 0 0 0 0 0 0 1 0 0
E 0 0 0 0 0 0 0 0 0 1 0 F 0 0 0 0 0 0 0 0 0 0 1 G 0 1 0 0 0 0 0 0 0 0 0 H 0 0 1 0 0 0 0 0 0 0 0 I 0 0 0 1 0 0 0 0 0 0 0 J 0 0 0 0 1 0 0 0 0 0 0 K 0 0 0 0 0 1 0 0 0 0 0
答案为：ABGCHDIEJFK (对一个1分)
2. 请给出图1的所有最小生成树。（10分）
共两棵。
第一棵为：(5分)错一条边扣1分。
a 1 c 3 2 b e d 5 f 6 c 8 图1
a 1 3 2 b e d 5 6 f 6
第二棵为：(5分)错一条边扣1分。
a 1 c 3 2
b e d 5 6 f 6
3. 请给出图2的所有拓扑排序序列。（16）
答案如下：仅有两个
第一个：abcdefgh (错一个字符扣1分) 第二个：abcdegfh (错一个字符扣1分)
4、对于有向无环图（如图2），写出它的所有不同的拓扑有序序列。(共16分)
g 图2 a c f b e h d