2015第二十二届全国青少年信息学奥林匹克联赛初赛
第二十一届全国青少年信息学奥林匹克联赛初赛
普及组 C++语言试题
竞赛时间： 2015 年 10 月 11 日 14:30-16:30
一、单项选择题(共 20 题)
包括以下题目及正确答案：
题号 1 答案 D
题号 2 答案 C
题号 3 答案 C
题号 4 答案 A
题号 5 答案 A
题号 6 答案 D
题号 7 答案 A
题号 8 答案 B
题号 9 答案 B
题号 10 答案 A
二、问题求解(共两题)
第一题：重新排列数字使得每个数字不在原来的位置上有9种排法。
第二题：一棵结点数为2015的二叉树最多有1008个叶子结点。
三、阅读程序写结果(共四小题)
第一题输出3；第二题输出3,2；第三题输出"It has 18 lowercases"；第四题输出Ab。
四、完善程序(共两小问)
第二十一届全国青少年信息学奥林匹克联赛初赛
普及组 C++语言试题
竞赛时间： 2015 年 10 月 11 日 14:30-16:30
一、单项选择题(共 20 题，每题 1.5 分，共计 30分；每题有且仅有一个正确选项) ⒈ 1MB 等于( )。
A.10000 字节 B.1024 字节 C.1000×1000 字节 D.1024×1024 字节
⒉在 PC 机中， PENTIUM(奔腾)、酷睿、赛扬等 是指( )。
A.生产厂家名称 B.硬盘的型号 C.CPU 的型号 D.显示器的型号
⒊操作系统的作用是( )。
将源代码转换为目标代码
A.二进制码 B.八进制码 C.十进制码 D.智能拼音码
⒌下列说法正确的是( )。
A.CPU 的主要任务是执行数据运算和程序控制
B.存储器具有记忆能力，其中信息任何时候都不会丢失
C.两个显示器屏幕尺寸相同，则它们的分辨率必定相同
D.个人用户只能使用Wifi 的方式连接到 Internet
⒍二进制数 00100100 和 00010100 的和是( )。
A.00101000 B.01100111 C.01000100 D.00111000
⒎与二进制小数 0.1 相等的十六进制数是( )。
A.0.8 B.0.4 C.0.2 D.0.1
⒏所谓的“中断”是指( )。
A.操作系统随意停止一个程序的运行
在遇到需求时, CPU 在处理现有任务时暂停运行, 并开始处理新的状况
C.因停机而停止一个程序的运行 D.电脑死机
⒐计算机病毒是( )。
A.通过计算机传播的危害人体健康的一种病毒
B. 故意生成具备入侵能力的行为序列，在能够能够在计算机系统内运行并引发故障
C.一种由于计算机元器件老化而产生的对生态环境有害的物质
D. 基于计算机的强大运算能力开发出一种用于疾病预防的新病毒
⒑ FTP 可以用于( )。
A.远程传输文件 B.发送电子邮件 C.浏览网页 D.网上聊天
⒒下面哪种软件不属于即时通信软件( )。
A.QQ B.MSN C.微信 D.P2P
⒓ 6 个顶点的连通图的最小生成树，其边数为( )。
A.6 B.5 C.7 D.4
⒔链表不具备的特点是( )。
A.可随机访问任何一个元素 B.插入、 删除操作不需要移动元素
C.无需事物估计存储空间大小 D.所需存储空间与存储元素个数成正比
⒕线性表若采用链表存储结构，要求内存中可用存储单元地址( )。
A.必须连续 B.部分地址必须连续 C.一定不连续 D.连续不连续均可
现有一个空栈S按照顺序依次对数据元素a,b,c,d,e,f执行入栈操作
A.f B.c C.a D.b
⒗前序遍历序列与中序遍历序列相同的二叉树为( )。
A.根结点无左子树 B.根结点无右子树
C.只有根结点的二叉树或非叶子结点只有左子树的二叉树
D.只有根结点的二叉树或非叶子结点只有右子树的二叉树
⒘如果根的高度为 1,具有 61 个结点的完全二叉树的高度为( )。
A.5 B.6 C.7 D.8
⒙下列选项中不属于视频文件格式的是( )。
A.TXT B.AVI C.MOV D.RMVB
假设某个算法的计算时间由递推关系式T(n) = T(n-1) + n（其中n为正整数）以及T(0) = 1给出，则该算法的时间复杂度是（）。
A.O (logn) B.O (nlogn) C.O (n) D.O (n2)
在NOI系列赛事中参赛者必须由主办方统一提供的设备。请选出以下物品中哪些是选手不得自带的（）。
A.鼠标 B.笔 C.身份证 D.准考证
二、问题求解（共 2 题，每题 5 分，共计 10 分；每题全部答对得5分）
⒈请重新排列为1234的一种形式，并满足每个数字都不在原位上的要求。共有 __ 种不同的排法能够达到这一目标。
⒉一棵拥有2015个结点的二叉树最多能够拥有 __ 个叶子结点。
三、阅读程序写结果(共 4 题，每题 8 分，共计 32分)
⒈
#include
using namespace std;
int main()
第 2 页 ， 共 7 页
{ int a, a = 1;
b = 2; c = 3; if(a > if(a
b, c;
b)
c)
cout << a << ' ';
else
cout << b << ' ';
cout << c << endl;
return 0;
}
输出： __
⒉
#include
using namespace std;
struct point
{
int x;
int y;
};
int main()
{
int a, b, c;
struct EX
{
int a;
int b;
point c;
}e;
第 3 页 ， 共 7 页
e.a = 1;
e.b = 2;
e.c.x = e.a + e.b;
e.c.y = e.a * e.b;
cout << e.c.x << ',' << e.c.y << endl;
return 0;
}
输出： __
⒊
#include
#include
using namespace std;
int main()
{
string str;
int i;
| int count; count = 0; getline(cin, for(i = 0; i | str); < str.length(); |
|---|
if(str[i] >= 'a' && str[i]
i++)
<= 'z')
count++;
cout << "It has " << count << " lowercases" << endl;
return 0;
}
输入： NOI2016 will be held in Mian Yang.
输出：
⒋
#include
#include
第 4 页 ， 共 7 页
using namespace std;
void fun(char *a, char *b)
{
a = b;
(*a)++;
}
int main()
{
char c1, c2, *p1, *p2;
c1 = 'A';
c2 = 'a';
p1 = &c1;
p2 = &c2;
fun(p1, p2);
cout << c1 << c2 << endl;
return 0;
}
输出： __
四、完善程序(共 2 题，每题 14 分，共计 28分)
输出月份日历
例如，2015 年 1 月的月历打印效果如下(第一列为周日)：
S M T W
4 5 6 7
11 12 13 14
18 19 20 21
T 1 8 15
22
F 2 9 16
23
S
3
10
17
24
25 26 27 28 29 30 31
#include
#include
using namespace std;
const int dayNum[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int m, offset, i;
int main()
{
cin >> m;
cout << "S\tM\tT\tW\tT\tF\tS" << endl; //'\t'为 TAB 制表符
⑴ __ ;
for(i = 1; i < m; i++)
offset =__⑵ __ ;
for(i = 0; i < offset; i++)
cout << '\t';
for(i = 1; i <=__⑶ __ ; i++)
{
cout <<__⑷ __ ;
if(i == dayNum[m] ||__⑸ __ == 0)
cout << endl;
else
cout << '\t';
}
return 0;
}
⒉ (中位数 median)给定 n(n 为奇数且小于 1000)个整数， 整数的范围在 0~m(0<m<2^31)之间， 请使
改写说明
#include
using namespace std;
const int MAXN = 1000;
int n, i, lbound, rbound, mid, m, count;
int x[MAXN];
第 6 页 ， 共 7 页
int main()
{
cin >> n >> m;
for(i = 0; i < n; i++)
cin >> x[i];
lbound = 0;
rbound = m;
while(__⑴ __)
{
mid = (lbound + rbound) / 2;
⑵ __ ;
for(i = 0; i < n; i++)
if(__⑶ __)
⑷ __ ;
if(count > n / 2)
lbound = mid + 1;
else
⑸ __ ;
cout << mid << " " << lbound << " " << rbound << " " << count << endl; }
cout << rbound << endl;
return 0;
}
第21届国家级少儿计算机学科奥林匹克联赛初赛 C++语言试题参考答案
一、单项选择题(共 20题，每题1.5 分，共计 30分；每题有且仅有一个正确选项)
⒈ D ⒉C ⒊C ⒋A ⒌A ⒍D ⒎A ⒏B ⒐B ⒑A ⒒D ⒓B ⒔A ⒕D ⒖B ⒗D ⒘B ⒙A
⒚D ⒛A
二、问题求解(共 2题，每题 5分，共计 10分；每题全部答对得 5 分，没有部分分) ⒈ 9 ⒉1008
三、阅读程序写结果(共 4题，每题8分，共计 32分)
⒈ 3 ⒉3,2 ⒊It has 18 lowercases ⒋Ab
四、完善程序(共 2题，每题 14分，共计 28 分) ⒈(第三、四空 2.5 分，其余 3 分)
⑴ offset = 4 ⑵(offset + dayNum[i]) % 7
⒉(第五空 2 分，其余 3 分)
⑴ lbound <= rbound) ⑵count = 0 ⑶x[i]
⑶dayNum[m] ⑷i ⑸(offset + i) % 7
= mid) ⑷count++ ⑸rbound = mid - 1