关于#数据结构#的问题,如何解决?

img


答案为(1)2;(2)7;(3)求A前n个元素中最后一个最大值元素的下标,n≤0时,返回-1。
请帮忙给个详细的解答过程,谢谢。

【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。

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7774909
  • 除此之外, 这篇博客: 【牛客选择题】树&&二叉树【一】中的 26.对n(n≥2)个权值均不相同的字符构成哈夫曼树, 下列 关于该 哈弗曼 树的叙述中,错误的是(A) 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:

    A.该树一定是一棵完全二叉树
    B.树中一定没有度为1的结点
    C.树中两个权值最小的结点一定是兄弟结点
    D.树中任一非叶结点的权值一定不小于下一层任一结点的权值

    解析:
    A.哈夫曼树也叫最右二叉树和带权路径最小树,是一颗二叉树,但并不一定是完全的二叉树。
    B.结点的孩子个数称为结点的度,哈夫曼树中只有度为2的结点和度为0的叶子结点。
    C.哈夫曼树的构造是从底到上,从小到大,所以最小权值的两个结点一定用于底部,是兄弟结点。
    D.根据哈弗曼树的定义,一棵二叉树要使其WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点,任一非叶子结点的权值是等于其自己孩子结点权值之和,大于或等于下一层的任一结点的权值。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^