数据结构习题集和答案(2007-6-11)

内容发布更新时间 : 2024/12/23 12:42:00星期一 下面是文章的全部内容请认真阅读。

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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi