2022年第20届NOC大赛_C++软件创意编程赛项_决赛_初中组真题（忽略分值）答案及解析.pdfVIP

一、单选题

1、时间复杂度为O(nlogn)的排序算法是()

A冒泡排序

B归并排序

C计数排序

D选择排序

解析：【喵呜刷题小喵解析】：冒泡排序、选择排序的时间复杂度都是O(n^2)，计

数排序的时间复杂度是O(n+k)，其中k是待排序数的范围，而归并排序的时间复杂

度是O(nlogn)。因此，时间复杂度为O(nlogn)的排序算法是归并排序，选项B正确。

2、后缀表达式32512+*+的值是（）。

A23

B25

C37

D65

解析：【喵呜刷题小喵解析】：

首先，我们需要理解后缀表达式（也称为逆波兰表达式）的计算规则。在后缀表达

式中，操作数位于操作符之前，因此计算顺序是从左到右。

对于表达式32512+*+，我们可以按照以下步骤计算：

1.取出前两个操作数3和2，由于它们之间没有操作符，所以直接作为结果保留。

2.取出下一个操作数5，与前面保留的结果3和2一起，形成表达式32

5。由于它们之间仍然没有操作符，所以继续保留。

3.取出下一个操作数12，与前面保留的表达式325一起，形成表达式325

12。由于仍然没有操作符，继续保留。

4.取出操作符+，与前面保留的表达式32512一起，形成表达式32512

+。根据后缀表达式的计算规则，此时应该计算5+12=17。

5.取出下一个操作数2（注意，不是5），与前面计算得到的17一起，形成表达式

172。由于仍然没有操作符，继续保留。

6.取出操作符*，与前面保留的表达式172一起，形成表达式172

*。根据后缀表达式的计算规则，此时应该计算17*2=34。

7.最后，取出最后一个操作符+，与前面计算得到的34一起，形成表达式34

+。根据后缀表达式的计算规则，此时应该计算34+3=37。

因此，后缀表达式32512+*+的值是37，对应选项B。

3、有如上函数定义，则调用fun(6)得到的返回结果为()

A720

B180

C144

D48

解析：【喵呜刷题小喵解析】根据题目中的函数定义，函数`fun`的公式为：

fun(n)=n*(n+1)*(n+2)

当调用`fun(6)`时，将n=6代入公式，得到：

fun(6)=6*(6+1)*(6+2)

=6*7*8

=336

因此，函数`fun(6)`的返回结果为336，而不是选项中的任何一个值。题目中给出的

选项可能是错误的或者题目被截断了。根据题目中的函数定义，最接近的可能是选

项C，但我们需要更多的信息来确定正确的答案。在此，我们只能基于题目中的函

数定义推测出答案可能是144，但真正的答案需要更多的上下文信息。

4、小于等于30000的正整数中，与30000互质的正整数有()个

A8000

B8500

C6000

D9000

解析：【喵呜刷题小喵解析】

首先，我们需要明确互质数的定义：两个正整数，如果它们的最大公约数（GCD

）是1，则它们被称为互质数。

对于本题，我们需要找出小于等于30000的正整数中，与30000互质的正整数有多少

个。

我们可以使用容斥原理来解决这个问题。容斥原理的基本思想是通过两个集合各自

的元素个数和它们的交集个数来计算它们的并集个数。

在这里，我们可以将小于等于30000的正整数分为若干个集合，每个集合中的元素

都与30000有相同的质因数。例如，我们可以将小于等于30000的正整数分为与3000

0有相同质因数2、3、5等的集合。

然后，我们可以计算每个集合中元素的个数，以及它们的交集个数。最后，根据容

斥原理，我们可以计算出与30000互质的正整数的个数。

具体来说，小于等于30000的正整数中，与30000有相同质因数2、3、5等的集合的

元素个数分别为：

-与30000有相同质因数2的集合的元素个数为：$\left\lfloor\frac{30000}{2}

\right\rfloor+\left\lfloor\frac{30000}{2^2}\right\rfloor+\left\lfloor\frac{30000}{2^3}

\right\rfloor+...=15000+7500+3750+187