发布时间 : 星期三 文章数据结构复习题090612更新完毕开始阅读5f34c8fa04a1b0717fd5ddd8
[-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