Question

数据结构的考试题帮帮忙啊谢谢啦

三、【应用题】（本大题共4小题，每题10分，共40分；请将答案填写在答题卷相应题号处）
1．根据下面的字母/频率表构造一棵Huffman树, 并给出各字母的Huffman编码。
A B C D E F G H
25 10 36 4 5 6 11 3
2．已知哈希表地址空间为0…10，哈希函数为H(k)=k%11，采用线性探查法处理冲突。将关键字{8，12，18，25，40，16，7，17，100}依次存入该散列表中，给出最后的结果散列表，并求出在等概率下的平均查找长度。搜索成功的平均搜索长度ASLsucc 是指搜索到表中已有表项的平均探查次数,它是找到表中各个已有表项的探查次数的平均值。
3．对下列数据表，写出采用Shell排序的每一趟的结果，增量序列为{7，3，1}。
{9, 8, 7, 6, 5, 4, 3, 2, 1}
4．设有一个关键码的输入序列{ 55， 88， 100， 120， 90， 150， 40， 20，95}，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。
5．一颗二叉树的中序序列和后序序列分别是DCBAEFG和DCBGFEA, 请画出该二叉树并给出先序序列。
6．设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树，并求出在等概率下的平均查找长度。搜索成功的平均搜索长度是指搜索到树中已有数据的平均探查次数。
7．一个带权无向图如下所示,画出该图的一棵最小支撑树，该图最小支撑树是否唯一，为什么？

8．若用二叉链表作为二叉树的存储表示，试编写算法统计二叉树中叶结点的个数。
9．设有一个含n个元素的数组，数组元素为自然数,写出一个算法，将所有值为素数的元素排在所有值为奇数的元素之前，将所有值为奇数的元素排在所有值为偶数的元素之前，要求该算法的时间复杂度为O(n)。
10．若用二叉链表作为二叉树的存储表示，试编写算法交换二叉树中各结点的左右子树。
11．若一个带权有向图如下图所示,请给出从顶点A到该图其他顶点的最短路径及最短路径长度。

12．编写一个算法判断无向连通图中是否有回路。

Answer 1

A:10     B:001   C:11   D:0001  E:0110   F:0111   G:010   H:0000 

第二题：|  | 12 | 100 |  25 |     | 16 |  17  |  18   |  8  | 40 |  7

               0    1     2       3     4    5      6       7      8     9    10

Answer 2

raph G, Vnode V)
{
int count= 0;
ArcNode *p;
p=V->firstarc;
while(p)
return count;
}

其实这个是最简单的，在用邻接表表示的有向图中第i 个链表中的结点个数只是顶点vi的出度，求顶点入度的难度稍微要复杂些，必须遍历整个邻接表。