《2013NOIP初赛提高组试题解析》由会员分享，可在线阅读，更多相关《2013NOIP初赛提高组试题解析（19页珍藏版）》请在金锄头文库上搜索。
1、19.2 十九届提高组一、单项选择题（共 15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项） 1一个 32 位整型变量占用（ A ）个字节。A4B8C32D1282二进制数 11.01 在十进制下是（ A ）。A3.25B4.125C6.25D11.1253下面的故事与（ B ）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事“：从前有座山，山里有座庙， 庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和 尚讲故事”A.枚举B.递归C.贪心D.分治41948 年，（ D）将热力学中的熵引入信息通信领域，标志着信息论研究的开端
2、。A.冯诺伊曼（John von Neumann）氏图灵（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）=1006A. 2B. 3C.
3、4D. 56.在一个有向图中，如果任意两点之间都存在路径相连，则称其为连通图。 右图是一个有 5个顶点、8 条边的连通图。若要使它不再是连通图，至少 要删去其中的（ B ）条边。分析】要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是 3，所以最少需要删除3 条边 7斐波那契数列的定义如下：Fl, F2=1, Fn=Fn-1+Fn-2 （n3）。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为(D )。 function F(n:longint):longint;beginif n100 dobeginsuni：=siini+I;end;C.i：=l；repeatsum：=
4、suni+I; inc(i);until i100;D.l： = l；repeat sujn：=SLLni+I; inc(i);until i=100;2. ( AD )的平均时间复杂度为0(n log n)，其中n是待排序的元素个数。A 快速排序B.插入排序C.冒泡排序D.归并排序【分析】只有快速排序和归并排序是n log n的，冒泡和插入都是n2的时间复杂度。3. 以 A0 作为起点，对下面的无向图进行深度优先遍历时(遍历的顺 序与顶点字母的下标无关)， 最后一个遍历到的顶点可能是( CD )。A. A1B. A2 C. A3D. A44. ( AB )属于 NP 类问题。A.存在一个P类
5、问题B.任何一个P类问题C. 任何一个不属于P类的问题D. 任何一个在(输入规模的)指数时间内能够解决的问题【分析】1. 时间复杂度：(1) 时间复杂度：是指执行算法所需要的计算工作量。 时间复杂度并不是表示一个程序 解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多 快。(2) 多项式时间算法：如果一个算法，它能在以输入规模为参变量的某个多项式的时间 内给出答案，则称它为多项式时间算法。度.如0、0 他 g(n)Q( 等一因为它的(mm多项式级的如：0(畋0和0(仃!)等！P2.规模n出现在底 的位置!问题一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 ProblemsP ProblemsNP Complete )5. CCF NOIP复赛考试结束后，因（ABCD ）提出的申诉将不会被受理。A.源程序文件名大小写错误 氏源程序保存在指定文件夹以外的位置C. 输出文件的文件名错误D. 只提交了可执行文件，未提交源程序三、问题求解（共 2 题，每题 5 分，共计 10 分；每题全部答对得 5 分，没有部分分）1. 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数si, s2,，sn,均为0或1。该系统每次随机生成n个数al, a2,，an,均为0或1,请用户回答（Slal+S2a2+.+Snan ）除以2的余数。如果多次的回答总是正确，即认
