2015年第二十一届全国青少年信息学奥林匹克联赛初赛普及组C＋详细答案

题目和答案

https://wenku.baidu.com/view/76e5f672284ac850ad0242f3.html?from=search

题解

一、选择题

1 D

1MB = 1024KB = 1024 * 1024B

2 C

全球两大个人电脑处理器厂商：Intel和AMD。

奔腾、酷睿、赛扬都是Intel生产的处理器型号。

性能：赛扬（低端）

i3, i5, i7都是酷睿的系列。目前市场上主流使用的型号为酷睿i5和酷睿i7。

3 C

A是编译器的作用，B是数据库的作用，D是主板的作用。

4 A

5 A

存储器外含主存储器（内存）和辅助存储器（外存）。

外存主要是硬盘、移动硬盘、优盘、光盘。

内存里的数据断电会消失。

外存里的数据断电不会消失，但是外存老化、坏掉，里面的数据也会遭到破坏。

所以说“任何时候都不会丢失”，太绝对了。

6 D

十进制逢十进一，二进制逢二进一，八进制逢八进一，十六进制逢十六进一。

这题2016年也考了。

7 A

二进制的0.1等于十六进制的0.8，等于八进制的0.4，等于十进制的0.5。

这题2016年也考了。

8 B

9 B

10 A

FTP: File Transfer Protocol，文件传输协议。

11 D

MSN：Microsoft Service Network。是微软公司旗下的门户网站。

MSN Messenger是微软发布的一款即时通软件，也简称为MSN。十年前在国内白领用的多，现在国内很少人用。

P2P：Peer-to-peer networking, 其定义为：网络的参与者共享他们所拥有的一部分硬件资源（处理能力、存储能力、网络连接能力、打印机等），这些共享资源通过网络提供服务和内容，能被其它对等节点（Peer）直接访问而无需经过中间实体。在此网络中的参与者既是资源、服务和内容的提供者（Server），又是资源、服务和内容的获取者（Client）。

12 B

连通图指的是图中的任意两个结点都可以互相到达。

既连通，又是最小生成树，则有5条边。

13 A

链表只能从头结点开始按顺序访问，不能随机访问。

14 D

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

在实际应用中，线性表常以链表、栈、队列、字符串等形式使用。

数组与线性表的区别：

0）线性表相邻元素是逻辑上的连续，数组相邻元素是物理上的连续；

1）线性表的长度可以改变，但数组的长度是固定的；

2）线性表可以插入元素，数组不能插入元素；

3）线性表可以删除元素，数组无法删除元素，数组只能将指定元素赋为null，但各种元素依然存在；

4）线性表提供方法来搜索指定元素的位置，数组一般无该方法；

5）线性表提供方法来清空所有元素，但数组一般无该方法

数组的存储空间要求连续的内存；线性表不要求连续的内存，当然连续的内存也可以。选D。

15 B

栈的特点是后入先出。

a进栈，b进栈，此时栈顶元素为b。

b出栈。

c进栈，d进栈。此时栈中从底部往顶部依次有a,c,d三个元素。

d出栈。此时栈中有a和c两个元素，且栈顶元素是c。

16 D

16.png

A. 如图（1）所示，前序遍历为a-b-c-d，中序遍历为a-c-b-d

B. 如图（2）所示，前序遍历为a-b-c-d，中序遍历为c-b-d-a

C. 如图（3）所示，前序遍历为a-b-c，中序遍历为c-b-a

D. 如图（4）所示，前序遍历为a-b-c，中序遍历为a-b-c

17 B

17-1.png

图17-1所示的是一棵满二叉树，也叫完美二叉树。若其深度为k，则节点总数为2k- 1

17-2.png

图17-2所示的是一棵完全二叉树。若其深度为k，则2k-1- 1 k- 1。

完全二叉树除最下面那层外，其他层的节点都排满了。

最下面那层的节点没有排满，并且需要从左到右依次填充节点。

17-3.png

题目中，26- 1 = 63，所以完全二叉树高度为6层，因为最后两个节点没有排满，所以不是满二叉树。

18 A

txt表示text，文本文件。

AVI英文全称为Audio Video Interleaved，即音频视频交错格式。

MOV即QuickTime影片格式，它是Apple公司开发的一种音频、视频文件格式。

RMVB，英文全称为RealMedia Variable Bitrate，是RealNetworks公司开发的一种视频格式。

19 D

 T(n)

= T(n - 1) + n

= T(n - 2) + (n - 1) + n

= T(n - 3) + (n - 2) + (n - 1) + n

= T(1) + 2 + …… + (n - 2) + (n - 1) + n

= T(0) + 1 + 2 + …… + (n - 2) + (n - 1) + n

= 1 + n*(n + 1) / 2

= n2/ 2 + n / 2 + 1

最高阶是n2，所以时间复杂度为n2。

20 A

二、问题求解