13高初试题解析.doc

13高初试题解析.doc第十九届全国青少年信息学奥林匹克联赛初赛(提高组)试题解析
下午带学生去比赛,回来应学生要求,将这份试卷认真做了一遍,以下答案仅供参考,如有错误,欢迎批评指正,谢谢!
一、单选题(15*)
1、A,一个字节有8个bit,32位整型变量占用4个字节,故选A。
2、A,,()2 = 1*2+1+0*+1* = ()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、AC,求1,2,...100的和,这个平时练习过很多次。
2、AD,只有快速排序和归并排序是nlgn的,冒泡和插入都是n^2的时间复杂度。
3、CD,此题最开始以为选BD,因为我题目错看成宽度优先搜索了。
4、AB,如果一个问题复杂度是该问题的一个实例规模n的多项式函数,则这种可以在多项式时间内解决的问题属于P类问题;可以在多项式时间内验证一个解是否正确的问题称为NP类问题;可以在多项式时间内解决的问题一定可以在多项式时间内验证,所以P类问题一定属于NP类问题,故此题应选择AB,D我看错了,NP类问题显然不是说在指数时间内能够解决的问题,谢谢网友提示!