数据结构的考试题帮帮忙啊谢谢啦三、【应用题】（本大题共4小题，每题10分，共40分；请将答案填写在答题卷相应题号处）1．根据下面的字母/频率表构造一棵Huffman树,并给出各字母的Huffma

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

　　三、【应用题】（本大题共4小题，每题10分，共40分；请将答案填写在答题卷相应题号处）

　　1．根据下面的字母/频率表构造一棵Huffman树,并给出各字母的Huffman编码。

　　ABCDEFGH

　　251036456113

　　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．编写一个算法判断无向连通图中是否有回路。