tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析


NOIP2013 第十九届全国青少年信息学奥林匹克联赛 初赛(提高组)试题解析
一、单选题(15*1.5) 1、A,一个字节有 8 个 bit,32 位整型变量占用 4 个字节,故选 A。 2、A,二进制 11.01 转为十进制,(11.01)2 = 1*2+1+0*0.5+1*0.25 = (3.25) 10 。 3、 B,老和尚给小和尚讲的故事里边有故事本身,递归是

函数内部调用函数本身, 故选 B,递归。 4、D,香农信息论鼻祖。 5、A,一定是满二叉树时拥有 2 个字节点的节点数最多,最下一层会有 2013-1023=990 个节点,于是倒数第二层会有 990/2=495 个节点有 2 个字节点, 从第 1 层到倒数第三层共有 1023-2^9=511 个节点,且这些节点都是用 2 个子节 点的节点,所以共有 495+511=1006 个,选 A。 6、B,要使图不联通,只要其中某一个节点不连通即可,所有顶点度最少是 3, 所以最少需要删除 3 条边,选 B。 7、D,此题最开始一眼扫到的时候脑子进水,跟学生将选 B,O(n),实际上不 是,计算 F1 需要 1 次,计算 F2 需要一次,计算 Fn 需要计算 F(n-1)的次数加上 F(n-2)的次数,所以其实就是计算 Fn 次,于是答案选择 D,至于这个 Fn 到底 是多大,数学上可以计算,它等于 O(((1+sqrt(5))/2)^n). 8、B,这个必须是 B,没有什么好说的,中序遍历保证左边都是小于根的,右边 都是大于根的,所以可以保证是一个有序序列。 9、D,A 项 6 和 17 对 11 取余都是 6 发生冲突,B 项 10 的平方和 17 的平方对 11 取余都是 1 发生冲突,C 项 6 的两倍和 17 的两倍对 11 取余都是 1 发生冲突,D 项分别为 1,2,3,4,不冲突。 10、D,IPV6 地址是 128 位的。谢谢网友指正! 11、C,二分为 6 个和 6 个的顶点,此时边最多,有 36 条边。 12、B,我的学生几乎全选 A 去了,因为之前讲题只介绍过 ASCII 码,但是看到 统一二字也应该想到 Uni...前缀啊。 13、D,64 位非零浮点数强制转换成 32 位浮点数,两个数会有大小上的细微差 别,但不会发生符号变化,因为有专门的符号位。 14、 Dijkstra 算法计算单源最短路时间复杂度如果不借助堆或优先队列优化, B, 是 O(n^2). 15、B,此题和学生讲的时候又是脑子进水了,我一眼扫以为选 A,后来令 n=2, 4,8,16 等值带如递推式,发现计算出来的 T(n)和 n 不成线性关系,也不成 n^2 关系,仔细研究了一下,发现其实是 nlgn,具体可以画图证明。 二、不定项选择题(5*1.5) 1、AC,求 1,2,...100 的和,这个平时练习过很多次。 2、 只有快速排序和归并排序是 nlgn 的, AD, 冒泡和插入都是 n^2 的时间复杂度。 3、CD,此题最开始以为选 BD,因为我题目错看成宽度优先搜索了。 4、AB,如果一个问题复杂度是该问题的一个实例规模 n 的多项式函数,则这种 可以在多项式时间内解决的问题属于 P 类问题; 可以在多项式时间内验证一个解

