应用名词解释题答案.docx

应用名词解释题答案.docx答案
—、应用题
1、
2、
后序序列: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+l)/2 + J,因此，A[8][5]在数组B中位置为
8* (8+ 1)/2+ 5 = 41。
后序序列为ACDBGIHFE»
划分次序
划分结果
第一次
[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、(l)(k,p,h)
⑶(b)
(2)(a,b)
(4)b
9、
10、
11、
12、
字符
a
b
c
d
e
f
g
h
哈夫曼编码
0010
10
00000
0001
01
00001
11
Oil
顶点
1
2
3
4
5
6
入度
3
2
1
1
2
2
出度
0
2
2
3
1
3
(3)
6>O11OQ> ooolol oloooo oooloo oolool
(2)
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、
点
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}