第十七届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
c 字符串数组怎么定义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个非负整数的数组]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。现在知道逆序对是啥了，就容易做了，数字这么少，穷举两个数只需C（2,8）=28次，到所有的逆序对，自己在草稿纸上开个数组，每到一个就在这个数下面加一，然后看哪个数在数组里等于3的就选它。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论