当前位置:首页 >> 学科竞赛 >>

noip2015初赛普及组答案分析


单项选择题
1.A。计算机内部的用来传送、存贮、加工处理的数据或指令都是以二 进制形式进行的。 2.A。写这题我用的是排除法,B 选项显然不对,内存在断电后数据会丢 失,C 选项也是,屏幕的分辨率是可以手动调整的,D 选项,当年我们都用 宽带连接 Internet 的。 3.A。二进制小数转化为十六进制小数时,每四位二进制数转化为以为 十六进制数,故 0.10002 可以转化为 0.816。 4.D。我的做法是将每个数都化为二进制形式,因为十六进制数和八进 制数转化为二进制数很容易,最后求得答案是 D。 5.D。在链表中,每个结点包括两个部分:一个是存储数据元素的数据 域,另一个是存储下一个结点地址的指针域,结点与结点之间是用指针 连接的,故地址不必连续。 6.B。模拟一下进栈出栈的过程就行了,共有 6 次操作:进栈,进栈,出栈, 进栈,进栈,出栈,每次操作后栈内元素分别为”a”,”a b”,”a”,”a b c”,”a b c d”,”a b c”,故最后栈顶元素是 c。 7.B。前序遍历的顺序是”根->左->右”,后序遍历的顺序是”左->右-> 根”,对照四个答案,只有 B 能满足题目要求。 8.B。我们知道树高为 n 的满二叉树的结点个数为 2n?1,当树高为 5 时结点个数为 31,当树高为 6 时结点个数为 63,故答案是 B。 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,插入时,先将 o->rlink 赋为 q,再将 q->rlink 赋为 p,然后将 q->llink 赋为 o,最后将 p->llink 赋为 q。 14.A。最粗暴的方法就是直接模拟,不知道有没有更先进的算法。 15.A。- -丨这题猜猜都是 A,哪有考生自带鼠标的。

不定项选择题
1.ABCD。典型的操作系统有 UNIX、Linux、Mac OS X、Windows、iOS、 Android、WP、Chrome OS 等,还望读者能记住。 2.ABC。视频文件常见格式有 AVI、WMV、MPEG、DivX/xvid、DV、MKV、 RM / RMVB、MOV、OGG、MOD 等。 3.ACD。IP 地址实际上是 32 位二进制数,为了便于记忆就分为四段, 每段八位,中间用小数点隔开。每段八位的二进制数转成十进制,大 小为 0 至 255。这种格式称为点分十进制。 4.AB。树的边数=结点个数-1,哈夫曼树是一棵满二叉树,故叶节点数比 非叶节点数多 1。 5.AC。二分图左半部分全黑,右半部分全白就可以了,树的话只要满足 子节点和父节点的颜色相异就行了。

问题求解
1.在 1 和 2015 之间(包括 1 和 2015 在内)不能被 4、5、6 三个数任意 一个数整除的数有_______个。 解析:1075。题目要求的是不能被整除的数,但仔细想想并没有什么好 的求法。于是转换思想,我们可以先求能被整除的数。区间内能被 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 个,这样求出来的是能被整除的数, 所以答案是 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 种方案。由此可得

fn=∑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.y=e.a*e.b=2,但要注意答案输出时有个“,”, 所以答案是 3,2。 2.Ab。指针变量题,要分清函数传入*a 和&a 的区别,*a 传入的是地 址,&a 传入的是值,如果不是很懂的话,请仔细阅读指针。 3.citizen。很容易看出程序输出的是输入数据中长度最长的字符串, 故答案是 citizen。 4.31。仔细观察函数内容可以发现函数中的 fromPos 和 toPos 并没有 什么卵用,所以不用管这两个变量直接求,答案是 25?1=31 。

完善程序
简单的东西,随便搞搞就行了。(这句话不是我说的,不用太在意)


