数据结构测验12.docx

数据结构测验二
一、单项选择题：
•任何一棵二叉树T,如果其终端结点数为n，度为2的结点数为n，则 o2
（ ）。
=n+1
o 2
2 .设X是一棵树,
n =n +1 C. n =2n +1 D. n =2n +1
2 优先遍历的算法
答题纸
学号: 姓名:
一、单项选择题：=24
题号
1
2
3
4
5
6
7
8
答题
A
B
B
A
C
B
D
D
题号
9
10
11
12
13
14
15
16
答题
D
B
B
C
B
A
A
D
二、判断题（认为正确在答题处写T,不正确写）1x10=10
题号
1
2
3
4
5
6
7
8
9
10
答题
x
T
x
T
T
T
x
T
x
T
三、简答题：
1．已知权值：4, 2, 3, 7, 6, 18, 27 请画出相应的哈夫曼树并计算其带
权路径长度WPL （要求左孩子的权小于同一双亲右孩子的权）。（6）
WPL=27*1+18*2+(4+6+7)*4+(2+3)*5=27+36+68+25=156
2．一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出，试
先序：
中序：
后序：
DBKFIAHEJCG
DKIFBHJEGCA
求出空格处的内容，
ABDFKICEHJG
3．
s 1 3 4
1 s 5 2
5 s 6
2 6s
假定无向图G有7个结点和7条边，并依次输入这7条边为（A, B）,
（A, D），（A，E），（G，C），（B, E），（C，F），（D，E）。试从顶点 A 出发,
分别写出按深度优先搜索和广度优先搜索进行遍历的生成树。 （6）
，并依次输入这7条边为（A, B）,
(A, D),(A，E), (G, C), (B, D), (C, F), (D, G)。试从顶点 A 出发,
分别写出按深度优先搜索和广度优先搜索进行遍历的生成树。
5}, E=〈〈0, 1〉},〈0, 2〉〈1,
4〉〈2, 5〉,〈5, 4〉,〈4, 3〉,〈5, 3〉｝。写出图G中顶点的所有拓扑排 序。 (6)
0 1 2 5 4 3
0 2 1 5 4 3
0 2 5 1 4 3 ，画出用Prim算法得的最小生成树。（从
顶点 0 开始，写出计算过程）（10）
(
8 1 2 2 2
1 OO 3 oo oo
2 3 00 5 o
2 o 5 o 3
2 OO O 3 o /
1
2
3
4
U
v-u
k
adjvex
0
0
0
0
{0}
{1,2,3,4}
1
lowcost
1
2
2
2
adjvex
0
0
0
{0,1}
{2,3,4}
2
lowcost
0
2
2
2
adjvex
0
0
{0,1,2}
{3,4}
3
lowcost
0
0
2
2
adjvex
0
{0,1,2,3}
{4}
4
lowcost
0
0
0
2
adjvex lowcost
0
0
0
0
{0,1,2,3,4}
{ }
最短工期是 97 最早开工时间是
v1
v2
v4
v6
v5
v3
v7
v8
0
6
1
50
51
89
75
97
四、算法设计题目：（10*2）
，并写出判断二叉树中结点p是否是结点q的祖 先的算法。
// 二叉树的二叉链表存储表示
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
方法一：
BiTree find(BiTree T，TElemType p)
{ if(T|| T->data==p) return T;
s= find(T->lchild,p);
if(s)
return s;
else return find(T->lchild,p);
}
}
int panduan(BiTree T, TElemType p, TElemType q)
{ if(T)
{ s=find(T,p);
if( s)
{ t=find(s,q);