nbhkdz.com冰点文库

NOIP2015初赛提高组答案

时间:2017-10-14

单项选择题
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初赛提高组答案.pdf

NOIP2015初赛提高组答案 - 单项选择题 1.A。计算机内部的用来传送、存

noip2015初赛普及组与提高组试题与答案.ppt

noip2015初赛普及组与提高组试题与答案_学科竞赛_高中教育_教育专区。noip2015(全国青少年信息学奥林匹克竞赛)初赛普及组与提高组试题与答案 ...

NOIP2015提高组参考答案.pdf

NOIP2015提高组参考答案 - 第二十一届全国青少年信息学奥林匹克联赛初赛 提高组参考答案 一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分) 1 2 3 4...

noip2015提高组复赛试题答案.doc

noip2015提高组复赛试题答案_IT认证_资格考试/认证_教育专区。全国信息学奥林...NOIP2015第二十一届全国... 9页 免费 NOIP2015普及组初赛PASC... 7页 1...

NOIP2015提高组初赛C++试题.pdf

NOIP2015提高组初赛C++试题_学科竞赛_高中教育_教育专区。NOIP2015提高组初赛C++试题 第二十一届全国青少年信息学奥林匹克联赛初赛提高组 C++语言试题 竞赛时间:2015 ...

NOIP2015年初赛提高组模拟试题.doc

NOIP2015初赛提高组模拟试题 - 信息学初赛模拟试题 一、 选择题 (共

NOIP2015提高组.pdf

NOIP2015提高组 - CCF NOIP2015 提高组复赛day1 试题... 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day...NOIP2015初赛提高组答案 5页 1下载券 NOIP2015提...

NOIP2015提高组Pascal试题及参考答案.doc

NOIP2015提高组Pascal试题及参考答案_其它考试_资格考试/认证_教育专区。第二十...第二十一届全国青少年信息学奥林匹克联赛初赛 提高组 Pascal 语言试题竞赛时间:...

NOIP2015提高组初赛试题C++(A3版).doc

第二十一届全国青少年信息学奥林匹克联赛初赛提高组 C++语言试题竞赛时间: 2015 年 10 月 11 日 14:30~16:30 一、单项选择题(共 15 题,每题 1.5 分,共...

NOIP2015提高组C试题.pdf

NOIP2015提高组C试题_学科竞赛_高中教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛提高组 C 语言试题 竞赛时间:2015 年 10 月 11 日 14:30~16:...

NOIP2015提高组Pascal试题及参考答案汇总.doc

NOIP2015提高组Pascal试题及参考答案汇总 - 第二十一届全国青少年信息学奥林匹克联赛初赛 提高组 Pascal 语言试题 竞赛时间:2015 年 10 月 11 日 14:30~16...

NOIP提高组初赛历年试题及答案求解题篇.doc

NOIP 提高组初赛历年试题及答案求解题篇问题求解题(每次 2 题,每题 5 分,共...在 1 和 2015 之间(包括 1 和 2015 在内)不能被 4、 5、 6 三个 数...

NOIP2015提高组复赛试题Day1.doc

NOIP2015提高组复赛试题Day1 - 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day1 (请选...

noip2015提高组复赛试题答案.doc

noip2015提高组复赛试题答案_IT认证_资格考试/认证_教育专区。noip2015 提高组...NOIP2015第二十一届全国... 9页 免费 NOIP2015普及组初赛PASC... 7页 1...

2015年NOIP提高组初赛(C++).doc

2015NOIP提高组初赛(C++) - 第二十一届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每...

NOIP2015提高组复赛 DAY1+DAY2 试题.pdf

NOIP2015提高组复赛 DAY1+DAY2 试题_学科竞赛_高中教育_教育专区。CCF NOIP2015提高组复赛 DAY1+DAY2 试题 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1...

NOIP提高组初赛历年试题及答案选择题篇.pdf

NOIP提高组初赛历年试题及答案选择题篇 - NOIP 提高组初赛历年试题及答案选择题篇 单项选择题(共 10-15 题,每题 1.5 分,共计 15-22.5 分。每题有且仅有...

NOIP2015提高组C++试题.doc

NOIP2015提高组C++试题_电脑基础知识_IT/计算机_专业资料。第二十一届全国青少年信息学奥林匹克联赛初赛提高组 C++语言试题 竞赛时间:2015 年 10 月 11 日 14:...

NOIP2015初赛普及组C++题目及答案.doc

NOIP2015初赛普及组C++题目及答案_学科竞赛_高中教育_教育专区。本文是noip2015年普及组c++的题目及答案,有需要的可以下载学习。 第二十一届全国青少年信息学奥林...

noip2015信息学奥赛初赛试题_图文.pdf

noip2015信息学奥赛初赛试题_学科竞赛_初中教育_教育专区。奥赛 文档贡献者 谁...信息学奥赛普及组初赛模... 10页 2下载券 2018 Baidu |由 百度云 提供...