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

一、单项选择题

1 D第一台电子计算机是在第二次世界大战后不久制成的,那时,随着火炮的发展,弹道计算日益复杂,原有的一些计算机已不能满足使用要求,迫切需要有一种新的快速的计算工具。这样,在一些科学家、工程师的努力下,在当时电子技术已显示出具有记数、计算、传输、存储控制等功能的基础上,电子计算机就应运而生了。世界上第一台电子计算机命名为"埃尼阿克",是1946年美国宾夕法尼亚大学埃克特等人研制成功的。

2 BRAM不是位置随机,而是随时访问。所谓“随机存储”,指的是“当存储器中的消息被读取或写入时,所需要的时间与这段信息所在的位置无关”。A错。高速缓冲区是CPU自带的,CPU的一二三级缓存就是高速缓存。与高速缓存相比,内存条只是下一级的低速缓存。寄存器是CPU的一部分。C错。内存中的数据,断电会立马消失。D错。

3 ABIOS是英文"Basic Input Output System"的缩略词,直译过来后中文名称就是"基本输入输出系统"。在IBM PC兼容系统上,是一种业界标准的固件接口。 BIOS是个人电脑启动时加载的第一个软件,它是一组固化到计算机内主板上一个ROM芯片上的程序,它保存着计算机最重要的基本输入输出的程序、开机后自检程序和系统自启动程序。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。BIOS是由主板厂商开发的,不是由操作系统厂商(如微软)开发的。

4 A汇编语言只有人能看的懂,CPU是看不懂的,需要用软件将汇编转换成机器语言,CPU才能执行程序。B错。位数只能说明处理的字长,所在的系统硬件指令不同,速度很难说谁快。C错。Intel最早发明的是微处理器,而CPU之前就由电子管、晶体管实现着呢。D错。

5 BASCII(American Standard Code for Information Interchange,美国信息交换标准代码)是基于拉丁字母的一套电脑编码系统,主要用于显示现代英语和其他西欧语言。它是现今最通用的单字节编码系。

6 D WPS是类似微软Office的国产文字处理软件,由金山公司出品。

7 CIPv6是Internet Protocol Version 6的缩写,其中Internet Protocol译为“互联网协议”。IPv6是IETF(互联网工程任务组,Internet Engineering Task Force)设计的用于替代现行版本IP协议(IPv4)的下一代IP协议,号称可以为全世界的每一粒沙子编上一个网址。A错。域名都需要绑定在IP上,域名比IP更好记,比如www.baidu.com为域名,IP都是数字。B错。考虑版权。D错。

8 B HTML全称HyperText Markup Language,即超文本标记语言,关于HTML是不是一门编程语言,业界仍有不小的争议。有人认为,HTML和其他标记语言(比如XML)一样具备了语言特征,可以被应用程序(比如浏览器)解释,但不具备高级程序设计语言的特征。另外Flash动画一般由Adobe公司的Flash软件开发,Flash游戏由ActionScript语言开发。

9 C释在程序代码中不会被执行,也不会被编译,因此注释不会影响程序的运行速度。A错。只要硬件系统具备运行环境,高级语言开发的程序能够在这些硬件系统上运行。比如C++,Java作为高级语言,已经广泛用于手机,机顶盒,打印机。B错。高级语言在编写程序时不用考虑最后程序会运行在那类操作系统上,因为很容易跨平台移植。C对。

10 D正确答案是74。

11 C1758 = 1 * 82 + 7 * 8 + 5 = 1250.18 = 1/8 = 0.125所以,175.18 = 125.125

12 CA选项:F进栈 -- E进栈 -- E出栈 -- D进栈 -- D出栈 -- C进栈 -- C出栈 -- F出栈 -- B进栈-- A进栈 -- A出栈 -- B出栈B选项:F进栈 -- E进栈 -- D进栈 -- D出栈 -- E出栈 -- C进栈 -- C出栈 -- B进栈 -- A进栈 -- A出栈 -- B出栈 -- F出栈C选项:F进栈 -- E进栈 -- D进栈 -- C进栈 -- C出栈 -- D出栈 -- ??,这里E一定会比F早出栈,所以本选项错误。D选项:F进栈 -- E进栈 -- D进栈 -- C进栈 -- B进栈 -- B出栈 -- C出栈 -- D出栈 -- A进栈 -- A出栈 -- E出栈 -- F出栈

13 B中缀表达式转换为后缀表达式的过程需要用到栈,具体过程如下:1)如果遇到操作数,我们就直接将其输出。2)如果遇到操作符,则我们将其放入到栈中,遇到左括号时我们也将其放入栈中。3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号,左括号也弹出但不输出。4)如果遇到任何其他的操作符,如“+”, “*”,“(”等,从栈中弹出元素直到遇到发现栈中更低优先级的元素或者栈为空为止。弹出完这些元素后,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到" ) "的情况下我们才弹出" ( ",其他情况我们都不会弹出" ( "。5)如果我们读到了输入的末尾,则将栈中所有元素依次弹出。

对于本题的例子:1)第一个是操作数“a”,直接输出2)接下来,操作符入栈,左括号入栈,输出“b”,“+”入栈,输出“c”。如图1所示 3)碰到右括号,将“+”弹出栈并输出,接着将左括号弹出但不输出,“”不弹出仍在栈里,如图2所示

1-13.png

4)碰到“-”,因为栈里“”的优先级比“-”要高,所以“”出栈并输出,“-”入栈,如图3所示5)碰到最后一个字符“d”,直接输出,并把栈中的元素“-”弹出并输出。如图4所示

