应用名词解释题答案.doc

答案
一、应用题
后序序列:C, B, F, E, I, J, H, G, D, A
34 56 58 63 94
2 1 3 4 4

元素值
比较次数
3、根据题意,矩阵A中当元素下标I与J满足I≥J时,任意元素A[I][J]在一维数组B中的存放位置为I * (I + 1) / 2 + J,因此,A[8][5]在数组B中位置为
8 * (8 + 1) / 2 + 5 = 41。
4、构造出的二叉树如下:E

C
D
A
B
G
I
H
F
 
 
 
 
 
 
 
 
 
 
 
后序序列为ACDBGIHFE。
5、
划分次序
划分结果
第一次
[38 24 40] 46 [56 80 95 79]
第二次
24 [38 40] 46 [56 80 95 79]
第三次
24 38 40 46 [56 80 95 79]
第四次
24 38 40 46 56 [80 95 79]
第五次
24 38 40 46 56 79 [80 95]
第六次
24 38 40 46 56 79 80 95
 
6、此二叉树的后序遍历结果是:EDCBIHJGFA
7、
图
深度优先序列
广度优先序列
邻接矩阵表示时
0,1,2,8,3,4,5,6,7,9
0,1,4,2,7,3,8,6,5,9
8、(1)(k,p,h) (2)(a,b)
(3)(b) (4)b
9、
10、
11、
12、
字符
a
b
c
d
e
f
g
h
哈夫曼编码
0010
10
00000
0001
01
00001
11
011
13、(1)
顶点
1
2
3
4
5
6
入度
3
2
1
1
2
2
出度
0
2
2
3
1
3
(2) (3)
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
1 1 0 0 1 0
14、
15、深度优先生成树广度优先生成树
16、
17、3趟。
第一次:{55,10,15,36,66,36,50,45}
第二次:{15,10,50,36,55,36,66,45}
第三次:{10,15,36,36,45,50,55,66}
18、第一趟:{20,30,38,42,45,25,56,65}
第二趟:{20,30,38,42,25,45,56,65}
第三趟:{20,30,38,25,42,45,56,65}
19、对有向图进行拓扑排序,如果图中所有顶点都在其拓扑有序序中,则不存在有向环。
该图中不存在有向环。拓扑序列为
(1,2,3,4,5,7,9,10,11,6,12,8)或
(9,10,11,6,1,12,4,2,3,5,7,8)
20、
终点
Dist
b
c
d
e
f
g
S
(终点集)
K=1
15
(a,b)
2
(a,c)
12
(a,d)
{a,c}
K=2
15
(a,b)
12
(a,d)
10
(a,c,e)
6
(a,c,f)
{a,c,f}
K