数据结构应用题练习.doc

1、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。
21、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：
请指出结点P的父结点，左子女，右子女。
3、给出下列二叉树的先序序列。

4、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。
答案：二叉树形态

（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C
①画出这棵二叉树。
②画出这棵二叉树的后序线索树。

③将这棵二叉树转换成对应的树（或森林）。

A

BM

F

D

(3)

C

EM

H

G

(1) (2)

1、已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H, A,C,K,I,L,F。
i. 写出该二叉树的后序序列；
ii. 画出该二叉树；
iii. 求该二叉树的高度(假定空树的高度为－1)和度为2、度为1、及度为0的结点个数。
该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。
该二叉树的形式如图所示：
A
B
J
K
I
F
C
G
E
D
L
H

该二叉树高度为：5。
度为2的结点的个数为：3。
度为1的结点的个数为：5。
度为0的结点个数为：4。

5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。
答案：

WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69
6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。
答案：(1)树形态：

(2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79

（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
① 试为这8个字母设计赫夫曼编码。
② 试设计另一种由二进制表示的等长编码方案。
③ 对于上述实例，比较两种方案的优缺点。
解：方案1；哈夫曼编码
先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32

0 1
0 1 0 1
19 21 32
0 1
0 1 0 1
7 10 6
0 1
2 3

（100）
（40） （60）
19 21 32 （28）
（17） （11）
7 10 6 （5）
2 3

方案比较：
字母编号
对应编码
出现频率
1
1100
0.07
2
00
0.19
3
11110
0.02
4
1110
0.06
5
10
0.32
6
11111
0.03
7
01
0.21
8
1101
0.10

字母编号
对应编码
出现频率
1
000
0.07
2
001
0.19
3
010
0.02
4
011
0.06
5
100
0.32
6
101
0.03
7
110
0.21
8
111
0.10

方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61
方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3
结论：哈夫曼编码优于等长二进制编码

2．应用题
（1）已知如图6.27所示的有向图，请给出：
① 每个顶点的入度和出度；
② 邻接矩阵；
③ 邻接表；
④ 逆邻接表。
图6.27 有向图

2 AOE网G如下所示，求关键路径。（要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径）

答案：(1)最早发生时间和最迟发生时间： (2)关键路径：

（2）已知如图6.28所示的无向网，请给出：
① 邻接矩阵；
② 邻接表；
③ 最小生成树
图6.28 无向网

a
→
b
4
→
c
3

b
→
a
4
→
c
5
→
d
5
→
e
9
^

c
→
a
3
→
b
5
→
d
5
→
h
5
^

d
→
b
5
→
c
5
→
e
7
→
f
6
→
g
5
→
h
4^
e
→
b
9
→
d
7
→
f
3
^

f
→
d
6
→
e
3
→
g
2
^

g
→
d
5
→
f
2
→
h
6
^

h
→
c
5
→
d
4
→
g
6
^

（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

图6.29 邻接矩阵

（2）根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程。（用图或者表的方式均可）。

答案：(1)广度优先遍历序列：1; 2, 3, 4; 5; 6
(2)最小生成树（prim算法）

V1
V5
V4
V6
V761
V2
V8
V56
1. 对下面的有向图，从顶点V1开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。

遍历得到的DFS生成森林和BFS生成森林如下图：
V1
V5
V4
V6
V761
V2
V8
V56
DFS生成森林

V1
V5
V4
V6
V761
V2
V8
V56
BFS生成森林

（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：
① 画出哈希表的示意图；
② 若查找关键字63，需要依次与哪些关键字进行比较？
③ 若查找关键字60，需要依次与哪些关键字比较
④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

①画表如下：
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
32
17
63
49

24
40
10

30
31
46
47
②查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;
然后顺移，与46,47,32,17,63相比，一共比较了6次！
③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
④对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，
所以ASL=1/11（6＋2＋3×3+6）＝23/11

设散列表的长度为m=13，散列函数为H(k)=k MOD m，给定的关键码序列为19，14，23，1，68，20，84，27，55，11，13，7，试写出用线性探查法解决冲突时所构造的散列表。
答案：表形态：

（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。

12
7 17
2 11 16 21
4 9 13

验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21

（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
③ 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

解：

⑦ 堆排序
第一步,形成初始大根堆（详细过程略），第二步做堆排序。
12
2
16
20
10
30
16*
28
6
18
30
28
16
10
20
16*
18
2
12
6

初始排序 不是大根堆 形成初始大根堆12
28
16
2
10
20
16*
18
6
30
28
20
16
10
12
16*
18
2
30
6

交换1与10对象 从1到9重新形成堆
6
20
16
2
10
12
16*
18
28
30
20
18
16
10
12
16*
6
2
30
28

交换1与9对象 从1到8重新形成堆
2
18
16
20
10
12
16*
6
28
30
18
12
16
10
2
16*
12
20
30
28

交换1与8对象 从1到7重新形成堆
16*
12
16
20
10
2
18
6
28
30
16*
12
16
10
2
18
6
20
30
28

交换1与7对象 从1到6重新形成堆
10
12
16
20
16*
2
18
6
28
30

16
12
10
16*
2
18
6
20
30
28

交换1与6对象 从1到5重新形成堆
6
12
10
20
16*
2
18
16
28
30
12
6
10
16*
2
18
16
20
30
28

交换1与5对象 从1到4重新形成堆
12
6
10
20
16*
12
18
16
28
30
10
6
2
16*
12
18
16

20
30
28

交换1与4对象 从1到3重新形成堆
2
6
10
20
16*
12
18
16
28
30
6
2
10
16*
12
18
16
20
30
28

交换1与3对象 从1到2重新形成堆

2
6
10
20
16*
12
18
16
28
30
2
6
10
16*
12
18
16
20
30
28

交换1与2对象 得到结果

90、请画出下图中的极大连通子图。
1
4
5
6
3
2

91、对于如下图请画出其用prim和kruskal两种不同算法生成最小生成树的各条边的并入顺序。画出最小生成树。并写出广度优先和深度优先的结点遍历顺序。
20
1
4
3
2
5
6
12
12
3
3
10
6
5
7
8
4

92、什么是静态查找，什么时动态查找，什么叫平均查找长度。
93、用序列（46，88，45，39，70，58，101，10，66，34）建立一个二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。
94、已知一个线性表（38，25，74，63，52，48），假定采用h(k)=k%7计算散列地址进行散列存储，若引用线性探测的开放地址法解决冲突，则在该散列表上进行检索的平均检索长度为多少，若利用连地址法处理冲突，则在该散列表上进行检索的平均查找长度为多少？设地址空间为9。请画出算列表。
96、已知长度为12的表：（Jan , Fed , Mar , Apr , May , Jun , Aug , Sep , Oct , Nov , Dec）按表中元素的顺序，依次插入一棵初始为空的二叉排序树，画出插完之后的二叉排序树，并求其在等概率情况下，查找成功的平均查找长度。
98、有散列函数为h(k)=k%11,如果用二次探测在散列的方式解决冲突，49应放入哪？
15
38
61
84

0 1 2 3 4 5 6 7 8 9 10 11 12 13

99、用增量序列{8、4、2、1}对下列关键字进行希尔排序，用图表示排序过程。
{56、37、59、41、98、47、94、50、63、52、42、54、60、72、86、90}
100、有一组关键字{14，15，30，28，5，10}，分别画出冒泡排序、快速排序过程的图示。