3、设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。
4、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二
第 页 11 共 23 页
叉树。
5、设无向网络图G的邻接矩阵的上三角部分如下表，请回答： （1） （2）
画出该网络图；
求该网络图的最小生成树(只要给出生成树即可)；
（3） 给出从顶点V5出发深度优先搜索遍历该图的顶点序列（顶点标号小者优先）。 V1 V2 V3 V4 V5 V6 V7 V1 ∞ 18 ∞ ∞ 23 4 6 V2 ∞ 5 8 12 ∞ ∞ V3 ∞ 10 ∞ ∞ ∞ G: V4 ∞ ∞ 15 ∞ V5 ∞ 25 ∞ V6 ∞ 7 V7 ∞
6、假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, 组成, 各字母在电文中出现的频率
分别为5, 25, 3, 6, 10, 11,。试为这6个字母设计不等长Huffman编码, 并给出该电文的总码数。
第 页 12 共 23 页
7、给定权值集合{15, 03, 14,20，02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权外
部路径长度。
8、设有数据逻辑结构为：
第 页 13 共 23 页
B = (K, R), K = {k1, k2, ?, k9}
R={
（2）相对于关系R, 指出所有的开始结点和终端结点。 （3）分别对关系R中的开始结点，举出一个拓扑序列的例子。 （4）分别画出该逻辑结构的正向邻接表和逆向邻接表。
9、已知序列{503，61， 512，87，122，908，170，897，275}，请给出采用快速排序法对该序列作
升序排列时每一趟的结果。（5分）
第 页 14 共 23 页
10．已知一个无向图如下图所示，要求用普鲁姆算法算法生成最小树
V0 5 1 5 5 V3 V1 V2 6 4 3 2 6 V4 V5 6
11、请写出如下无向连通图的最小生成树，写出prim算法执行过程示意图。
V2 6 5 V1 1 V3 5 5 V4
6 4 2 3 6 V5 V6
12、对如下图所示的二叉树进行遍历，分别画出先序、中序、后序线索二叉树的逻辑表示图。
第 页 15 共 23 页