数据结构课堂习题.pdfVIP

臣心一片磁针石，不指南方不肯休。——文天祥

数据结构课堂习题

1.已知一棵二叉树的先序遍历序列为V1,V2,V4,V5,V6,V7,V3,V8，中

序遍历序列为V4,V2,V6,V5,V7,V1,V8,V3。（已知中序和后序）

(1)画出这棵二叉树;

(2)写出该二叉树的后序遍历序列;

(3)画出这棵二叉树的中序线索二叉树的存储结构图。

2.假设用于通信的电文仅由8种字母ABCDEFGH组成，每个字母出

现的概率分别为0.05,0.25,0.03,0.06,0.1,0.11,0.36,0.04。

(1)用8个概率值为权值设计Huffman(哈夫曼)树。

(2)计算它的带权路径长度WPL。

(3)设计这8种字符的Huffman编码

3.请利用Prime（普里姆）算法计算下图的最小生成树（10分）

3

12

3

4

45

745

3456

88

56

5

78

4.已知一个无向图G=(V,E),V={v1,v2,v3,v4,v5,v6,v7,v8},E=

{(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7),(v4,v8),(v

5,v8),(v6,v7)};(1)画出该无向图；(2)画出该图的邻接表存储结构；

(3)根据存储结构，写出深度优先有哪些信誉好的足球投注网站遍历序列和广度优先有哪些信誉好的足球投注网站遍历

序列。

臣心一片磁针石，不指南方不肯休。——文天祥

5.

利用下图表示一个工程，V1为源点、V6为汇点，边表示活动，顶

点表示事件，请计算下图从的关键路径

a4=3

V2V5

a1=3a3=2a8=1

a7=2

V1V4

V6

a5=4

a2=2

a6=3

V3

6.使用迪杰斯特拉算法计算从顶点V1出发到其余各点的最短路径.

4

V2