nbhkdz.com冰点文库

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


第十九届全国青少年信息学奥林匹克联赛初赛(提高组)试题解析
下午带学生去比赛,回来应学生要求,将这份试卷认真做了一遍,以下答案仅供参考,如有错 误,欢迎批评指正,谢谢! 一、单选题(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 算法计算单源最短路时间复杂度如果不借助堆或优先队列优化, O B, 是 (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/2, 次的概率是 1/4, 1 2 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],此题没什么好说的,题目中的注释 已经讲得很明白了。


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

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

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

第十九届全国青少年信息学奥林匹克联赛初赛(提高组)试题解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛(提高组)试题解析 NOIP2003 C语言...

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

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

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

2013年第十九届全国青少年信息学奥林匹克联赛提高组初赛试题_自我管理与提升_求职/职场_应用文书。第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题竞赛...

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

2013第十九届全国青少年信息学奥林匹克联赛初赛提高组(C++)_学科竞赛_高中教育_教育专区。C++ 2013 第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 ...

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

NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考...NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛 ...执业医师实践技能考试模拟试题89份文档 应届生求职季...

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

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_高中教育_教育专区。2013 年第十九届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 一、单项选择...

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

2013第十九届全国青少年信息学奥林匹克联赛普及组初赛试题_学科竞赛_初中教育_教育专区。2013 年第十九届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 一、...

2015年第二十一届全国青少年信息学奥林匹克联赛提高组初赛试题(C++)

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