NOIP2018普及组初赛题解

展开全文

第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*2⁷+0*2⁶+0*2⁵+1*2⁴+0*2³+1*2²+1*2¹+0*2⁰=150

3）二进制转八进制

方法为：3位二进制数按权展开相加得到1位八进制数。（注意事项，3位二进制转成八进制是从右到左开始转换，不足时补0）。

例如：10010110 = 010010110= 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. (k^h+1-1)/(k-1)

B. k^h-1

C. k^h

D. (k^h-1) / (k - 1)

解析：A

S=k⁰+k¹+k²+k³+k⁴+....+k^h-1+k^h

kS=k¹+k²+k³+k⁴+....+k^h-1+k^h+k^h+1=(S-1)+k^h+1

(k-1)S = k^h+1-1

S=（k^h+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个元素的集合的全部子集数为2¹⁰=1024，
又因为其中由7个元素组成的子集数为120。

则：

13. 10000以内，与10000互质的正整数有( )个。

A. 2000

B. 4000

C. 6000

D. 8000

解析：B

互质的意思，与10000没有公约数，也即不能被10000的质因子整除。

10000=10⁴=2⁴×5⁴，
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 分）

#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('%s\n', st);

return 0;

}

输入：QuanGuoLianSai

输出：RuanHuoMianTai

#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

#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

#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('%d\n', 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;

}

原文链接：https://blog.csdn.net/weixin_39104847/article/details/118998613