当前位置:首页 >> 学科竞赛 >> 2011第17届NOIP试题及解析

2011第17届NOIP试题及解析


第十七届 NOIP2011 提高组初赛试题+答案+解析(pascal) 一、单项选择题(共 10 题,每题 1.5 分,共 15 分,每题有且仅有一个正确选项。 ) 1. 在二进制下,1011010+( )=1100111。 A.1011 B.1101 C.1010 D.1111 答案:B 解析:简单的二进制运算,炮灰都会。 2. 字符“A”的 ASCII 码为十六进制 41,则

字符“Z”的 ASCII 码为十六进制的( ) 。 A.66 B.5A C.50 D.视具体的计算机而定 答案:B 解析:每年必考进制转换题。背得 ASCII 码的可以直接算出 Z 的码然后转回 16 进制。 像我不背得的就把十六进制的 41 转回十进制,4*16+1=65,然后+25 得 90,再转成 16 进制 得 5A。 3. 右图是一棵二叉树,它的先序遍历是( ) 。 (我就不画图了= =带鱼语口述一下:根是 A,左右子树分别为 B 和 C,B 的左右子树分别 为 D 和 E,E 的右子树为 F) A.ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF 答案:A 解析:每年必考树的遍历题。先序遍历就是先根遍历,就是先根,再左右子树的遍历。 然后就 ABDEFC 出来了。从这个解析可以看出这个解析是新手向的解析-。4. 寄存器是( )的重要组成部分。 A. 硬盘 B. 高速缓存 C. 内存 D. 中央处理器(CPU) 答案:D 解析:每年必考硬件知识题。寄存器在 CPU 里。 5. 广度优先搜索时,需要用到的数据结构是( ) 。 A. 链表 B. 队列 C. 栈 D. 散列表 答案:B 解析:数据结构题。广搜需要存每一层的一大堆东西,继续向下一层搜时需要用到,所以要 用存取方便的队列。链表取数不便,栈是深搜用的,散列表就是 hash 表,和宽搜没啥必然 联系。 6. A. B. 在使用高级语言编写程序时,一般提到的“空间复杂度”中的“空间”是指( ) 程序运行时理论上所占的内存空间 程序运行时理论上所占的数组空间

