2022年第20届NOC大赛_C++软件创意编程赛项_选拔赛_初中组真题
一、选择题
第 1 题 单选题
一个C++的源程序中，有关主函数的说法正确的是（）
A. 可以有多个主函数
B. 必须有一个主函数
C. 必须有主函数和其他函数
D. 可以没有主函数
第 2 题 单选题
下列四个不同进制的数中，与其他三项数值上不相等的是（）
A. (42.8)16
B. (66.5)10
C. (102.4)8
D. (1000011.1)2
第 3 题 单选题
在上面的条件语句中（其中s1和s2代表C++语言的语句），只有一个在功能上与其他三个语句不等价，它是（）
A. if (n) s1; else s2;
B. if (n == 0) s1; else s2;
C. if (n == 0) s2; else sl;
D. if (n != 0) s1; else s2;
第 4 题 单选题
从1到2022这2022个数中，共有____个包含数字2的数。()
A. 565
B. 629
C. 630
D. 566
第 5 题 单选题
若定义int a=2，b=2，下列表达式中值不为4的是（）。
A.
a*(++b)
B.
a*(b++)
C.
a+b
D.
a*b
第 6 题 单选题
若有如下程序段，其中s、n、i均为已定义的长整型变量。
s=0;
for(i=1;i<=n;i++)
{
s=s*2+1;
}
当n=50时，s的值为
A. 249-1
B. 250-1
C. 251-1
D. 以上答案都不对
第 7 题 单选题
对于入栈顺序为 a，b，c，d，e，f的序列，下列（）是不合法的出栈序列。
A. a,b,c,d,e,f
B. a,c,e,b,d,f
C. e,d,c,f,b,a
D. b,a,d,c,f,e
第 8 题 单选题
（ ）的平均时间复杂度为 O(n log n)，其中 n是待排序的元素个数。
A. 插入排序
B. 冒泡排序
C. 快速排序
D. 基数排序
第 9 题 单选题
若二维数组a有n列，则a[i][j]前的元素个数为（）
A.
i*n+j
B.
i*n+j-1
C.
i*n+j+1
D.
j*n+i
第 10 题 单选题
设某算法的时间复杂度函数的递推方程是T(n)=T(n-1)＋n²（n为正整数）及T(1)=1，则该算法的时间复杂度为（）。
A. O(2n)
B. O(n2logn)
C. O(n2)
D. O(n3)
第 11 题 单选题
阅读以下程序，执行以下程序后，下列选项中说法错误的是（）
A. cnta的值为字符串str中大小写字母的个数
B. cntn的值为字符串str中'0'~'9'数字的个数
C. cnta + cntn的值一定等于字符串str的字符个数
D. 字符串str中可能存在空格
第 12 题 单选题
阅读以下程序，执行以下程序后，下列选项中说法正确的是（）
A. 该程序会输出字符串s中所有仅出现了一次的字符的出现次数
B. 如果字符串s中存在多个仅出现一次的字符，则会输出"no"
C. 该程序会输出字符串s中所有仅出现了一次的字符
D. 如果字符串s中所有字符的出现次数都多于1次，则会输出"no"
第 13 题 单选题
运行以上程序，输出结果为（）
A. 633
B. 631023
C. 623013
D. 632103
第 14 题 单选题
阅读以下程序，执行以下程序后，
第一行输入n,m;(m<=n)第二行输入n个数。
如果输入的n个数data[i]都相同，则程序输出的值为（）
A. m+1
B. m
C. 1
D. 0
第 15 题 单选题
阅读以下程序，执行以下程序后，
第一行输入n,m;(m<=n)第二行输入n个数。
如果输入的n个数data[i]为升序且互不相同，则程序输出的值为（）
A. n-m+1
B. n-m-1
C. n-m
D. m+1
二、编程题
第 16 题 问答题
密码翻译
【题目描述】
我们得到了由如下加密规则加密而成的一段密文，请你解密出原文。
加密规则：把所有原文中的英文字母以之后的第k个字母代替，如果超出字母表，则转回第一个字母。
例如，规定k=4，则字母'A'以'E'代替（A->B->C->D->E），字母'X'以字母'B'代替（X->Y->Z->A->B）。因此单词“AXE”加密后为“EBI”；如果密文是“EAEC”则可以推出明文是"AWAY"。
给出一段仅有大小写英文字母和数字组成的密文和密钥k，请你解密出原文。
注意，原文和密文对应位置的字母的大小写应保持一致。
【输入格式】
第一行，一个正整数k；
第二行，一个仅有大小写英文字母和数字组成的密文字符串。
【输出格式】
共一行，为解密后的原文字符串。
【输入样例1】
3
QRF
【输出样例1】
NOC
【输入样例2】
53 Dqq11
【输出样例2】
Cpp11
【数据范围】
对于40%的数据，1≤k≤26，1≤字符串长度 < 100，字符串仅有大小写字母组成。
对于100%的数据，1≤k≤100，1≤字符串长度≤1000
第 17 题 问答题
体操训练
【题目描述】
为了提高健康水平，同学开始进行体操训练了！
共安排了K次训练课，每次课体委都会根据N个同学的表现给他们进行排名。之后，他想知道，有多少种一个同学会“完胜”另外一个同学的情况。（如果某同学A在每次训练课中都表现得都比另一个同学B要好，那么称A"完胜"B。）
请编程计算有多少种一个同学会“完胜”另外一个同学的情况。
【输入格式】
输入的第一行包含两个正整数K和N。
以下K行每行包含整数1...N的某种排列，表示同学们的排名（同学们用编号1....N进行区分）。如果在某一行中A出现在B之前，表示同学A表现得比同学B要好。
【输出格式】
输出一行，一个整数表示有多少种一个同学会"完胜"另外一个同学的情况。
【输入样例1】
3 4
4 1 2 3
4 1 3 2
4 2 1 3
【输出样例1】
4
【样例1说明】
共有4种情况：
4号同学完胜1号同学
4号同学完胜2号同学
4号同学完胜3号同学
1号同学完胜3号同学
【输入样例2】
3 10
10 1 4 2 3 9 5 7 8 6
8 4 9 10 7 6 3 1 2 5
1 6 7 2 4 3 8 9 10 5
【输出样例2】
9
【数据范围】
对于60%的数据，1≤k≤20，1≤n≤100
对于100%的数据，1≤k≤1000，1≤n≤100
查看答案 第 18 题 问答题 飞跃摩天楼
【题目描述】
东东是一位穿梭在暗夜的城市里惩恶扬善的超级英雄，但是在一次侦查的过程中，他被一群坏蛋发现了。为了逃脱恶人的追捕，东东需要在摩天楼的屋顶之间飞跃，最终到达安全的位置。逃跑路线—共有N座摩天大楼，从1到N进行编号，东东从1号大楼出发，通过特制的跳跃装置跳到2号大楼，然后再通过2号大楼跳到3号大楼……最终跳到N号大楼，就是目标的安全位置。由于跳跃距离越远，跳跃装置的安全性就越差，所以东东希望他跳跃的最大距离尽可能小。为了安全，东东已经提前准备好两个强力热气球，热气球可以代替大楼作为东东一次跳跃的终点和下一次跳跃的起点，他可以把热气球安排在合适的位置，来帮助他更安全的逃脱。
为了确定自己能顺利逃脱，东东需要他的技术顾问，也就是你，替他算出在最安全的情况下，他最大的跳跃距离。
【输入格式】
输入有两行，第一行为两个正整数N，表示摩天大楼的数量。
第二行有N-1个整数，表示第i座摩天大楼与第i＋1座摩天大楼之间的距离。
【输出格式】
输出一个整数，表示东东最大的跳跃距离，如果结果是小数，请向上取整。
【输入样例1】
6
3 5 4 11 8
【输出样例1】
6
【样例1说明】
在第4和第5座摩天大楼中间、第5和第6座摩天大楼中间各放一个热气球，东东可以进行次跳跃，距离分别是：3、5、4、5.5、5.5、4、4。其中最远距离向上取整为6。
【输入样例2】
10
19 99 26 32 9 3 7 10 21
【输出样例2】
33
【数据范围】
对于20%的数据：1≤N≤10，相邻的摩天楼距离不超过100；
对于60%的数据：1≤N≤10000；
对于100%的数据：1≤N≤105，相邻的摩天楼距离不超过109。
第 19 题 问答题
比k大的数
【题目描述】
一个不含0的n位数，其中值等于i的数码有ci个（1≤i≤9）。
在这个n位数的所有可能的值中，比k大的值最小是多少？
【输入格式】
第1行，2个正整数n，k。
第2行，9个非负整数c1，c2，…，c9，分别表示1～9的个数。
【输出格式】
输出所有可能的值中，比k大的值的最小值。
如果没有比k大的值，输出-1。
【输入样例1】
3 213
1 1 1 0 0 0 0 0 0
【输出样例1】
231
【输入样例2】
4 4000
1 0 2 1 0 0 0 0 0
【输出样例2】
4133
【输入样例3】
3 9999
1 1 1 0 0 0 0 0 0
【输出样例3】
-1
【输入样例4】
21 791823456795285473500
1 2 2 3 2 3 2 3 3
【输出样例4】
791823456795286344689
【样例1说明】
有1个1、1个2、1个3，可能的值有123，132，213，231，312，321，共6个。其中，比k=213 大的最小值是231。
【样例2说明】
有1个1、2个3、1个4，可能的值有
1334，1343，1433，3134，3143，3314，3341，3413，3431，4133，4313，4331共12个。其中，比k=4000 大的最小数是4133。
【样例3说明】
有1个1、1个2、1个3，可以得到的最大值321都比k=9999小，所以无法得到比k大的值。
【样例4说明】
输入输出可能超过64位整数类型范围。
【数据范围】
对于25%的数据，n≤9；k≤109。
对于50%的数据，n≤200；k≤10200。
对于100%的数据，1≤n≤500000；1≤k≤10500001；
Ci ≥0,C1＋C2＋C3＋C4＋C5＋C6＋C7＋C8＋C9=n。