NOIP 2010普及组初赛C/C++答案详解

以你之姓@ 2022-04-18 05:22 347阅读 0赞

# 一、单项选择题 #

1 D  
2E + 03 = 2 \* 103 = 2000  
2E - 03 = 2 \* 1 / (2 \* 103) = 2 \* 0.001 = 0.002

2 A  
常识题

3 A  
对于A选项，假设P为真，则结果必为真；假设P为假，则!p为真 ==> (!P & Q)和(!P & !Q)中必有一个为真 ==> P | (!P & Q) | (!P & !Q)为真。  
对于B选项，当P和Q同时为假时，Q | (!P & Q) | (P & !Q)为假。  
对于C选项，当P和Q同时为假时，整个表达式为假。  
对于D选项，当P为真Q为假时，整个表达式为假。

4 D  
exe是Windows下的可执行文件。exe是executable（可执行的）的缩写

COM是Component Object Model （组件对象模型）的缩写。COM是微软公司为了计算机工业的软件生产更加符合人类的行为方式开发的一种新的软件开发技术。在COM构架下，人们可以开发出各种各样的功能专一的组件，然后将它们按照需要组合起来，构成复杂的应用系统。

注意，这里的com不是域名（比如[www.google.com][]）中的com。若是有学生误以为是域名中的com而将B选项排除，只能说是碰巧排除对了。

DLL是Dynamic Link Library的缩写，意为动态链接库。在Windows中，许多应用程序并不是一个完整的可执行文件，它们被分割成一些相对独立的动态链接库，即DLL文件，放置于系统中。当我们执行某一个程序时，相应的DLL文件就会被调用。一个应用程序可有多个DLL文件，一个DLL文件也可能被几个应用程序所共用。

所以A, B, C选项都是Windows系统的文件，并且dll文件不能被独立执行。

那么Linux下的可执行文件后缀名是什么呢？答案是Linux/Unix/Mac系统下的程序的后缀名不重要，Linux/Unix/Mac系统下的文件功能不是以后缀名来划分的。这是Linux/Unix/Mac与Windows的一大重要差别。

5 A  
1层最多有21 \- 1 = 1个结点。  
2层最多有22 \- 1 = 3个结点。  
3层最多有23 \- 1 = 7个结点。

6 D  
识记题。  
美籍匈牙利数学家冯·诺依曼于1946年提出存储程序原理，把程序本身当作数据来对待，程序和该程序处理的数据用同样的方式储存。 冯·诺依曼体系结构冯·诺依曼理论的要点是：计算机的数制采用二进制；计算机应该按照程序顺序执行。人们把冯·诺依曼的这个理论称为冯·诺依曼体系结构。

7 B  
最低位，Y + X = X，则Y必为0  
最高位，X + Z = XY，则Z = 2, X = 1  
XY \* ZX = 10 \* 21 = 210 = ZXY

8 D  
PASCAL与C面向过程，C++面向对象。  
脚本语言又被称为扩建的语言，或者动态语言，是一种编程语言，用来控制软件应用程序，脚本通常以文本（如ASCII)保存，只在被调用时进行解释或编译。脚本语言有Shell, JavaScript, Perl, Python, PHP, Ruby等。  
解释型语言相对于编译型语言存在的，源代码不是直接翻译成机器语言，而是先翻译成中间代码，再由解释器对中间代码进行解释运行。比如Python/JavaScript / Perl /Shell等都是解释型语言。

9 C  
前缀表达式的计算机求值：  
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。  
本题中，先将12和5先后入栈；碰到+，将5和12依次弹出，计算5 + 12 = 17，将17入栈；将2入栈；碰到\*，将2和17依次弹出栈，计算2 \* 17 = 34，将34入栈；将3入栈；碰到+，将3和34依次弹出栈，计算3 + 34 = 37。

10 B  
CPU高速缓存（Cache Memory）是位于CPU与内存之间的临时存储器，它的容量比内存小的多但是交换速度却比内存要快得多。高速缓存的出现主要是为了解决CPU运算速度与内存读写速度不匹配的矛盾，因为CPU运算速度要比内存读写速度快很多，这样会使CPU花费很长时间等待数据到来或把数据写入内存。在缓存中的数据是内存中的一小部分，但这一小部分是短时间内CPU即将访问的，当CPU调用大量数据时，就可先缓存中调用，从而加快读取速度。

11 D  
正数的原码、反码、补码都一样。  
负数的补码为原码取反加1，原码为补码减1取反（注意最高位的1是符号位，不用取反）。

12 B  
对于n个待排序元素，在未比较时，可能的正确结果有n!种。  
在经过一次比较后，其中两个元素的顺序被确定，所以可能的正确结果剩余n!/2种（确定之前两个元素的前后位置的情况是相同，确定之后相当于少了一半的可能性）。  
次类推，直到经过m次比较，剩余可能性n!/(2^m)种。  
直到n!/(2^m)<=1时，结果只剩余一种。  
由n!/(2^m) <= 1  
得m >= log2(n!)  
= log2(n \* (n - 1) \* (n - 2) \* … \* 2 \* 1)  
= log2n + log2(n - 1) + log2(n - 2) + … + log22 + log21  
>= log2n + log2(n - 1) + log2(n - 2) + … + log2(n/2)  
>= log2(n/2) + log2(n/2) + log2(n/2) + … + log2(n/2)  
>= n/2\*log2(n/2)  
所以基于比较的排序的时间复杂度下界是O(nlog2n)

13 B  
这题可以举个特例n = 3。三位数的最小值为100，最大值为999。  
100 = 1100100，这是七位二进制。  
999 < 1024 = 210 = 10000000000(B), 1024是十一位二进制，则999是十位二进制。  
再看四个答案，5n = 15, n*log(10) = 8.x, 10*log(n) > 10, 10nlog(n) > 1000。所以选B。

14 B  
href是Hypertext Reference的缩写。意思是指定超链接目标的URL。

15 B  
R1在R2的下方，所以R2不可能是最后一个出栈的。

16 A

![1-16.png][]

A选项中，p->rlink->llink = p->rlink;表示RightNode的左指针指向了RightNode本身，错误。

17 A  
画出图即可知道答案。

![1-17.png][]

18 D  
拓补排序的思路：  
在有向图中选一个没有前驱的顶点并且输出；  
从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）  
重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。

有环图不能进行拓补排序，A错；拓补排序可能有好几个结果，B错；只要求第一个结点一定是入度为0的结点，C错。

19 C  
举个特例。比如k = 3时，3号结点的父结点是1号结点（也就是根结点）。  
1 = ⌊k/2⌋ = ⌊3/2⌋ 。

20 D  
NOIP又叫CCF NOIP，CCF即为NOIP的主办单位。CCF, China Computer Federation，中国计算机学会。

# 二、问题求解 #

1 答案：2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6  
分析：  
x为1，y为2，空格为3；第一次碰到yyxy后加入到词典里，编号为4；第一次碰到xx后加入到词典里，编号为5；第一次碰到xyx后加入到词典里，编号为6。

> 信息学学习、算法答疑请加微信307591841  
> 关注公众号请扫描二维码  
> ![qrcode\_for\_kidscode\_258.jpg][qrcode_for_kidscode_258.jpg]

[www.google.com]: http://www.google.com
[1-16.png]: /images/20220418/d3d70a192029484a891be6b76f5c1722.png
[1-17.png]: /images/20220418/64092ca06322491f8f83b751fd2894a7.png
[qrcode_for_kidscode_258.jpg]: /images/20220418/ee869174a41d457e94b2a44d037200cc.png