首页
学习
活动
专区
工具
TVP
发布

2017年第二十三届NOIP普及组初赛试题及详细答案

竞赛时间: 2017 年 10月14日 14:30~ 16:30

选手注意:不得使用任何电子设备(如计算器、手机、电子词典等 )或查阅任何书籍资料

一、单项选择题(共20题,每题1.5分,共计30分;每题有且仅有一个正确选项)

2.计算机存储数据的基本单位是( )

A. bit B. Byte C. GB D. KB

3.下列协议中与电子邮件无关的是( )

A. POP3 B. SMTP C WTO D IMAP

4.分辨率为800*600、16位色的位图,存储图像信息所需的空间为( )

A. 937.5KB B. 4218.75KB C. 4320KB D. 2880KB

5.计算机应用的最早领域是( )

A. 数值计算 B. 人工智能 C. 机器人 D. 过程控制

6.下列不属于面向对象程序设计语言的是( )

A. C B. C++ C. Java D. C#

7.NOI的中文意思是( )

A. 中国信息学联赛 B. 全国青少年信息学奥林匹克竞赛

C. 中国青少年信息学奥林匹克竞赛 D. 中国计算机学会

8.2017年10月1日是星期日,1999年10月1日是( )

A. 星期三 B.星期日 C. 星期五 D.星期二

9.甲、乙、丙三位同学选修课程,从4门课程中,甲选修2门,乙、丙各选修3门,则不同的选修方案共有( )

A. 36 B. 48 C. 96 D. 192

10.设G是有n个结点、m条边(n≤m)的连接图,必须删去G的( )条边,才能使得G变成一棵树。

A. m-n+1 B. m-n C. m+n+1 D. n-m+1

11.对于给定的序列{ak},我们把(i , j)称为逆序对当且仅当 iaj .那么序列1,7,2,3,5,4的逆序对数为( )个

A. 4 B. 5 C. 6 D. 7

12.表达式的后缀形式是( )

A.

B.

C.

D.

13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时,应执行( )

A. hs->next =s ;

B. s->next=hs; hs=s ;

C. s->next=hs->next;hs->next=s;

D. s->next=hs; hs=hs->next;

14.若串S=“copyright”,其子串的个数是( )

A. 72 B. 45 C. 46 D. 36

15.十进制小数13.375对应的二进制数是( )

A. 1101.011 B. 10111.011 C. 1101.101 D. 1010.01

16.对于入栈顺序为a,b,c,d,e,f,g的序列,下列( )不可能是合法的出栈序列

A. a,b,c,d,e,f,g B. a,d,c,b,e,g,f C. a,d,b,c,g,f,e D. g,f,e,d,c,b,a

17.设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,任何以元素比较作为基本运算的归并算法在最坏情况下至少要做( )次比较

A. n2 B. n log n C. 2n D. 2n-1

18.从( )年开始,NOIP竞赛将不再支持Pascal语言

A. 2020 B. 2021 C. 2022 D. 2023

19.一家四口人,至少两个人生日属于同一月份的概率是( )

(假定每个人生日属于每个月份的概率相同且不同人之间相互独立)

A. 1/12 B. 1/144 C. 41/96 D. 3/4

20.以下和计算机领域密切相关的奖项是( )

A. 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 普利策奖

二、问题求解(共2题,每题5分,共计10分)

1.一个人站在坐标(0,0)处,面朝x轴正方向。第一轮,他向前走1单位距离,然后右转;第二轮,他向前走2单位距离,然后右转;第三轮,他向前走3单位 距离,然后右转……他一直这么走下去。请问第2017轮后,他的坐标是:(,_)。(请在答题纸上用逗号隔开两空答案)

1.png

2.如右图所示,共有13个格子。对任何一个格子进行一次操作,会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0,或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要_次操作。

三、阅读程序写结果(共4题,每题8分,共计32分)

1.

输入: xyzxyw

输出:_.

2.

输入: 7 3

输出:__.

3.

输入: 1001101011001101101011110001

输出:________________.

4.

输入1: 4 3

输出1:_____(3分)

输入2:2017 1014

输出 2:____(5分)

四、完善程序 (共2题,每题14分,共计28分)

1.(快速幂)请完善下面的程序,该程序使用分治法求 xp mod m的值。(第一空2分,其余3分)

输入:三个不超过 10000的正整数 x, p, m .

输出:x^p mod m的值。

提示:若p为偶数,x ^ p=(x ^ 2) ^ p/2 ; 若p为奇数,x ^ p=x*(x ^ 2) ^ ( p - 1)/2 .

2.(切割绳子) 有n条绳子,每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割,但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段,求绳段的最大长度是多少。(第一、二空2.5分,其余3分)

输入:第一行是一个不超过100的正整数n,第二行是n个不超过10 ^ 6的正整数,表示每条绳子的长度,第三行是一个不超过10 ^ 8的正整数m。

