资源预览内容
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
第9页 / 共19页
第10页 / 共19页
亲,该文档总共19页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
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 )将热力学中的熵引入信息通信领域,标志着信息论研究的开端。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.在一个有向图中,如果任意两点之间都存在路径相连,则称其为连通图。 右图是一个有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(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类的问题任何一个在(输入规模的)指数时间内能够解决的问题)属于NP类问题。B.任何一个P类问题【分析】1. 时间复杂度:(1)时间复杂度:是指执行算法所需要的计算工作量。时间复杂度并不是表示一个程序 解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多 快。(2)多项式时间算法:如果一个算法,它能在以输入规模为参变量的某个多项式的时间内给出答案,则称它为多项式时间算法。时间复杂度丿丿多项式级的复杂 度.如O,O佃g(n)Q(仃沟 等一因为它的 规模林出现在谍 数的&W. !”非多项式级的C如r 0(曲)和 o(m)等!2. P类、NP类问题(1)P 类问题的概念:如果一个问题可以找到一个能在多项式的时间里解决它的算法, 那么这个问题就属于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问题的定义非常简单。同时满足下面两个条件的问题就是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次问答:分析】
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号