C. 程序运行时理论上所占的硬盘空间 D. 程序源文件理论上所占的硬盘空间 答案:A 解析:常识题。BCD 均明显错。 7. 应用快速排序的分治思想, 可以实现一个求第 K 大数的程序。 假定不考虑极端的最坏 情况,理论上可以实现的最低的算法时间复杂度为( ) 。 A. O(n^2) B. O(n log n) C. O(n) D. O(1) 答案:C 解析:快排思想找第 K 大的数以前初赛就出过,那时是个补完程序题。快排的时间复杂度 是 O(nlogn) ,这题我费解了一下,我认为是 O(logn) ,不过没这个选项,于是我猜是 O (n) 。刚才上网查,这个方法找第 K 大的数时间复杂度的确是 O(n) 。 8. 为解决 Web 应用中的不兼容问题,保障信息的顺利流通, )制定了一系列标准, ( 涉及 HTML、XML、CSS 等,并建议开发者遵循。 A. 微软 B. 美国计算机协会(ACM) C. 联合国教科文组织 D. 万维网联盟(W3C) 答案:D 解析:姿势题,我承认我不会,不过我根据丰富的经验,猜对了。虽然微软很流弊,但是这 种标准一般不是微软定制的;联合国教科文组织总部设在法国巴黎。其宗旨是促进教育、科 学及文化方面的国际合作,以利于各国人民之间的相互了解,维护世界和平。所以就是 D 了。 9. 体育课的铃声响了,同学们都陆续地奔向操场,按老师的要求从高道矮站成一排。每 个同学按顺序来到操场时,都从排尾走到排头,找到第一个比自己高的同学,并站在他的后 面。这种站队的方法类似于( )算法。 A. 快速排序 B. 插入排序 C. 冒泡排序 D. 归并排序 答案:B 解析:排序问题。这个站队方法与插排相同,找个位置插进去! 10. 1956 年( )授予肖克利(William Shockley) (带鱼: “有没有一种‘You are shock!’ 的感觉啊~”、巴丁(John Bardeen)和布拉顿(Walter Brattain),以表彰他们对半导体的研 ) 究和晶体管效应的发现。 A. 诺贝尔物理学奖 B. 约翰·冯·诺依曼奖 C. 图灵奖

D. 高德纳奖(Donald E.Knuth Prize) 答案:A 解析:超级姿势题,没啥人做得对,我也错了?我看 D 标了英文,很犀利的样子,我就选 D 了,结果竟然是 A。D 的那个也是计算机的奖,始于 1996 年。1996 年姚期智得了高德纳 奖,2000 年姚期智得了图灵奖,不过姚期智太不注重名利了,没啥人知道,搜狗拼音都打 不出来。1997 年莱斯利得了高德纳奖,2010 年得了图灵奖,我以为会考最新的图灵奖得主, 背了这人名字,结果没考,考的是几十年前的人??囧

二、不定项选择题(共 10 题,每题 1.5 分,共 15 分。每题有一个或多个正确选项。多选或 少选均不得分。 ) (这部分较难得分,我错了很多题) 1. 如果根节点的深度记为 1,则一棵恰有 2011 个叶子结点的二叉树的深度可能是( ) 。 A. 10 B. 11 C. 12 D. 2011 答案:CD 解析: 可以自己推出, 深度为 n 的满二叉树叶子结点数为 2^ (n-1) 2^10=1024, , 2^11=2048, 深度为 11 的数怎么搞都搞不出 2011 个结点,所以 10 和 11 不选。深度为 n 的一根蛋疼树也 可以有 n 个叶子结点?这个我没考虑到,果断错了。 2. 在布尔逻辑中,逻辑“或”的性质有( )(原题 ABCD 选项里的或是个类似 V 的表 。 示或的符号,为了该文档流通方便我都改成了“V” ) A. 交换律:PVq=qVp B. 结合律:P V(Q V R)=(P V Q)V R C. 幂等律:P V P = P D. 有界率:P V 1 = 1 (1 表示逻辑真) 答案:ABCD 解析:基础题。虽然我不知道 or 是否有什么交换律结合律,思考一下就行了。A,位置交 换肯定不影响结果;B,不管怎么括,都是其中有 1 就是 1,都为 0 才为 0,;C 肯定,D 更 不用说。 3. 一个正整数在十六进制下有 100 位,则它在二进制下可能有( )位。 A. 399 B. 400 C. 401 D. 404 答案:AB 解析:一个十六进制数字可用 4 个二进制数字表示,100 位的十六进制可以用 400 位二进制 表示,当然刚开始那几位可能是 0,所以也可能是 399、398、397 位二进制表示。 4. A. 汇编语言( ) 。 是一种与硬件无关的程序设计语言

B. 在编写复杂程序时,相对于高级语言而言代码量较大,且不易调试 C. 可以直接访问寄存器、内存单元、I/O 端口 D. 随着高级语言的诞生,如今已完全被淘汰,不再使用 答案:BC 解析:姿势题,我姿势不够没做对。A,与硬件有关;B,这是肯定的;C,百度说汇编语 言能够直接访问与硬件相关的存储器或 I/O 端口。D,百度说汇编语言是一种功能很强的程 序设计语言, 也是利用计算机所有硬件特性并能直接控制硬件的语言。 汇编语言是比较底层 的语言,不会不再使用,只是不用来直接编程而已。 5. 现有一段文言文,要通过二进制哈弗曼编码进行压缩。简单起见,假设这段文言文只 由 4 个汉字“之”“乎”“者”“也”组成,它们出现的次数分别为 700、600、300、400。 、 、 、 那么, “也”字的编码长度可能是( ) 。 A. 1 B. 2 C. 3 D. 4 答案:BC 解析:初赛常考的哈夫曼编码。哈夫曼编码是一种很犀利的编码,按那啥的使用频率,把使 用频率高的那啥编为短一点的编码,使用频率高的长一点。一般方法是建一棵哈弗曼树,然 后左子树为 0 右子树为 1,从上到下的一条路为这个叶子结点的编码。百度说把所有东西放 到一个集合 F 中,在 F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树, 新二叉树的根结点的权值为其左右子树的根结点的权值之和。 从 F 中删除这两棵树,并把 这棵新的二叉树同样以升序排列加入到集合 F 中。这样,从这题来看,先弄 300 和 400 的 两个,变成一个根为 700 的树。然后现在就有 600,700,700,选 600 和其中一个 700 再做一 颗树。这样就会有两种情况, “也”可能是 2 位也可能是 3 位,所以选 BC。 6. 生物特征识别是利用人体本身的生物特征进行身份认证的一种技术。 目前, 指纹识别、 虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征 识别技术及其应用的是( ) 。 A. 指静脉验证 B. 步态验证 C. ATM 机密码验证 D. 声音验证 答案:ABD 解析:蛋疼题。主要纠结于选不选 D,你需要一定的考试经验和对出题老师的心理分析,得 出 D 这个选项就是特指生物的声音而不是各种声音,选上 D。 7. 对于序列“7、5、1、9、3、6、8、4” ,在不改变顺序的情况下,去掉( )会使逆序 对的个数减少 3. A. 7 B. 5 C. 3 D. 6 答案:CD

解析: 姿势题, 我没姿势我不自豪, 做错。 百度说, 对于一个包含 N 个非负整数的数组 A[1..n], 如果有 i < j,且 A[ i ]>A[ j ],则称(A[ i] ,A[ j] )为数组 A 中的一个逆序对。现在知道逆序对 是啥了,就容易做了,数字这么少,穷举两个数只需 C(2,8)=28 次,找到所有的逆序对, 自己在草稿纸上开个数组,每找到一个就在这个数下面加一,然后看哪个数在数组里等于 3 的就选它。 8. 计算机中的数值信息分为整数和实数(浮点数) 。实属之所以能表示很大或者很小的 数是由于使用了( ) 。 A. 阶码 B. 补码 C. 反码 D. 较长的位数 答案:A 解析:姿势题,我略看了一点这方面的姿势,我有姿势我自豪。 9. 对右图使用 Dijkstra 算法计算 S 点到其余各点的最短路径长度时, B 点的距离 d B】 到 【 初始时赋值为 8,在算法的执行过程中还会出现的值有( ) 。 (原试题右图, 为照顾手机党我字述边集 ((a,b,c)代表 a 到 b 有条长 c 的边) (S,A,2), : (S,B,8), (S,D,3),(A,B,5),(B,C,1),(B,D,3),(C,D,1) A. 3 B. 7 C. 6 D. 5 答案:BCD 解析:学过 Dijkstra 就知道,我是太久没用这个忘记了囧?Dijkstra 的思想是建个一维数组 记录起点到其他各点的距离(没路为无限大) ,然后找一个这个距起点最近的点作为中间结 点,更新起点到各个点的距离,然后把中心结点加个用过的标记,继续找下一个距离起点最 近的点为中心结点,直到所有的点都当过中心结点就结束。这题中,第一个找到的中间结点 是 A,这时把 SB 更新为 7,然后找到的中心结点为 D,这时把 SB 更新为 6,把 SC 更新为 4;下一个找到的中心结点为 C,这时把 SB 更新为 5。所以选 BCD。 10. 为计算机网络中进行数据交换而建立的规则、 标准或约定的集合称为 (原题写的是 “成 为” )网络协议。下列英文缩写中, )是网络协议。 ( A. HTTP B. TCP/IP C. FTP D. WWW 答案:ABC 解析:网络协议不单指某一协议,而是指各种为计算机网络中进行数据交换而建立的规则、 标准或约定的集合。所以 HTTP(超文本传输协议) 、TCP/IP、FTP(文件传输协议)都属于 网络协议。WWW 是万维网,不是协议。 三、问题求解(共 2 题,每题 5 分,共计 10 分) 1.平面图是可以画在平面上, 且它的边仅在顶点上才能相交的简单无向图。 个顶点的 4

平面图至多有 6 条边,如右图所示。那么,5 个顶点的平面图至多有____条边。 (图我就不画了,比较简单,是一个口画一条对角线,然后没有对角线的那 2 个点从 口外面连了一条曲线) 答案:9 解析:手画,怎么画最多都只能画 9 条,所以?? 2.定义一种字符串操作,一次可以将其中一个元素移到任意位置。举例说明,对于字 符串 “BCA” 可以将 A 移到 B 之前,变成字符串 , “ABC” 如果要将字符串“DACHEBGIF” 。 变成“ABCDEFGHI” ,最少需要____次操作。 答案:4 解析:这个不是交换位置喔,是取出再插入。先在原序列中找个最长上升子序列(除 去某些元素,但不影响相对位置的序列称为子序列) ,发现是 ACEGI,长度为 5,最长了, 剩下 4 个移动一下就能成有序的 ABCDEFGHI 了。

四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. const SIZE=100; var n,i,sum,x:integer; A:array[1..SIZE]of integer; begin readln(n); fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); inc(a[x]); end; i:=0; sum:=0; while sum<(n div 2 + 1) do begin inc(i); sum:=sum+a[i]; end; writeln(i); end. 输入: 11

45664332321 输出:__________ 答案:3 解析:这是个求中位数的程序。注意读入的时候不是把数读进 a[i],而是让 a[x]+1。简单模 拟也可以。

2. var

啊 n:ineger;

procedure f2(x,y:integer); forward; procedure f1(x,y:integer); begin if x<n then f2(y,x+y); end; procedure f2(x,y:integer); begin write(x,’ ‘); f1(y,x+y); end; begin readln(n); f1(0,1); end. 输入:30 输出:__________ 答案:1 2 5 13 34 解析:模拟一下,发现是隔一个输出一个的斐波那契数列,注意主程序调用的是 f1 而 不是 f2,我没注意看以为是 f2 结果整个都错位了囧。

3. 啊 const v = 100;

var visited:array[1..v]of boolean; e:array[1..v,1..v]of integer; n,m,ans,i,j,a,b,c:integer; procedure dfs(x,len:integer); var i:integer; begin visited[x] := true; if len > ans then ans:=len; for i:=1 to n do if (not visited(i)) and(e[x,i] <> -1) then dfs(I,len+e[x,i]); visited[x] := false; end; begin readln(n,m); for i:=1 to n do for j:=1 to n do e[i][j] := -1; for i:=1 to m do begin readln(a,b,c); e[a][b]:=c; e[b][a]:=c; end; for i:=1 to n do visited[i]:=false; ans:=0; for i:=1 to n do dfs(i,0); writeln(ans); end. 输入: 46 1 2 10 2 3 20 3 4 30 4 1 40 1 3 50

2 4 60 输出:______ 答案:150 解析:一眼看去,过程名叫 DFS,输入是个无向图,len>ans 的话 ans:=len,可以得知 这是个在图中用 DFS 找最长的路径的程序。DFS 以任意点作为起点,找一条路径,本次走 过的点不走,找到没路走为止。由于就 4 个点,最多就走 3 条边,看看最长的那 3 条,60 50 40,可以一次走完,即走 2-4-1-3 可以走完这 3 条边,所以 ans 是 150。

4. 啊 const SIZE = 10000; LENGTH = 10; var sum : longint; n,m,I,j : integer; a:array[1..SIZE , 1..LENGTH]of integer; function h(u , v :integer):integer; var ans,i : integer; begin ans:=0; for i:=1 to n do if a[u][i] <> a[v][i] then inc(ans); h := ans; end; begin readln(n); fillchar(a,sizeof (a),0); m:=1; repeat i := 1; while (i <=n) and (a[m][i] =1 ) do inc(i); if i>n then break; a[m][i]:=1; for j:=i + 1 to n do a[m][j] := a[m-1][j]; until false;

sum := 0; for i := 1 to m do for j := 1 to m do sum := sum + h(i,j); writeln(sum); end. 输入:7 输出:______ 答案:57344 解析:这题比起前几题难多了,我看了半天也看不懂这是干啥的,然后手工模拟,还是不懂 是干啥的。于是输入小 n,得出 sum,找规律。 n=1,sum=2 n=2,sum=16 n=3,sum=96 n=4,sum=512 算这个费了很长时间- -然后还得花时间找规律?我这方法是很不好的方法,大家不要 学我。 然后规律是 sum=2^(2n-1) *n,然后就能算出 n=7 的情况了。 (其实我当时还没找到这 个规律,找到的是 sum=2^n*m,m 是个很难算的数,用到了杨辉三角?考完后我发现蛋疼 了) 57344=2^13 *7。


更多相关文档:

2011十七届noip提高组题目及答案

2011十七届noip提高组题目及答案_学科竞赛_高中教育_教育专区。为了打印各种调的~~~第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高组 Pascal 语言 两小时完成...

NOIP2011第十七届初赛C++普及组试题与答案(Word精排版)

NOIP2011第十七届初赛C++普及组试题答案(Word精排版)_IT/计算机_专业资料。NOIP2011第十七届初赛C++普及组试题答案(Word手工精排版)今日...

2011年第十七届信息奥林匹克初赛提高组pascal 附答案

第十七届全国青少年信息学奥林匹克联赛初赛试题 CCF NOIP2011初赛 提高组 ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一、单项选择题 1....

noip2011年第十七届全国青少年信息学奥林匹克联赛初赛...

noip2011第十七届全国青少年信息学奥林匹克联赛初赛答案_学科竞赛_初中教育_教育专区。NOIP2011 普及组(Pascal 语言)参考答案与评分标准 一、单项选择题(共 20 题...

noip2011初赛试题及答案(完美Word版)

noip2011初赛试题及答案(完美Word版)_英语考试_外语学习_教育专区。第十七届全国...输入:7 输出:___ 五、完善程序(第 1 题,每空 2 分,第 2 题,每空 3 ...

第十七届2011提高组初赛试题及答案C++版

第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高组●● C++语言 两小时完成...} NOIP2011 年提高组(C++语言)参考答案与评分标准一、单项选择题:(每题 1.5 ...

NOIP2011第十七届初赛Pascal普及组试题

NOIP2011第十七届初赛Pascal普及组试题_学科竞赛_初中教育_教育专区。第十七届全国...●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●●一、单项选择...

noip2011普及组初赛试题与答案

noip2011普及组初赛试题答案_学科竞赛_初中教育_教育专区。2011第十七届...2011第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 Pascal 语言 ...

第十七届2011全国青少年信息学奥林匹克联赛初赛试题(普...

第十七届2011全国青少年信息学奥林匹克联赛初赛试题(普及组C++)_学科竞赛_高中...NOIP2011 初赛 普及组 C++ 9 NOIP2011 年普及组(C++语言)参考答案与评分标准一...

NOIP2011 第十七届信息学奥林匹克联赛初赛提高组 C++试题

NOIP2011 第十七届信息学奥林匹克联赛初赛提高组 C++试题_IT/计算机_专业资料。NOIP2011 第十七届信息学奥林匹克联赛初赛提高组 C++试题今日...
更多相关标签:
noip普及组初赛试题 | noip试题 | noip初赛试题 | noip2011 | noip普及组试题精选 | noip提高组初赛试题 | noip2011普及组复赛 | noip2011提高组复赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com