相关文章:
NOIP2015初赛普及组C++试题及参考答案.doc
NOIP2015初赛普及组C++试题及参考答案_财会/金融考试_资格考试/认证_
noip2015初赛普及组答案分析.doc
noip2015初赛普及组答案分析 - 单项选择题 1.A。计算机内部的用来传送
noip2015初赛普及组与提高组试题与答案.ppt
noip2015初赛普及组与提高组试题与答案_学科竞赛_高中教育_教育专区。noip2015(全国青少年信息学奥林匹克竞赛)初赛普及组与提高组试题与答案 ...
noip2015 初赛普及组C++试题及参考答案.doc
noip2015 初赛普及组C++试题及参考答案_学科竞赛_初中教育_教育专区。NOIP,信息学奥林匹克,竞赛,普及组,试题,答案 Noip 2015 初赛普及组 C++试题 第二十一届全国...
2015-2016NOIP 初赛试题及答案 C++.pdf
2015-2016NOIP 初赛试题及答案 C++_学科竞赛_初中教育_教育专区。noip 普及组 初赛 试题及答案 第二十一届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题 竞赛...
noip2015普及组初赛试卷.pdf
noip2015普及组初赛试卷_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载 | 举报文档 noip2015普及组初赛试卷_学科竞赛_初中教育_教育专区。noip2015 ...
NOIP2015初赛普及组C试题_图文.pdf
NOIP2015初赛普及组C试题_从业资格考试_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP2015初赛普及组C试题_从业资格考试_资格考试/认证_教育专区...
NOIP普及组初赛历年试题及答案完善题篇.pdf
NOIP 普及组初赛历年试题及答案 (完善题篇)完善程序,每年两题,每题每空 2-4...} NOIP2015-1. 打印月历 输入月份 m(1≤m≤12),按一定格式打印 2015 年第...
NOIP2015普及组初赛试题及答案(Pascal).pdf
NOIP2015普及组初赛试题及答案(Pascal) - 第二十一届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言试题 竞赛时间:2015 年 10 月 11 日 14:30~16...
noip2015普及组题解最终分解.doc
noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院 2015 年 11 月 11 ...NOIP2015普及组一等奖 暂无评价 58页 免费 noip2015初赛普及组答案... 暂无...
NOIP2015复赛普及组试题.doc
NOIP2015复赛普及组试题 - 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 (请选手务必仔细阅读本页内容) ...
NOIP2015普及组初赛试题及答案(PASCAL).pdf
NOIP2015普及组初赛试题及答案(PASCAL)_电子/电路_工程科技_专业资料。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 ...
noip2015普及组解题报告.txt
noip2015普及组解题报告_学科竞赛_高中教育_教育专区。noip2015普及组满分解题报告...noip2015普及组答案 1页 免费 noip2015普及组解题报告 14页 1下载券 noip20...
NOIP2015普及组解题报告.doc
NOIP2015 普及组解题报告 From 贴吧 id u007zzt 金币 国王将金币作为工资,发放...答案就是(n1+n2)*(a1+a2)+……+……。如果这样做就是 O(n^2)的 算法...
NOIP2015普及组复赛试题讲解(c++版本)_图文.ppt
NOIP2015普及组复赛试题讲解(c++版本) - 试题分析 NOIP2015 普及组复赛题解 NOIP2015普及组C++ 2017. 07. 28 第1题 “金币”简述 ? 国王将...
noip2015普及组题解最终.doc
每一个答案都有两种可能来源:sum[i-1] +2*s[p[i]]+a[p[i]]+前 i-...noip2015初赛普及组试题... 18页 免费 NOIP2015普及组复赛试卷 7页 1下载券...
NOIP2015普及组初赛试题C++.pdf
NOIP2015普及组初赛试题C++ - 第二十一届全国青少年信息学奥林匹克联赛初赛 普及组 C++语言试题 竞赛时间:2015 年 10 月 11 日 14:30~16:30 选手注意: ? ....
NOIP普及组初赛历年试题及答案求解题篇.pdf
NOIP普及组初赛历年试题及答案求解题篇 - NOIP 普及组初赛历年试题及答案求解题篇 问题求解:每次共 2 题,每空 5 分,共计 10 分。每题全部答对得 5 分,没...
NOIP2015_普及组复赛word版.doc
全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组(请选手务必仔细阅读本页内容)一.题目概况中文题目名称 英文题目...
2015noip第二十一届普及组初赛试题.doc
A.可随机访问任何一个元素 B.插入、删除操作不需要移动元素 C.无需事先估计存储空间大小 D.所需存储空间与存储元素个数成正比 CCF NOIP2015 初赛普及组 Pascal...