是否正确的问题称为 NP 类问题;可以在多项式时间内解决的问题一定可以在多 项式时间内验证,所以 P 类问题一定属于 NP 类问题,故此题应选择 AB,D 我看 错了,NP 类问题显然不是说在指数时间内能够解决的问题,谢谢网友提示!。 5、ABCD,此题完全不会,因为是第一次带学生参赛,对复赛什么情况完全不了 解,个人觉得程序名、输出文件名这类问题不应该是什么大问题应该允许申诉, 但对 BD 这些没按规定要求做的肯定不会受理的,网友回复说选 ABCD,那就暂时 改为 ABCD,如有其他声音,欢迎批评指正。 三、问题求解(2*5) 1、0 1 1 1;此题应该算是简单题,密码都是 0 或 1,所以根据第 5 项可以很轻 松得到 S1=0,再根据第 1 项可以得到 S2=1,再根据第 3 项可以 S3=1,最后根据 第 2 项得到 S4=1,然后利用第 4 项进行验证发现可行。 2、37/12,此题最开始看到做不出来,只知道这是一道求数学期望的题目。计算 n=2 为什么平均一共跳 2 次的时候,我最开始是这么想的,1 次跳到 1 处的概率 是 1/2,2 次的概率是 1/4,3 次是 1/8.。。。于是数学期望 Ex=1*1/2+2*1/4+3*1/8+......=2,但是这样的计算对于后边 n=3,得情况却怎 么都算不了,于是想到递归,设从 2 跳到 1 的期望是 f2,那么有 1/2 的概率是 一次跳到 1,还有 1/2 的概率是(1+f2)次跳到 1,即第一次没有跳到 1,跳到 2 的情况,于是可以列出等式:f2=1*1/2+(1+f2)*1/2,解出 f2=2;对于 n=3,则 有 1/3 的概率一次跳到 1,有 1/3 的概率(1+f2)次跳到 1,即第一次跳到 2, 再从 2 跳到 1 的过程, 最后还有 1/3 的概率 (1+f3) 次跳到 1, 于是 f3=1/3+ 1+f2) ( *1/3+(1+f3)*1/3,解出 f3=2.5;同理 f4=1/4+(1+f2)*1/4+(1+f3)*1/4+ (1+f4)*1/4,解出 f4=17/6;f5=1/5+ (1+f2)*1/5+(1+f3)*1/5+(1+f4)*1/5+(1+f5)*1/5,解出 f5=37/12. 四、阅读程序写结果(4*8) 1、 Yes, 此程序判断给定字符串是否是回文串。 显然输入串"abceecba"是回文串。 2、133,此题计数 1-1000 范围内能够整除 10 或 15 的数有多少个,使用容斥原 理或者集合求并很容易可以得到 1000/10+1000/15-1000/30=133. 3、4,此题实际上是一种简单的动态规划的方法找最长递增串的长度,从输入数 据 3 2 5 11 12 7 4 10 来看,显然最长的递增串可以是 3 5 11 12,长度为 4; 4、7,似乎二分图染色问题,手动模拟出结果为 7. 五、完善程序(15+13) 1、n-p+i i-p+1 a[i-p] i>end1 i j-1; 序列重排还是比较简单的一道题目,第一种方法是通过开一个 b 数组,然后先将 a 数组中 1 到 p 的数复制到 b 数组中 n-p+1 到 n,将 p+1 到 n 区间的数复制到 b 数组 1,n-p,最后再将 b 数组元素复制回 a 数组中;显然第一空是 n-p+i。 第二种方法是以时间换空间的方法, 每一次先将要移到前面的数保存在 temp 中, 然后将前面那 p 个数依次往后移,再将空出来的那个位置存 temp;所以第二个 空和第三个空分别是 i-p+1 和 a[i-p]。 第三种方法的实际上是一种递归的思想,第四、五、六空分别是 i〉end1 i,i, j-1 2、j-i cur1 count1--; count2--; cur1=a[j],此题没什么好说的,题目中的 注释已经讲得很明白了。


推荐相关:

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析_学科竞赛_高中教育_教育专区。NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛试题解析NOIP...


第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_...任何一个在(输入规模的)指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束后...


第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_...任何一个在(输入规模的)指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束后...


NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组Pascal试题【整理版附答案】

NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组Pascal试题、整理打印版、答案第十九届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言试题 竞赛时间:2013...


2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题

2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题_自我管理与提升_求职...; end. CCF NOIP2013 初赛提高组 Pascal 语言试题 第 11 页,共 11 页 ...


2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_高中教育_教育专区。...输入:3 5 输出:___ CCF NOIP2013 第十九届 初赛普及组 Pascal 语言试题 ...


2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_学科竞赛_初中教育_教育...CCF NOIP2013 第十九届 初赛普及组 Pascal 语言试题 输入:3 5 输出:___ 2...


第十九届全国奥林匹克信息学联赛初赛(NOIP2013)

第十九届全国奥林匹克信息学联赛初赛(NOIP2013)_IT/计算机_专业资料。第十九届全国青少年信息学奥林匹克联赛初赛提高组 C 语言试题 竞赛时间:2013 年 10 月 13 日...


NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案

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

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com