1999年至历年信息学奥赛提高组初赛答案.docx
- 文档编号:4818000
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:30
- 大小:61.69KB
1999年至历年信息学奥赛提高组初赛答案.docx
《1999年至历年信息学奥赛提高组初赛答案.docx》由会员分享,可在线阅读,更多相关《1999年至历年信息学奥赛提高组初赛答案.docx(30页珍藏版)》请在冰点文库上搜索。
1999年至历年信息学奥赛提高组初赛答案
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、0111;此题应该算是简单题,密码都是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,此题实际上是一种简单的动态规划的方法找最长递增串的长度,从输入数据32511127410来看,显然最长的递增串可以是351112,长度为4;
4、7,似乎二分图染色问题,手动模拟出结果为7.
五、完善程序(15+13)
1、n-p+ii-p+1a[i-p]i>end1ij-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〉end1i,i,j-1
2、j-icur1count1--;count2--;cur1=a[j],此题没什么好说的,题目中的注释已经讲得很明白了。
NOIP2012初赛提高组参考答案(PASCAL)
一、单项选择题
1
2
3
4
5
6
7
8
9
10
A
B
B
A
D
A
A
D
A
B
二、不定项选择题
1
2
3
4
5
6
7
8
9
10
A
AD
AD
BD
ABC
CD
AB
A
CD
BD
三、问题求解
1、 256
2、 5536
四、阅读程序题
1.41
2.16
3.
(1)7
(2)2004
4.55
五、完成程序题
1、
(1)false
(2)used[data[i]]:
=false; (3)j (4)n (5)break
2、
(1)next:
=kmodc+1 或 next:
=(kmodc)+1
(2)s[n]:
=q[tail]; (3)q[head]
(4)q[head] (5)q[tail] (6)next(head)
注:
false可以用0来代替;
第十七届(2011年)信息学奥赛提高组初赛试题答案
一、单项选择题(共10题,每题1.5分,共计15分)
1
2
3
4
5
6
7
8
9
10
B
B
A
D
B
A
C
D
B
A
二、不定项选择题(共10题,每题1.5分,共计15分,多选或少选均不得分)
1
2
3
4
5
6
7
8
9
10
CD
ABCD
AB
BC
BC
ABD
CD
A
BCD
ABC
三、问题求解(共2题,每题5分,共计10分)
1.9
2.4
四、阅读程序写结果(共4题,每题8分,共计32分)
1.3
2.1251334
3.150
4.57344
五、完善程序(第1题,每空2分,第2题,每空3分,共计28分)
(说明:
以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不一定上报科学委员会审查)
1.①ans.num[i+j-1]
②ans.num[i]:
=ans.num[i]mod10;
③ans.num[i]+a.num[i]+b.num[i];
④ans.num[i]mod2(或ans.num[i]and1)
⑤inc(ans.len)(或ans.len:
=ans.len+1)
⑥a.len ⑦ord('0')(或48) ⑧times(middle,middle),target 2.①inc(num)(或num: =num+1) ②j: =i ③solve(left,j-1,deep+1) ④solve(j+1,right,deep+1) 第十六届(2010年)信息学奥赛初赛试题答案 一、单项选择题(共10题,每题1.5分,共计15分) 12345678910 CAADBDCBCB 二、不定项选择题(共10题,每题1.5分,共计15分,多选或少选均不得分) 12345678910 ACDADABDACBBDDBCDABC 三、问题求解(共3题,每题5分,共计15分) 1.yyxyxxyyxyxyxxxxyx2.123.18 四、阅读程序写结果(共4题,每题7分,共计28分) 1.162.123567910143.44.169548327 五、完善程序(第1空2分,其余10空,每空2.5分,共计27分) (说明: 以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不一定上报科学委员会审查) 1.①num<=2(或num<3或num=2) ②go(LEFT_TO_RIGHT) ③pos[i]=LEFT(或LEFT=pos[i]) ④time[i]+go(RIGHT_TO_LEFT)(或go(RIGHT_TO_LEFT)+time[i]) ⑤pos[i]: =LEFT 本小题中,LEFT可用true代替,LEFT_TO_RIGHT可用true代替,RIGHT_TO_LEFT可用false代替。 2.①opt[k] ②home[r]: =k ③j: =i+i(或j: =2*i或j: =i*2) ④swap(i,j)(或swap(j,i)) ⑤value[i]+heap[1](或heap[1]+value[i]) ⑥i-m 第十五届(2009年)信息学奥赛提高组初赛试题答案 一.单项选择题(共10题,每题1.5分,共计15分,每题有且仅有一个正确答案。 ) 1、关于图灵机下面的说法哪个是正确的: 答案(C) A)图灵机是世界上最早的电子计算机。 B)由于大量使用磁带操作,图灵机运行速度很慢。 C)图灵机只是一个理论上的计算模型。 D)图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作用。 最早的计算机是ENIAC 图灵机是计算机模型,没有运行速度,更谈不上磁带操作 图灵机是英国人阿兰图灵提出的理论, 阿兰图灵本人在二战中破译德军密码系统发挥重要作用,而不是图灵机发挥作用。 图灵是英国著名的数学家和逻辑学家,被称为计算机科学之父、人工智能之父,是计算机逻辑的奠基者,提出了“图灵机”和“图灵测试”等重要概念。 人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。 1936年,阿兰.图灵提出了一种抽象的计算模型──图灵机(TuringMachine)。 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作: 在纸上写上或擦除某个符号; 把注意力从纸的一个位置移动到另一个位置; “图灵机”不是一种具体的机器,而是一种思想模型,可制造一种十分简单但运算能力极强的计算机装置,用来计算所有能想像得到的可计算函数。 装置由一个控制器和一根假设两端无界的工作带(起存储器的作用)组成。 工作带被划分为大小相同的方格,每一格上可书写一个给定字母表上的符号。 控制器可以在带上左右移动,它带有一个读写出一个你期待的结果。 外行人看了会坠入云里雾里,而内行人则称它是“阐明现代电脑原理的开山之作”,并冠以“理想计算机”的名称。 “图灵机”更在电脑史上与“冯·诺依曼机”齐名,被永远载入计算机的发展史中。 回顾20世纪科学技术的辉煌发展时,不能不提及20世纪最杰出的数学家之一的冯·诺依曼(美籍匈牙利人)。 20世纪40年代,冯·诺依曼在参与世界上第一台计算机-ENIAC的研制小组工作时,发现ENIAC有两个致命的缺陷: 一是采用十进制运算,逻辑元件多,结构复杂,可靠性低;二是没有内部存贮器,操纵运算的指令分散存贮在许多电路部件内,这些运算部件如同一副积木,解题时必须像搭积木一样用人工把大量运算部件搭配成各种解题的布局,每算一题都要搭配一次,非常麻烦且费时。 针对这两个问题,诺依曼和其他合作者一起呕心沥血地进行了半年多时间的改革性研究,结果取得了令人满意的成果。 但是,由于ENIAC的制造已接近尾声,因此它未能采用诺依曼的改进意见。 诺依曼的研究成果得到了ENIAC研制小组专家的青睐,他们在ENIAC尚未竣工之前,就着手计划一个结构全新的电子计算机—EDVAC方案。 1945年6月底,由诺依曼执笔写出了EDVAC计划草案。 在这个方案中,诺依曼提出了在计算机中采用二进制算法和设置内存贮器的理论,并明确规定了电子计算机必须由运算器、控制器、存贮器、输入设备和输出设备等五大部分构成的基本结构形式。 他认为,计算机采用二进制算法和内存贮器后,指令和数据便可以一起存放在存贮器中,并可作同样处理,这样,不仅可以使计算机的结构大大简化,而且为实现运算控制自动化和提高运算速度提供了良好的条件。 EDVAC于1952年建成,它的运算速度与ENIAC相似,而使用的电子管却只有5900多个,比ENIAC少得多。 EDVAC的诞生,使计算机技术出现了一个新的飞跃。 它奠定了现代电子计算机的基本结构,标志着电子计算机时代的真正开始。 根据冯·诺依曼提出的原理制造的计算机被称为冯·诺依曼结构计算机,现代计算机虽然结构更加复杂,计算能力更加强大,但仍然是基于这一原理设计的,也是冯诺依曼机。 最简单的来说,他的精髓贡献是2点: 2进制思想与程序内存思想。 2、关于BIOS下面的说法哪个是正确的: 答案(A) A)BIOS是计算机基本输入输出系统软件的简称。 B)BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。 C)BIOS一般由操作系统厂商来开发完成。 D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 其实bios=Basic Input Output System。 但是对于是否是软件这一说法还存在争议呢! BIOS只存一些系统启动的基本信息,这些设备的驱动程序是不存的。 BIOS一般是由单独的芯片厂家生产的,最著名的都是台湾的三家。 固件BIOS根本这些功能。 BIOS是"基本输入输出系统"。 其实,它是一组固化到计算机内主板上一个ROM芯片上的程序,它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。 3、已知大写字母A的ASCII编码为65(十进制),则大写字母J的十六进制ASCII编码为: 答案(D) A)48B)49C)50D)以上都不是 “0”的ASCII编码为48 “A”的ASCII编码为65 “a”的ASCII编码为97 4、在字长为16位的系统环境下,一个16位带符号整数的二进制补码为 111111*********1。 其对应的十进制整数应该是: 答案(B) A)19B)-19C)18D)-18 最高位为符号位 补码–1再取反 原码: 1000000000010011 十进制整数: -19 5、一个包含n个分支结点(非叶结点)的非空满k叉树,k>=1,它的叶结点数目为: 答案(D) A)nk+1B)nk-1C)(k+1)n-1D)(k-1)n+1 多叉树的性质,N0=(K-1)N+1,考试的时带入K=2时候,验证二叉树能得到结果。 二叉树的性质: N0=N2+1 即叶子节点比二叉节点数多一个。 (1)完全二叉树的定义: 深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。 特点: 叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l或l+1 (2)满二叉树: 一棵深度为k,且有2的(k)次方-1个节点的二叉树 特点: 每一层上的结点数都是最大结点数 满二叉树肯定是完全二叉树 完全二叉树不一定是满二叉树 一棵深度为K且有2的K次方减1个结点的二叉树称为满二叉树。 深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至N的结点一一对应,称之为完全二叉树。 0 0 0 / \ / \ / \ 0 0 0 0 0 0 /\ /\ / /\ 0 00 0 0 0 0 (1) (2) (3) 1、是满二叉树,也是完全二叉树。 2、是完全二叉树。 3、非完全二叉树。 简单的讲,将节点按层次从1-n编号: 1 / \ 2 3 /\ /\ 4 56 7 ........... 缺少的节点只能是大号的,即: 如果n号节点存在,则1到n-1号节点必定存在, 同样,若n号节点不存在,则n+1号及更大号的节点也必定不存在 可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知: n0=n2+1,则n=n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得: n=2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2,合并成一个公式: n0=(n+1)/2,就可根据完全二叉树的结点总数计算出叶子结点数。 6、表达式a*(b+c)-d的后缀表达式是: 答案(B) A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd 主要是考树的遍历,要明白前缀、中缀和后缀表达式。 构造二叉树,操作数做叶子节点,运算符做非叶节点。 按中序遍历就可以得到中缀表达式。 根据所给表达式(其实正常的都是中缀表达式)可以构造二叉树 — /\ *d /\ a+ /\ bc 中缀表达式就是中序遍历a*(b+c)-d 后缀表达式就是后续遍历abc+*d- 前缀表达式就是前序遍历-*a+bcd 7、最优前缀编码,也称Huffman编码。 这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码,以提高通讯的效率。 下面编码组合哪一组不是合法的前缀编码: 答案(B) A)(00,01,10,11) B)(0,1,00,11) C)(0,10,110,111) D)(1,01,000,001) 0是00的前缀码,这部分是数据结构中哈夫曼编码处的知识。 哈夫曼编码 从哈夫曼树根结点开始,对左子树分配代码“0”,右子树分配代码“1”,一直到达叶子结点为止,然后将从树根沿每条路径到达叶子结点的代码排列起来,便得到了哈夫曼编码。 例,对电文EMCAD编码。 若等长编码,则 EMCAD=>000001010011100共15位 设各字母的使用频度为{E,M,C,A,D}={1,2,3,3,4}。 用频度为权值生成哈夫曼树,并在叶子上标注对应的字母,树枝分配代码“0”或“1”: 各字母的编码即为哈夫曼编码: EMCAD=>000001011011共12位 8、快速排序平均情况和最坏情况下的算法时间复杂度分别为: 答案(A) A)平均情况O(nlog(2,n)),最坏情况O(n^2) B)平均情况O(n),最坏情况O(n^2) C)平均情况O(n),最坏情况O(nlog(2,n)) D)平均情况O(log(2,n)),最坏情况O(n^2) 最好的时候是n×log(2,n),最坏情况的是退化成冒泡排序,复杂度为O(n^2)。 选择排序: O(n^2) 冒泡排序: O(n^2) 计数排序: O(n^2) 比较排序: O(log(2,n)-1.44n) 堆排序: O(log(2,n)) 9、左图给出了一个加权无向图,从顶点V0开始用prim算法求最小生成树。 则依次加入最小生成树的顶点集合的顶点序列为: 答案(A) A)V0,V1,V2,V3,V5,V4 B)V0,V1,V5,V4,V3,V3 C)V1,V2,V3,V0,V5,V4 D)V1,V2,V3,V0,V4,V5 加入的边依次为v0v1、v1v2、v1v3(或v2v3)、v1v5、v3v4。 Prim算法用于求无向图的最小生成树。 假设V是图中顶点的集合,E是图中边的集合,设图G=(V,E),其生成树的顶点集合为U。 ①、把v0放入U。 ②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树。 ③、把②找到的边的v加入U集合。 如果U集合已有n个元素,则结束,否则继续执行②。 其算法的时间复
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 1999 历年 信息学 提高 初赛 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)