专栏首页海天一树NOIP 2010普及组初赛C/C++答案详解

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

一、单项选择题

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, nlog(10) = 8.x, 10log(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。

本文分享自微信公众号 - KidsCode少儿编程(gh_de7b45c40e8b)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 小朋友学C++(14):两数交换

    之前学C语言的时候,咱们直接在main函数中使用“异或”位运算符,很容易实现了两数交换。 本节课将在此基础上,把交换两个数的算法,封装到swap函数中。这样不管...

    海天一树
  • 二叉树的建立和遍历

    二叉树:每个结点的子结点个数不大于2的树,叫做二叉树。 根结点:最顶部的那个结点叫做根结点,根结点是所有子结点的共同祖先。比如上图中的“7”结点就是根结点。 子...

    海天一树
  • 洛谷P1002题解

    海天一树
  • 数据结构-二叉树遍历总结

    二叉树结构 二叉树是一种特殊的树,每个父结点最多只能用有两个子结点。 ? 在树中,按照结点的“继承”关系可以分为父结点和子结点; 按照结点的位置...

    chaibubble
  • 数据结构 键树查找法

    键树查找法 又称数字查找树(根节点子树>=2个),键树节点存储的不是某个关键字,而是组成关键字的单个符号。

    Debug客栈
  • 数据结构 第4讲 单链表

    链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

    rainchxy
  • ChannelPipeline源码分析

    AbstractChannelHandlerContext

    良辰美景TT
  • Java集合框架源码解析之LinkedHashMap

    叶应是叶
  • 大会 | CVPR VUHCS Workshop征稿啦,附带5项极具吸引力的比赛

    AI 科技评论按:CVPR 2018 将于 2018 年 06 月 18-22 日在美国盐湖城举办,除了主会议程,各式各样的 Workshop 也值得大家一探究...

    AI科技评论
  • WP无觅插件For SAE

    直接上传到SAE,提示wumii-related-posts.php的第182行,stream_set_timeout()函数被禁用~

    libo1106

扫码关注云+社区

领取腾讯云代金券