资源描述：
《noip2015初赛普及组答案分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、单项选择题1.A。计算机内部的用来传送、存贮、加工处理的数据或指令都是以二进制形式进行的。2.A。写这题我用的是排除法,B选项显然不对,内存在断电后数据会丢失,C选项也是,屏幕的分辨率是可以手动调整的,D选项,当年我们都用宽带连接Internet的。3.A。二进制小数转化为十六进制小数时,每四位二进制数转化为以为十六进制数,故0.10002可以转化为0.816。4.D。我的做法是将每个数都化为二进制形式,因为十六进制数和八进制数转化为二进制数很容易,最后求得答案是D。5.D。在链表中,每个结点包括两个部分：一个是存储数据元
2、素的数据域,另一个是存储下一个结点地址的指针域,结点与结点之间是用指针连接的,故地址不必连续。6.B。模拟一下进栈出栈的过程就行了,共有6次操作:进栈,进栈,出栈,进栈,进栈,出栈,每次操作后栈内元素分别为”a”,”ab”,”a”,”abc”,”abcd”,”abc”,故最后栈顶元素是c。7.B。前序遍历的顺序是”根->左->右”,后序遍历的顺序是”左->右->根”,对照四个答案,只有B能满足题目要求。8.B。我们知道树高为n的满二叉树的结点个数为2n−1,当树高为5时结点个数为31,当树高为6时结点个数为63,故答案是B
3、。9.B。画一张图的事情,就不说了。10.D。由递推公式可得T(n)=1+(1+2+…+n)=n2+n2+1,故算法时间的复杂度为O(n2)。11.D。用vector存边,由一个顶点的边引到另一个顶点,再不断引出别的顶点,过程中每个顶点和每条边都只用到一遍,故复杂度为O(n+e)。12.A。哈夫曼算法用来求哈夫曼树,此树的特点就是引出的路程最短,求的过程运用到贪心思想,具体的请参考一下别的文章。13.D。llink和rlink分别指向前驱和后继,不妨设p的前驱为o,在未插入前p->llink就是o,o->rlink就是p,
4、插入时,先将o->rlink赋为q,再将q->rlink赋为p,然后将q->llink赋为o,最后将p->llink赋为q。14.A。最粗暴的方法就是直接模拟,不知道有没有更先进的算法。15.A。--丨这题猜猜都是A,哪有考生自带鼠标的。不定项选择题1.ABCD。典型的操作系统有UNIX、Linux、MacOSX、Windows、iOS、Android、WP、ChromeOS等,还望读者能记住。2.ABC。视频文件常见格式有AVI、WMV、MPEG、DivX/xvid、DV、MKV、RM/RMVB、MOV、OGG、MOD等
5、。3.ACD。IP地址实际上是32位二进制数，为了便于记忆就分为四段，每段八位，中间用小数点隔开。每段八位的二进制数转成十进制，大小为0至255。这种格式称为点分十进制。4.AB。树的边数=结点个数-1,哈夫曼树是一棵满二叉树,故叶节点数比非叶节点数多1。5.AC。二分图左半部分全黑,右半部分全白就可以了,树的话只要满足子节点和父节点的颜色相异就行了。问题求解1.在1和2015之间(包括1和2015在内)不能被4、5、6三个数任意一个数整除的数有_______个。解析：1075。题目要求的是不能被整除的数,但仔细想想并没有
6、什么好的求法。于是转换思想,我们可以先求能被整除的数。区间内能被4整除的数有503个,能被5整除的数有403个,能被6整除的数有335个,难道只是把这几个数加起来吗？并不是的,我们还要减去能被4和5、4和6、5和6的最小公倍数整除的数,因为这些数被算了两遍。区间内能被20整除的数有100个,能被12整除的数有167个,能被30整除的有67个,我们将这些数减去之后还不行,因为答案中4、5、6的最小公倍数都被减去了,所以还要加上区间中能被60整除的数。求出结果是503+403+335-100-67-167+33=940个,这样
7、求出来的是能被整除的数,所以答案是2015-940=1075个。2.结点数为5的不同形态的二叉树一共有_______种。(结点数为2的二叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。)解析：42。直接枚举出答案自然是可行，但有更简单的方法，那就是递推。我们记fn为结点数为n的二叉树的种数：当二叉树的左子树结点个数为0时,有f0×fn−1种方案；当左子树结点个数为1时,有f1×fn−2种方案；当左子树结点个数为2时,有f2×fn−3种方案；……；当左子树结点个数为n-1个时,有fn−1×f0种方案。由此可得f
8、n=∑i=0n−1fi×fn−1−i这就是著名的卡特兰数,关于这条公式可以参见一下百度百科的catalan。求得这个公式之后就可以代入求解了,最后求得答案是42种。阅读程序写结果由于代码比较长，在此不给出代码。1.3,2。定义了两个结构体,e.a=1,e.b=2,则e.c.x=e.a+e.b=3,e.c
