记录、总结一下值得记录、总结的题。
1.赫夫曼树相关（选择）
题目：由于电文中字符出现的频率不同，设有30个字符，它们在电文中出现的频率分别为1,2,3,4,.....30。用它们组成一颗赫夫曼树，则该赫夫曼树共有几个结点。
解答：先考虑一下赫夫曼树的构造过程：选两个权值最小的字符，作为一个新结点的两个叶子结点。将新节点的权值设为叶子结点权值之和。在剩余的结点中（包含刚刚新组建的结点）中再选择两个权值最小的结点作为叶子结点组成新结点，如此反复直到所有结点都在树上为止。
从构建过程可知：在树中表示字符的结点都是叶子结点，树中没有度为1的结点。用n2,n1,n0分别表示赫夫曼树中度为2,1,0的结点个数。那么n1 = 0。又由二叉树的一般规律n2 = n0 -1.可得总结点数n = 2n0-1.
no = 30，故答案为59。
2.triangle(编程题第二题)
题目：输入n，求对于数列1,2,3,4,5,6,7……n，最少去掉几个数可以使得在剩下的数中任意选择三个（作为三角形三边长度）都无法组成三角型。
分析：组成三角形的条件：较小的两边之和大于第三边。这个题可以反向考虑。考虑剩下哪些数就不能组成三角形了。剩下哪些呢?两边之和小于第三边？想呀想，想呀想。咦，有个数列叫斐波那契数列，听过没？这个数列的特点是一个数等于前两项之和，正好不能组成三角形呀，而且怎么也选不出三个数组成三角形。是的，没错，答案就是这个。
结论：当且仅当剩下的数是斐波那契数列时不能组成三角形。那么这个题就是求：斐波那契数列中小于n的数的个数。再用n减去这个个数。但最骚的这个题我做错的原因是没有看到是多组测试数据，直接处理了一组数据。
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
System.out.print(func(n));
}
}
private static int func(int n) {
if(n < 4) return 0;
else if(n == 4) return 1;
int first = 1;
int second = 2;
int count = 0;
while(second <= n) {
count++;
int tmp = second;
second = second + first;
first = tmp;
}
return (n - count- 1);
}
}
3.C语言的题，求程序输出
#include <stdio.h>
main()
{
char *p = "6938";
int i,s=0;
for(i = 3; i >= 0; i--)
s = 10 * s + p[i] - '0';
printf("%d\n",s);
}
输出6938。其实挺简单的，就是把字符串表示的数字颠倒了过来。
4.在AVL树中，RL失衡状态中可以对插入结点执行哪个操作使之平衡？（选择）
- A 右旋
- B左旋
- C 先右旋再左旋
- D 先左旋再右旋
解析：
先来复习一下AVL树吧。
AVL树即平衡二叉树。它的特点是：他是一个二叉排序树，并且其每一个结点的左右子树都是一颗平衡二叉树，并且左右子树的深度相差最大值为1。
平衡因子：左子树深度减去右子树深度。
AVL的所有结点的平衡因子只有三个取值：-1,0,1
网友评论