数据结构复习题090612

[-1，0]，[1，2]，[1，3]，[-2，-1]，请分别按行序和列序列出各元素。

8．有一份电文中共使用5个字符：a，b，c，d，e，它们出现的频率依次为4，7，5，2，9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。

9．有如图所示的二叉树，回答如下问题。 a（1） 写出该树的中序遍历序列; （2） 写出该树的先序遍历序列; bc（3） 写出该树的后序遍历序列；

（4） 画出该二叉树的中序线索二叉树； def（5） 画出该二叉树的后序线索二叉树； （6） 画出该二叉树对应的森林； gh i 10．已知一棵树边的集合为{,,,,,,,,,,, ,}，画出这棵树。

11．假设二叉树采用顺序存储结构，如图所示。 （1） 画出二叉树表示；

（2） 写出先序遍历、中序遍历和后序遍历的结果； （3） 写出结点值c的双亲结点，其左、右孩子； （4） 画出把此二叉树还原成森林的图。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b

12．已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。 13．某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，给出其后序遍历序列。

14．将下图所示森林转换成为二叉树，并写出转化后二叉树中序遍历结果。

ABDCEFGHIJKLMPQRNO

15．有一份电文中共使用8个字符：a、b、c、d、e、f、o、i，它们的出现频率依次为10，20，15，32，40，60，26，18。试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。 16．已知某系统在通信联络中只可能出现A,B,C,D,E,F,G,H八种字符，其频率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计哈夫曼编码。

17．对有五个顶点{v1,v2,v3,v4,v5}的图的邻接矩阵如图所示，解答下列问题： （1）画出逻辑图。

（2）画出该逻辑结构的邻接表。

（3）基于邻接矩阵写出图的深度、广度优先遍历序列。

?010030?10? ??0???? ????60020??

???10?0? ??? ????500??

18．如图所示，解答如下问题：

（1）写出从定点A出发，深度和广度优先遍历方法遍历该图的顶点序列。

（2）根据普里姆算法和克鲁斯卡尔算法，分别求它的最小生成树，要求给出构造过程。

A56BE3G115F 24C3D

19．给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的邻接表的基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。

13425

图 一个无向图G

20．使用普里姆算法构造出如图所示的图G的一棵最小生成树。

1615552342364656

图 一个无向图G21．使用克鲁斯卡尔算法构造出如图所示的图G的一棵最小生成树。

16234725181225815107543620图 一个无向图G

22．设有一棵二叉树，它的中序和后序遍历结果如下，请画出该二叉树。 中序：1 4 3 5 6 2 后序：4 6 5 3 2 1

23．设一棵顺序二叉树具有10个结点，请计算其中叶子结点的数目。

24．设如图所示二叉树是由某棵树转化而来，请画出其对应的原树。

1234657

25．设有如图所示的一棵树，请将其转化为二叉树。

12144581012

36711913