NOIP2015初赛题分析
marklikeamd · · 个人记录
- 线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。
A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可
答案：D
解析：数据结构问题=w=，链表结构与顺序结构最大的不同在于链表存储地址可以不连续，便于元素的插入和删除
-
在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ ）思想的算法
A. 贪心 B. 分治 C. 递推 D. 回溯
答案：A
解析： 1.初始化： 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。
2.找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3.删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。
4.判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树
2.下列属于视频文件格式的有（ ）。
A. AVI B. MPEG C. WMV D. JPEG
答案：ABC
常见的视频格式：视频文件格式有不同的分类，如：
微软视频 ：wmv、asf、asx
Real Player ：rm、 rmvb
MPEG视频 ：mpg、mpeg、mpe
手机视频 ：3gp
Apple视频 ：mov
Sony视频 ：mp4、m4v
其他常见视频：avi、dat、mkv、flv、vob
4.下列有关树的叙述中，叙述正确的有（ ）。
A. 在含有n个结点的树中，边数只能是(n-1)条
B. 在哈夫曼树中，叶结点的个数比非叶结点个数多1
C. 完全二叉树一定是满二叉树
D. 在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先
答案：AB
A显然对，B的话了解哈夫曼树的形成的话显然是对的，
C完全二叉树：只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，
D：根左右，在前面的也可能是根的左结点
问题求解
2.结点数为5的不同形态的二叉树一共有__种。
(结点数为2的二叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。)
解析：42。直接枚举出答案自然是可行，但有更简单的方法，那就是递推。 我们记fn为结点数为n的二叉树的种数：当二叉树的左子树结点个数为0时,有f0×fn−1种方案； 当左子树结点个数为1时,有f1×fn−2f1×fn−2种方案； 当左子树结点个数为2时,有f2×fn−3f2×fn−3种方案； …………；
当左子树结点个数为n-1个时,有fn−1×f0fn−1×f0种方案。由此可得
fn=∑i=0n−1fi×fn−1−i
这就是著名的卡特兰数,关于这条公式可以参见一下百度百科的catalan
阅读程序写结果
2.Ab
指针变量题,要分清函数传入a和&a的区别,a传入的是地址,&a传入的是值,如果不是很懂的话，请仔细阅读指针。