《2013NOIP初赛提高组试题解析》由会员分享，可在线阅读，更多相关《2013NOIP初赛提高组试题解析（19页珍藏版）》请在金锄头文库上搜索。
1、19.2 十九届提高组一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项） 1一个32位整型变量占用（ A ）个字节。A4 B8 C32 D128 2二进制数11.01在十进制下是（ A ）。A3.25 B4.125 C6.25 D11.125 3下面的故事与（ B ）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事“：从前有座山，山里有座庙， 庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和 尚讲故事”A. 枚举B.递归C.贪心D.分治41948年，（ D ）将热力学中的熵引入信息通信领域，标志着信息论研
2、究的开端。A.冯诺伊曼（John von Neumann）B.图灵（Alan Turing）C.欧拉（Leonhard Euler）D.克劳德香农（Claude Shannon）【分析】 香农信息论鼻祖5.已知一棵二叉树有2013个节点，则其中至多有（ A ）个节点有2个子节点。 A.1006B.1007C.1023D.1024【分析 （ 1 ）树根深度为0，深度为10的满二叉树节点总数2047；（ 2 ）本题树深为10的完全二叉树，与满二叉树相比少了34个节点，（ 3 ）深度为9的满二叉树节点总数量为1023；（ 4 ） 1023- （ 34/2 ） =10066.在一个有向图中，如果任意两
3、点之间都存在路径相连，则称其为连通图。 右图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少 要删去其中的（B ）条边。A. 2B. 3C. 4D. 5【分析】要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是 要删除3条边7斐波那契数列的定义如下：Fl, F2=1，Fn=Fn-1+Fn-2 （n3）。如果用下面的函数计算斐波 那契数列的第n项，则其时间复杂度为（D ）。function F（n:longint）:longint;beginif n100 do begin.3UJlL：=5LLIIl+I；end;C.i：=l；tepeatsum： =eujh+I; mc(
4、i);until i100;D.i：=l；repeatEUJll：=EUJIl+I； mc(ik until i=100;2D.归并排序 2的时间复杂度。（AD ）的平均时间复杂度为0（n log n）,其中n是待排序的元素个数。 A.快速排序B.插入排序C.冒泡排序【分析】只有快速排序和归并排序是n log n的，冒泡和插入都是n3.以A0作为起点，对下面的无向图进行深度优先遍历时（遍历的顺 序与顶点字母的下标无关），（A.CDA1)。B. A2 C. A34.A.C.D.最后一个遍历到的顶点可能是D. A4AB存在一个P类问题任何一个不属于P类的问题任何一个在（输入规模的）指数时间内能够解
5、决的问题）属于NP类问题。B.任何一个P类问题【分析】1. 时间复杂度：（1）时间复杂度：是指执行算法所需要的计算工作量。时间复杂度并不是表示一个程序 解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多 快。（2）多项式时间算法：如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。时间复杂度丿丿多项式级的复杂 度.如O，O佃g（n）Q（仃沟 等一因为它的 规模林出现在谍 数的&W. !”非多项式级的C如r 0（曲）和 o（m）等！2. P类、NP类问题（1）P 类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，
6、 那么这个问题就属于P问题。（2）NP类问题：NP （Non-de terminis tic Polynomial）问题是指可以在多项式的时间里 验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问 题。（3）所有的P类问题都是NP问题。NP问题不是非P类问题3. NPC问题（NP完全问题）：Cook在1971年给出并证明了有一类问题具有下述性质：（1）这类问题中任何一个问题至今未找到多项式时间算法；（2）如果这类问题中存在一个问题有多项式时间算法，则这类问题都有多项式时间算法 这类问题就是所谓的NP完全问题。（3）NPC问题的定义非常简单。同时满足下面两个条件的问题就
7、是NPC问题。首先，它 得是一个NP问题；然后，所有的NP问题都可以约化到它。NP Problems P ProblemsNP Complete )5. CCF NOIP复赛考试结束后，因(ABCD )提出的申诉将不会被受理。A. 源程序文件名大小写错误B. 源程序保存在指定文件夹以外的位置C. 输出文件的文件名错误D. 只提交了可执行文件，未提交源程序 三、问题求解(共2题，每题5分，共计10分；每题全部答对得5分，没有部分分)1. 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数si, s2,，sn，均为0或1。该系统每次随机生成n个数al，a2,，an，均为0或1,请用户回答(S1a1+S2a2+snan )除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码因为用户并没有直接发送密码。然而，事与愿违。 例如，当n=4时，有人窃听了以下5次问答：分析】
