第24届全国青少年信息学奥林匹克联赛初赛
普及组C++语言试题
竞赛时间：2018 年 10 月 13 日 14:30~16:30
选手注意：
1、试题纸共有 7 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上的一律无效。
2、不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1. 以下哪一种设备属于输出设备:( )
A.扫描仪
B.键盘
C.鼠标
D.打印机
解析：D，其他三项都属于输入设备。
扩展：
输入设备（Input Device ）是把数据、指令及某些标志信息等输送到计算机中去。键盘、鼠标、摄像头、扫描仪、光笔、手写输入板、游戏杆、语音输入装置等都属于输入设备。
输出设备（Output Device）是把计算或处理的结果或中间结果以人能识别的各种形式,如数字、符号、字母等表示出来,因此输入输出设备起了人与机器之间进行联系的作用。常见的有显示器、打印机、绘图仪、影像输出系统、语音输出系统、磁记录设备等。
控制台打字机、光笔、显示器等既可作输入设备、也可作输出设备。
2. 下列四个不同进制的数中，与其它三项数值上不相等的是( )。
A. (269)16
B. (617)10
C. (1151)8
D. (1001101011)2
解析：D
A选项：2 * 16^2 + 6 * 16^1 + 9 * 16 ^0 = 617
C选项：1 * 8^3 + 1 * 8^2 + 5 * 8^1 + 1 * 8^0 = 617
D选项：1*2^9+1*2^6+1*2^5+1*2^3+1*2^1+1^0=621
扩展：
进制也就是进制位，对于接触过电脑的人来说应该都不陌生，我们常用的进制包括：二进制、八进制、十进制与十六进制，它们之间区别在于数运算时是逢几进一位。比如二进制是逢2进一位，十进制也就是我们常用的0-9是逢10进一位。
进制转换总结：
1）十进制转二进制
方法为：十进制数除2取余法，即十进制数除2，余数为权位上的数，得到的商值继续除2，依此步骤继续向下运算直到商为0为止。（除2取余倒序法）
2）二进制转十进制
方法为：把二进制数按权展开、相加即得十进制数。
例如：10010110 = 1*27+0*26+0*25+1*24+0*23+1*22+1*21+0*20=150
3）二进制转八进制
方法为：3位二进制数按权展开相加得到1位八进制数。（注意事项，3位二进制转成八进制是从右到左开始转换，不足时补0）。
例如：10010110 = 010 010 110 = 226
4）八进制转成二进制
方法为：八进制数通过除2取余法，得到二进制数，对每个八进制为3个二进制，不足时在最左边补零。
5）二进制转十六进制
方法为：与二进制转八进制方法近似，八进制是取三合一，十六进制是取四合一。（注意事项，4位二进制转成十六进制是从右到左开始转换，不足时补0）。
6）十六进制转二进制
方法为：十六进制数通过除2取余法，得到二进制数，对每个十六进制为4个二进制，不足时在最左边补零。
7）十进制转八进制或者十六进制有两种方法
第一：间接法—把十进制转成二进制，然后再由二进制转成八进制或者十六进制。
第二：直接法—把十进制转八进制或者十六进制按照除8或者16取余，直到商为0为止。
8）八进制或者十六进制转成十进制
方法为：把八进制、十六进制数按权展开、相加即得十进制数。
9）八进制与十六进制之间的转换有两种方法
第一种：他们之间的转换可以先转成二进制然后再相互转换。
第二种：他们之间的转换可以先转成十进制然后再相互转换。
3. 1MB等于( )。
A. 1000 字节
B. 1024 字节
C. 1000 X 1000字节
D. 1024 X 1024字节
解析：D
1TB等于1024GB；
1GB等于1024MB；
1MB等于1024KB；
1KB等于1024Byte(字节)；
1Byte等于8bit(位)；
4. 广域网的英文缩写是( )。
A. LAN
B. WAN (Wide Area Network)
C. MAN
D.LNA
解析：B
局域网（Local Area Network）英文缩写:LAN。通常只范围在几百米到几十千米的网络。
城域网(Metropolitan Area Network)简称MAN。是在一个城市范围内所建立的计算机通信网。
广域网（Wide Area Network）英文缩写:WAN。通常跨接很大范围如一个国家。
5. 中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。
A. 1983
B. 1984
C. 1985
D. 1986
解析：B
1984年邓小平指出：“计算机的普及要从娃娃做起。”中国计算机学会于1984年创办全国青少年计算机程序设计竞赛（简称：NOI），当年参加竞赛的有8000多人。竞赛旨在向中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀计算机人才。
6. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、字母键 A、字母键S、字母键 D、字母键 F 的顺序循环按键，即 CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第 81 个字符是字母 ( )。
A. A
B. S
C. D
D. A
解析：A
ASDFasdf八个字符一循环，81/8=10……1，所以是第一个字符。
7. 根节点深度为 0，一棵深度为 h 的满 k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有( )个结点。
A. (kh+1-1)/(k-1)
B. kh-1
C. k h
D. (kh-1) / (k – 1)
解析：A
S=k0+k1+k2+k3+k4+….+kh-1+kh
kS=k1+k2+k3+k4+….+kh-1+kh+kh+1=(S-1)+kh+1
(k-1)S = kh+1-1
S=（kh+1-1)/(k-1)
8. 以下排序算法中，不需要进行关键字比较操作的算法是( )。
A. 基数排序
B. 冒泡排序
C. 堆排序
D. 直接插入排序
解析：A
基数排序，属于“分配式排序”，又称“桶子法”或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些桶中，藉以达到排序的作用。
冒泡排序，它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
堆排序，是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
直接插入排序，基本思想是：当插入第i(i >= 1)时，前面的V[0]，V[1]，……，V[i-1]已经排好序。这时，用V[i]的排序码与V[i-1]，V[i-2]，…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。
9. 给定一个含 N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要 N – 1 次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整，⌊ ⌋表示向下取整)
A. ⌈3N / 2⌉ – 2
B. ⌊3N / 2⌋ – 2
C. 2N – 2
D. 2N – 4
解析：A
如果分别找最大值、最小值，则至少都需要N-1次操作。
同时找最大最小值，按照下面的优化算法：
初始值：
N为奇数，最大值、最小值的初始值都设为第一个元素。
N为偶数，将前两个元素比较，最大值初始值为大的元素，最小值初始值为小的元素。
枚举，每次两个元素（循环步长为2）
比较两个元素，分出大小。
大的元素与最大值比较，比最大值大则设为该元素。
小的元素与最小值比较，比最小值小则设为该元素。
循环结束，得到最大、最小值。
N为奇数时，比较次数为3*(N-1)/2 =(3N+1)/2 – 2
N为偶数时，比较次数为1 +3*(N-2)/2 = 3N/2 – 2
综合奇偶，显然答案为A。
10. 下面的故事与( )算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事:“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事:‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”
A. 枚举
B. 递归
C. 贪心
D. 分治
解析：B
枚举：把所有元素一个一个拿出来进行操作。
递归：自己调用自己。
贪心：总是做出在当前看来是最好的选择。
分治：将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
11. 由四个没有区别的点构成的简单无向连通图的个数是( )。
A. 6
B. 7
C. 8
D.9
解析：A
1) 四个区别的点，意味着以下的图形为相同形状。
用d=[1, 2, 2,1]表示对应点的度，则以上的图的d数组都是一样的。
2）而以下的图形则是不同的另外一个形状，其d=[1, 3, 1, 1]。
题目要求，实际就是找出不同的d数组的个数。
3）根据边数来分类判断：
小于3条边，不构成连通，排除掉。
3条边：d=[1, 2, 2, 1]和[1, 3,1,1]两种
4条边：d=[2,2,2,2]和[1,3,2,2]两种
5条边：d=[2,2,3,3]一种
6条边：d=[3,3,3,3]一种
一共6种不同的图形，答案是A。
12. 设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为T，则T / S的值为( )。
A. 5 / 32
B. 15 / 128
C. 1 / 8
D. 21 / 128
解析：B
因为含有10个元素的集合的全部子集数为210=1024，
又因为其中由7个元素组成的子集数为120。
则：
13. 10000以内，与10000互质的正整数有( )个。
A. 2000
B. 4000
C. 6000
D. 8000
解析：B
互质的意思，与10000没有公约数，也即不能被10000的质因子整除。
10000=104=24×54，
10000÷2=5000，10000以内有质因数2的数有5000个，
10000÷5=2000，10000以内有质因数5的数有2000个，
10000÷10=1000，同时有质因数2和5的数有1000个，
5000 +2000 – 1000 =6000，被2或5整除的数有6000个，
互质的数有：10000 – 6000 ＝ 4000个。
14. 为了统计一个非负整数的二进制形式中 1 的个数，代码如下:
int CountBit(int x)
{
int ret = 0;
while (x)
{
ret++;
___________;
}
return ret;
}
则空格内要填入的语句是( )。
A. x >>= 1
B. x &= x – 1
C. x |= x >> 1
D. x <<= 1
解析：B
x>>=1等价于x=x>>1
如果知道x = x&(x-1)是二进制从后往前去掉1个1的话，答案B自然知道。
如果不知道的话，就自己模拟一下吧，比如用一个数5=(101)2
A选项模拟，结果为3（101,10,1,0）
B选项模拟，结果为2（101,100,0）
C选项模拟，死循环
D选项模拟，死循环
15. 下图中所使用的数据结构是( )。
A. 哈希表
B. 栈
C. 队列
D. 二叉树
解析：B
先入后出，栈的性质
先入先出，队列
二、问题求解（共 2 题，每题 5 分，共计 10 分）
1. 甲乙丙丁四人在考虑周末要不要外出郊游。已知1如果周末下雨，并且乙不去，则甲一定不去；2如果乙去，则丁一定去；3如果丙去，则丁一定不去；4如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲_____ (去了/没去)(1 分)，乙_____(去了/没去)(1 分)，丁_____(去了/没去)(1 分)，周末______(下雨/ 没下雨)(2 分)。
解析：
首先，丙是要去的。
那么根据(4)可以得知丁、甲中一定有一个或两个去。
而又根据(3)可以得知丁不去，所以甲去。
又根据(2)，因为前面已经提到：丁不去。所以证明乙也不去。
最后根据(1)得知，周末一定不下雨，如果下雨，那么甲也不去，就和之前的矛盾了。
所以答案：
甲（去了） 乙（没去） 丁（没去） 周末（没下雨）
2. 从 1 到 2018 这 2018 个数中，共有_____个包含数字 8 的数。
解析：
包含数字 8 的数是指有某一位是“8”的数，例如“2018”与“188”。
100内：个位是8，十位是8：共:10+9=19
每1到100一百个数字里有19个，80到89是10个，在加上8、18、28到98的9个（因为80到89中的88算过了，所以要去掉一个）
2000里面有20个一百，再去掉800到899和1800到1899这两个整百，最后再加上2008和2018这两个，
综合列式是200+19×18+2=200+342+2=544一共有544个含8的数。
三、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）
1.
#include<cstdio>
char st[100];
int main() {
scanf(“%s”, st);
for (int i = 0; st[i]; ++i) {
if (‘A’ <= st[i] && st[i]<= ‘Z’)
st[i] += 1;
}
printf(“%sn”, st);
return 0;
}
输入：QuanGuoLianSai
输出：RuanHuoMianTai
2.
#include<cstdio>
int main() {
int x;
scanf(“%d”, &x);
int res = 0;
for (int i = 0; i < x; ++i) {
if (i * i % x == 1) {
++res;
}
}
printf(“%d”, res);
return 0;
}
输入：15
输出：4
3.
#include<iostream>
using namespace std;
int n, m;
int findans(int n, int m) {
if (n == 0) return m;
if (m == 0) return n % 3;
return findans(n – 1, m) – findans(n, m – 1) +findans(n – 1, m – 1);
}
int main(){
cin >> n >> m;
cout << findans(n, m) << endl;
return 0;
}
输入：5 6
输出：8
4.
#include<cstdio>
int n, d[100];
bool v[100];
int main() {
scanf(“%d”, &n);
for (int i = 0; i < n; ++i) {
scanf(“%d”, d + i);
v[i] = false;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!v[i]) {
for (int j = i; !v[j]; j = d[j]) {
v[j] = true;
}
++cnt;
}
}
printf(“%dn”, cnt);
return 0;
}
输入：10 7 1 4 3 2 5 9 8 0 6
输出：6
四、完善程序（共 2 题，每题 14 分，共计 28 分）
1. （最大公约数之和）下列程序想要求解整数
举例来说，4的所有约数是1,2,4。1和2的最大公约数为1；2和4的最大公约数为2；1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。
要求 getDivisor 函数的复杂度为0(√n)，gcd 函数的复杂度为O(log max(a, b))。
#include<iostream>
using namespace std;
const int N =110000, P = 10007;
int n;
int a[N], len;
int ans;
//计算出所有公约数，并存储在a数组中
void getDivisor(){
len = 0;
for(int i=1; i * i <=n;++i)
if (n % i == 0) {
a[++len] = i;
if( n / i !=i)a[++len]=n/i;
}
}
//求两个数的最大公约数
int gcd(int a,int b) {
if (b == 0) {
return a ;
}
return gcd(b, a % b );
}
int main() {
cin >> n;
getDivisor();
ans = 0;
for (int i = 1; i <= len; ++i) {
for (int j = i + 1; j <= len; ++j) {
ans=( ans + gcd(a[i], a[j]) )%P;
}
}
cout << ans << endl;
return 0;
}
2. 对于一个1到n的排列p(即1到n中每一个数在p中出现了恰好一次)，令qi为第i个位置之后第一个比pi值更大的位置，如果不存在这样的位置，则qi =n+1。
举例来说，如果n=5且p为1 5 4 2 3，则q为2 6 6 5 6。
下列程序读入了排列p，使用双向链表求解了答案。试补全程序。（第二空2分，其余3分）
数据范围 1 ≤ n ≤ 105。
#include<iostream>
using namespace std;
const int N =100010;
int n;
int L[N], R[N],a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
a[x] = i ;
}
for (int i = 1; i <= n; ++i) {
R[i]= i + 1 ;
L[i] = i – 1;
}
for (int i = 1; i <= n; ++i) {
L[ R[a[i]] ]= L[a[i]];
R[L[a[i]]] = R[ a[i] ];
}
for (int i = 1; i <= n; ++i) {
cout << R[i] <<” “;
}
cout << endl;
return 0;
}
转自公众号：
信息学少儿编程