输出 :绳段的最大长度,若无法切割,输出Failed.

参考答案

一、单项选择题

1 B

原码、反码、补码请参考 https://www.jianshu.com/p/b53fe5765884

正数的原码与反码、补码相同。

负数的反码为原码取反,最高位符号位不变;负数的补码为原码取反加1,最高位符号位不变。

2 B

3 C

POP3: Post Office Protocol - Version 3,邮局协议3

SMTP: Simple Mail Transfer Protocol,简单邮件传输协议

WTO: World Trade Organization,世界贸易组织

IMAP: Internet Mail Access Protocol,因特网邮件访问协议

4 A

8 bit = 1 B

1024 B = 1KB

800 * 600 * 16 / (8 * 1024) = 937.5kB

5 A

美国最早用于计算弹道和射击路线,即数值分析

6 A

C语言是面向过程的语言

7 B

NOI: National Olypiad in Infomatics,全国青少年信息学奥林匹克竞赛

NOIP: National Olypiad in Infomatics in Provices,全国青少年信息学奥林匹克联赛

8 C

非闰年,X年10月1日到X+1年10月1日,经过365天。365 % 7 = 1,在星期上相当于过了一天。

闰年一年366天,366 % 7 = 2,在星期上相当于过了二天。

判断闰年有两个条件:能被400整除;或能被4整除且不能被100整除。

1999年10月1日~2017年10月1日,这18年里有13个非闰年5个闰年(2000,2004,2008,2012,2016),相当于经过13 + 5 * 2 = 23天,23 % 7 = 2,相当于经过了天。

星期日 - 2 = 星期五。

9 C

求组合数:C(4, 2) * C(4, 3) * C(4, 3) = 6 * 4 * 4 = 96

10 A

a-1.jpg

树的节点数 = 边数 + 1,比如上图中节点10个,边有9条。

题目中,图要变成树,只能保留n - 1条边。m - (n - 1) = m - n + 1

11 B

7 2, 7 3, 7 5, 7 4, 5 4。共五对。

12 B

考察二叉树数据结构,可参考 https://www.jianshu.com/p/c95ea81b726d

a-2.png

如果没有指明是前缀(前序)、中缀(中序)还是后缀(后序),那么默认指的是中序遍历。

上图二叉树中,

中序遍历为

后序遍历为

前序遍历为

13 B

考察栈的数据结构,可参考 https://www.jianshu.com/p/f9e4961bf145

新元素入栈后,要把栈顶指针指到新元素的位置。

14 C

长度为9的子串有9-9+1=1个,即S本身。

长度为8的子串有9-8+1=2个,即"copyrigh"和"opyright"。

长度为7的子串有9-7+1=3个,即"copyrig", "opyrigh"和"pyright"

……

长度为1的子串有9-1+1=9个,即"c", "o", "p", "y", "r", "i", "g", "h", "t"

长度为0的子串有1个,即空串""

公式cnt = len * (len + 1) / 2 + 1

15 A

整数部分,1101 = 2^3 + 2^2 + 2^0 = 13,排除BD

小数部分,小数十进制转二进制,就是小数部分不断乘以2直到小数完全消失,计算过程中每次取整数部分作为二进制值。

0.375 * 2 = 0.75 ,取整数部分0

0.75 * 2 = 1.5,取整数部分1,其小数部分0.5参与下次计算

0.5 * 2 = 1,取整数部分1

所以小数部分为011

16 C

A中,每次进栈一个字母,然后该字母立马出栈

B中,先入栈a,弹出a;再入栈bcd,弹出dcb;第三次入栈e,弹出e;最后入栈fg,弹出gf

C中,无论怎样入栈,都不会有db的出栈顺序

D中,把所有字母进栈,再把所有字母出栈

17 D

考察归并排序,可参考 https://www.jianshu.com/p/5b08c571762d

设A中的元素为a1, a2, a3; B中的元素为b1, b2, b3; 依题意有a1

比较的代码为

这段代码是每比较一次,就把一个元素放到tmpArr中。

(1)比较最多的情况,比如tmpArr = ,或者tempArr = ,或者tmpArr = ,或者之类的。

注意最后一个元素肯定放在最后,不用比较。所以是2n - 1次。

(2)更少的情况,比如tmpArr = ,这样比较2n - 2次就可以了。

(3)最少的情况,比如a3

所以,最多比较2n - 1次。

18 C

从2022年开始,不可使用C和Pascal,只能使用C++

19 C

设P(A)表示至少两个人生日在同一月份的概率,P(A')表示四个人的生日都不在同一月份的概率,则P(A) = 1 - P(A')

