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、 B, Dijkstra 算法计算单源最短路时间复杂度如果不借助堆或优先队列优化, 是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、AD,只有快速排序和归并排序 是 nlgn 的,冒泡和插入都是 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)_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 文档贡献者 虎头虎脑—— 贡献于2013...


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

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


第十九届全国青少年信息学奥林匹克联赛初赛(含答案)

第十九届全国青少年信息学奥林匹克联赛初赛(含答案)_学科竞赛_初中教育_教育专区...2013NOIP第十九届全国青... 暂无评价 1页 免费喜欢此文档的还喜欢 ...


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

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


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

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


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

2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题_其它课程_高中教育_教育...; end. CCF NOIP2013 初赛提高组 Pascal 语言试题 第 11 页,共 11 页 ...


NOIP2013全国青少年信息学奥林匹克联赛初赛参考答案(提...

NOIP2013全国青少年信息学奥林匹克联赛初赛参考答案(提高组PASCAL)_学科竞赛_高中教育...第十九届全国青少年信息学奥林匹克联赛初赛提高组参考答案 一、单项选择题(共 1...


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

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


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

2013第十九届全国青少年信息学奥林匹克联赛初赛试题_学科竞赛_高中教育_教育专区。...D. 20. CCF NOIP 复赛全国统一评测时使用的系统软件是( )。 A. NOI ...


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

2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题-1_学科竞赛_高中教育...? ? ? CCF NOIP2013 初赛提高组 Pascal 语言试题 第 1 页,共 4 页 begin...

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