单项选择(1998年中国科学技术大学)

在叶子数目和权值相同的所有二叉树中,最优二叉树一定是完全二叉树,该说法【 】。

A、正确

B、错误

答案解析

B

讨论

啥夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。

什么是啥夫曼(Huffman)树?

在有 6 个字符组成的字符集 S 中,各个字符出现的频次分别为 3、4、5、6、8、10,为 S 构造的哈夫曼树的加权平均长度为【 】

具有n个叶子的二叉树,每个叶子的权值为wi(1≤i≤n),其中带权路径长度最小的二叉树称为__________。

最优二叉树(或哈夫曼树)是指权值为w1,w2,…,wn的n个叶结点的二叉树中带权路径长度最小的二叉树。【 】是哈夫曼树(叶结点中的数字为其权值)。

如果一棵huffman树T有n0个叶子结点,那么,树T有多少个结点?要求给出求解过程。

求具有最小带权路径长度的二叉树的算法称为__________算法。对于给出的一组权W={10,12,16,21,30},通过该算法示出的二叉树的带权路径长度为__________。

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){     int i,j;     for (j=__________;j>=1;j--){         a[k]=j;          if (__________){             printf ( "%d = %d" , a[0],a[l]);             for (i = 2 ; i < = k ; i + + )                 printf ( " + % d " , a[i]);             printf ( "  n " );         }else test(__________,k + l );     } }

如果只考虑有序树的情形,那么具有7个结点的不同形态的树共有【】

对于前序遍历和中序遍历结果相同的二叉树为__________;对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树