P(A') = A(12, 4) / 12 ^ 4 = 12 * 11 * 10 * 9 / (12 * 12 * 12 * 12)= 55 / 96

P(A) = 1 - P(A') = 41 / 96

20 B

奥斯卡是电影类的奖项

诺贝尔有六种奖项:物理、化学、生物和医疗、文学、经济、和平

普利策是新闻类的奖项

1 坐标为(1009,)

先列出前十个坐标,然后找归律

第0轮:(0, 0)

第1轮:(1, 0)

第2轮:(1, -2)

第3轮:(-2, -2)

第4轮:(-2, 2)

第5轮:(3, 2)

第6轮:(3, -4)

第7轮:(-4, -4)

第8轮:(-4, 4)

第9轮:(5, 4)

第10轮:(5, -6)

可以看出,x的规律为(n + 1) / 2 * (-1) ^ ((n - 1) / 2)

所以x_2017 = 1009 * (-1) ^ 1008 = 1009

y的规律为(int(n + 2) / 4) * 2 * (-1) ^ (n / 2)

所以,y_2017 = (int(2017 + 2) / 4) * 2 * (-1) ^ (2017 / 2) = 504 * 2 * (-1) ^ 1008 = 1008

2 答案是3

2-2.png

第一步,把顶部的1变成0,如右上角的图所示

第二步,把中间第4个空格上的0变成1,如左下角的图所示

第三步,把中央的1变成0,如右下角的图所示

至此,所有的数字都变成0

1 输出z

分析:第二个for是统计每个字符出现的次数。x出现了两次,y出现了两次,z出现了一次,w出现了一次。

i = 0时,t['x'] = t[120] = 1

i = 1时,t['y'] = t[121] = 1

i = 2时,t['z'] = t[122] = 1

i = 3时,t['x'] = t[120] = 2

i = 4时,t['y'] = t[121] = 2

i = 5时,t['w'] = t[119] = 1

第三个for中的执行情况:

i = 0时,t[s[0]] = t['x'] = 2,if不成立

i = 1时,t[s[1]] = t['y'] = 2,if不成立

i = 2时,t[s[2]] = t['z'] = 1,if成立,输出z,程序结束。

2 输出8

此题考递归,只有当n为1时,g函数返回,此时ans累加1

初始时,m=7, n=3, x=0,

for循环为

i = 0时,ans += g(7, 2, 0)

i = 1时,ans += g(6, 2, 1)

i = 2时,ans += g(5, 2, 2)

对于g(7, 2, 0),递归为

i = 0时,ans += g(7, 1, 0) = 1

i = 1时,ans += g(6, 1, 1) = 2

i = 2时,ans += g(5, 1, 2) = 3

i = 3时,ans += g(4, 1, 3) = 4

对于g(6, 2, 1),递归为

i = 1时, ans += g(5, 1, 1) = 5

i = 2时, ans += g(4, 1, 2) = 6

i = 2时,ans += g(3, 1, 3) = 7

对于g(5, 2, 2),递归为

i = 2时,ans += g(3, 1, 2) = 8

至此,递归结束,答案为8

3 输出11

本程序计算的是某位置x左边的1的个数与x(包括x本身)右边的0的个数的和的最小值。注意,本程序的第一个数的位置算做1,而不是0。

以1001101011001101101011110001为例

i = 1时,左边有0个1,右边有12个0,sum = 0 + 12 = 12

i = 2时,左边有1个1,右边(包括i = 2本身)有12个0,sum = 1 + 12 = 13

i = 3时,左边有1个1,右边(包括i = 3本身)有11个0,sum = 1 + 11 = 12

i = 4时,左边有1个1,右边有10个0,res = 1 + 10 = 11,sum = 1 + 10 = 11

……

i = 27时,左边有15个1,右边(包括i = 27本身)有1个0,sum = 15 + 1 = 16

i = 28时,左边有15个1,右边有0个0,sum = 15 + 0 = 15

所以,最小的和为i = 4时,sum = 11

4 输出1,3

输出2017,1

分析:从if(x == 1 || x == n)和if(y == 1 || y == m)可以看出,这道题是求公共半周期的。

以n = 4, m = 3为例:

x = 1-->2-->3-->4-->3-->2-->1,半周期为3,周期为6

y = 1-->2-->3-->2-->1,半周期为2,周期为4

所以x的半周期为n - 1,周期为2 * (n - 1);y的半周期为m - 1,周期为2 * (m - 1)。

(1)n = 4, m = 3时,公共半周期为2和3的最小公倍数lcm(2, 3) = 6。

当走了6步时,x走了月个半周期,回到1;y走了3个半周期,到达3;此时两个if都成立,cnt = 2,while循环结束。所以x = 1, y = 3即为所求。

(2)n = 2017,m = 1014时,lcm(2017 - 1, 1014 - 1) = 2042208。

当走了2042208时,x走了1013个半周期,到达2017;y走了2016个半周期,回到1; 此时两个if都成立,cnt = 2,while循环结束。所以x = 2017, y = 1即为所求。

1

2

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180427G00VFE00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券