14 D二叉树的结点有两种:叶子节点和非叶结点(也叫分支结点)。当二叉树为完美二叉树时,叶子结点最多。以下图为例,分支结点(非叶结点)有7个,叶子结点有8个。所以是n+1。

1-14.png

15 D在最坏的情况下,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,它就是一棵斜树。此时需要执行n‐1次递归调用,且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录,也就是枢轴的位置,因此比较次数为

1-15.jpg

最终其时间复杂度为O(n2)。

16 Blog4000 < log4096 = 12

17 D快速排序的具体做法:设置需要排序序列第一个数字为关键字P(也叫枢轴),同时设置两个指针high和low,初始状态时,low指向P,high指向序列中最后一个数;首先从high所指位置起向前找第一个小于关键字P的数字,并与P相互交换位置;然后从low所指位置起向后搜索,找到第一个大于P的数字,并与P相互交换位置,重复这两部直至low=high为止,这就是一趟快速排序完成;但是到此不一定就完成了快速排序的排序工作,第一趟排序完成只是将序列中的数字分成三部分,P在中间部分,P之前的数字肯定比P小,P后面的那些数字都是比P大的,在分别对前后两部分进行快速排序即可。排序的稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。比如:对{49,38,49,20,97,76} 进行快速排序,第一轮比较是20和第一个49互换位置,导致第一个49跑到第二个49后面,所以这是不稳定的排序。

18 A

1-18.png

有向图至少需要n条有向边,无向图至少需要n - 1条无向边。

19 C

20 B赛场纪律http://www.noi.cn/newsview.html?id=68&hash=CDD941&type=6

选手可以携带书写工具,如钢笔、铅笔等,以及手表和适量的衣物等进入赛场。有特殊情况需要携带其它物品者需事先取得竞赛委员会的批准。选手不可以携带上述规定之外的其它物品,如纸张、书籍、食品、饮料等进入赛场。选手被严格禁止携带软盘、光盘、U盘等存储设备和介质,以及手机、电子辞典、PDA等电子及通信设备。凡携带上述被严格禁止的设备进入竞赛场地者,在竞赛开始后一经发现,无论是否使用,均以作弊论处,取消其该场竞赛的资格和成绩。选手在竞赛中不得与其他选手交谈,不得干扰他人的竞赛活动,不得损坏竞赛设备。选手在竞赛过程中如需入厕,需举手向赛场服务人员示意并征得允许。

二、问题求解

1 答案:70分析:b1, a1, a2, a3的相对位置是固定的。尤其是b1,一定是放在第一个位置。

2-1.png

这里的问号,可以填b2,b3,b4,b5中的一个或多个,也可以为空。(一)枚举法枚举法过于复杂,不能使用枚举法,否则容易出错。(二)求组合B任务中的b1一定做,而且肯定是第一个做的。所以b1就不用考虑了。第一类:完成A任务,只有1种。即a1 a2 a3第二类:完成A任务和b2,有C(4,1)=4种:① b2 a1 a2 a3② a1 b2 a2 a3③ a1 a2 b2 a3④ a1 a2 a3 b1第三类:完成A任务和b2、b3,有C(5,2)=10种。这里C(5, 2)表示从五个位置中挑选出2个且顺序已经定好:第一个位置放b2,第二个位置放b3。其他三个位置不用选,肯定按从左到右的顺序放a1,a2和a3。第四类:完成A任务和b2、b3、b4,有C(6,3)=20种。第五类:完成A任务和b2、b3、b4、b,有C(7,4)=35种。加起来1+4+10+20+35=70。

原文发布于微信公众号 - KidsCode少儿编程(gh_de7b45c40e8b)

原文发表时间:2018-11-24

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

在美国国会图书馆标题表的SKOS上运行Apache Spark GraphX算法

这是Bob DuCharme的一篇客串文章。

47070
来自专栏ImportSource

设计模式的那些事儿-(概要)

相信你看了很多关于设计模式的书籍或文章。里边一定会有咖啡果汁之类或者画圆或矩形的例子,或者其他的我们平时就无法一下子用到的具体场景。 ...

36670
来自专栏余林丰

访问者模式

这是23种设计模式的最后一个——访问者模式,这个模式确实不怎么好理解,不怎么好用,而且实际中也很少用到这个设计模式。《大话设计模式》中就提到GoF四个人中有一个...

22350
来自专栏乐享123

再谈以太网帧格式

13920
来自专栏喔家ArchiSelf

一行Python代码

自从08年接触Python,就有爱不释手的感觉,逐渐地,有些不忍地疏远了Perl 和Shell编程,因为python 的优雅么? 不全是,主要是可以高效开发吧。

29040
来自专栏数据结构与算法

473. 核电站问题

★   输入文件:nucle.in   输出文件:nucle.out   简单对比 时间限制:1 s   内存限制:128 MB 【问题描述】     一个核...

469130
来自专栏web前端教室

javascript ES6 初次相见

JS的ES6网上也热炒了好久了, 我一直也没怎么太细看, 今天想起来就写个东西, 也为分享,也为学习。 我喜欢接地气一点,所以网上的那些新名词我就不写了, 就写...

19870
来自专栏编程一生

谈面试时从写一个单例开始究竟能问多深及终极解决方案

15140
来自专栏计算机视觉与深度学习基础

模拟猜单词游戏

模拟实现猜单词游戏,纯模拟,不涉及图形界面,注释很详细,虽然本人代码写得丑,但是希望可以给大家提供帮助 #include<algorithm> #include...

216100
来自专栏java工会

一分钟搞明白java8中的lambda|文末红包

23750

扫码关注云+社区

领取腾讯云代金券