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