最新消息:网站支持在线创作,微信分享,请点击【创作中心】编辑作品。

备考 | 2018NOIP普及组初赛真题及详细参考答案

C++ 少儿编程 124浏览 0评论

第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。

则:

备考 | 2018NOIP普及组初赛真题及详细参考答案

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. 下图中所使用的数据结构是( )。

备考 | 2018NOIP普及组初赛真题及详细参考答案

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;

}

转自公众号:
信息学少儿编程

您必须 登录 才能发表评论!