【1】f30(A5)的返回值为2,因为A5表示只考虑A数组的前5个元素[25,34,256,9,38],m=f30(A, 4)则表示只考虑前4个元素[25,34,256,9],其中m=2是256所在的下标,因此返回值为2。
【2 】f30(A,9)的返回值为7,因为m=f30(A,8)则表示只考虑前8个元素[25,34,256,9,38,47,128,256],其中m=2是256所在的下标,而A[m]>A[8-1],因此返回值为2。注意这里的n是9,而非8。
【3】算法f30的功能为在数组A中找到一个下标i,使得A[i]是A中最大的元素。具体实现是通过递归方式实现的,首先判断n是否小于等于0,如果是则返回-1表示没有找到;然后判断n是否等于1,如果是则返回0表示A中只有一个元素;否则递归调用f30(A,n-1)找到前n-1个元素中的最大值所在的下标m,然后比较A[m]和A[n-1]的大小,如果A[m]大于A[n-1],则返回m;否则返回n-1。整个算法的思路是将问题不断分解为规模更小的子问题,直到问题的规模足够小,可以直接求解,然后将子问题的解合并起来得到原问题的解。
(1)4,
(2)8,
(3)该函数的输入参数包括一个整型数组A和数组长度n。
若n小于等于0,则返回-1。
若n等于1,则返回0。
若n大于1,则递归调用f30函数,传入A数组和n-1,得到返回值m。
若A[m]大于A[n-1],则返回m。
否则返回n-1。
A.该树一定是一棵完全二叉树
B.树中一定没有度为1的结点
C.树中两个权值最小的结点一定是兄弟结点
D.树中任一非叶结点的权值一定不小于下一层任一结点的权值
解析:
A.哈夫曼树也叫最右二叉树和带权路径最小树,是一颗二叉树,但并不一定是完全的二叉树。
B.结点的孩子个数称为结点的度,哈夫曼树中只有度为2的结点和度为0的叶子结点。
C.哈夫曼树的构造是从底到上,从小到大,所以最小权值的两个结点一定用于底部,是兄弟结点。
D.根据哈弗曼树的定义,一棵二叉树要使其WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点,任一非叶子结点的权值是等于其自己孩子结点权值之和,大于或等于下一层的任一结点的权值。