阅读程序-枚举算法
阅读程序
注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。
第3节：枚举算法
第1题【NOIP】2013
#include <iostream>
#include <string>
using namespace std;
int main() {
string str;
cin>>str;
int n=str.size();
8 bool isPlalindrome=true;
for (int i = 0; i < n/2; i++) {
if (str[i] != str[n-i-1]){
11 isPlalindrome = 0;
}
}
if (isPlalindrome)
printf("Yes\n");
else
printf("No\n");
18 return 0;
}
●判断题
(1)如果去掉第18行，程序不能正常运行。
{{ select(1-1) }}
- 对
- 错
(2)如果去掉第8行的初始化，程序可能得不到正确答案。
{{ select(1-2) }}
- 对
- 错
(3)在11行下添加一行break;,程序运行结果不变
{{ select(1-3) }}
- 对
- 错
(4)如果输入abceecba,输出Yes。
{{ select(1-4) }}
- 对
- 错
●选择题
(5)程序的时间复杂度为()。
{{ select(1-5) }}
- O(n)
- O(logn)
- O(nlogn)
- O()
(6)输入abcdefghijklmnmlkjihgfedcba,输出为( )。
{{ select(1-6) }}
- No
- Yes
- NO
- YES
第2题【NOIP】2017
#include<iostream>
using namespace std;
int main(){
int t[256];
string s;
int i;
7 cin >> s;
8 for (i = 0; i < 256; i++)
9 t[i] = 0;
for (i = 0; i < s.length(); i++)
t[s[i]]++;
for (i = 0; i < s.length(); i++)
if (t[s[i]] == 1){
cout << s[i] << endl;
return 0;
}
cout << "no" << endl;
return 0;
}
●判断题
(1)第7行输入的字符串s可以是任意字符，包括字母、数字、各类符号甚至中文汉字及符号。()
{{ select(2-1) }}
- 对
- 错
(2)若去掉8~9行，输出结果不变。
{{ select(2-2) }}
- 对
- 错
(3)若答案为no,则说明字符串s中的每个字符出现次数都大于1。
{{ select(2-3) }}
- 对
- 错
(4)若输人的字符串中各字符互不相同，则输出结果为no。
{{ select(2-4) }}
- 对
- 错
●选择题
(5)若输入的字符为yzywYZYW,则输出为( )。
{{ select(2-5) }}
- y
- z
- w
- W
(6)若输入的字符为YZYWyzyw,则输出为()。
{{ select(2-6) }}
- Y
- Z
- W
- w
第3题【NOIP】2017
#include<iostream>
using namespace std;
int main(){
string ch;
int a[200];
int b[200];
int n, i, t, res;
cin >> ch;
n = ch.length();
10 for (i = 0; i < 200; i++)
11 b[i] = 0;
for (i = 1; i <= n; i++){
a[i] = ch[i - 1] - '0';
b[i] = b[i - 1] + a[i];
}
res = b[n];
t = 0;
for (i = n; i > 0; i--){
if (a[i] == 0)
t++;
if (b[i - 1] + t < res)
res = b[i - 1] + t;
}
cout << res << endl;
return 0;
}
●判断题
(1)输入的字符串长度必须小于等于200,否则可能会出现运行时错误。
{{ select(3-1) }}
- 对
- 错
(2)若输入字符串为1001101011001101101011110001,则会输出12。
{{ select(3-2) }}
- 对
- 错
(3)去掉第10行和第11行，程序一定可以正常运行。
{{ select(3-3) }}
- 对
- 错
(4)输入的字符串必须由01字符组成。
{{ select(3-4) }}
- 对
- 错
●选择题
(5)程序的时间复杂度为( )。
{{ select(3-5) }}
- O(1)
- O(nlogn)
- O(n)
- O()
(6)若输人1010405010401090109080100,输出为()。
{{ select(3-6) }}
- 0
- 5
- 26
- 13
第4题【NOIP】2010
#include<iostream>
using namespace std;
int main(){
const int SIZE=10;
int data[SIZE],i,j,cnt,n,m;
cin>>n>>m;
for(i=1;i<=n;i++)
cin>>data[i];
for(i=1;i<=n;i++) {
cnt=0;
for(j=1;j<=n;j++)
if( (data[i]<data[j]) || (data[j]==data[i] && j<i) )
cnt++;
14 if (cnt==m)
cout<<data[i]<<endl;
}
return 0;
}
●判断题
(1)若输入的n大于等于10,则程序可能发生运行时错误。
{{ select(4-1) }}
- 对
- 错
(2)若输入的m大于等于n,则程序没有输出。
{{ select(4-2) }}
- 对
- 错
(3)若把第14行的==换成>=,则程序运行结果不变。
{{ select(4-3) }}
- 对
- 错
(4)输入5 2 9 6-8 0 16 87,则会输出17。
{{ select(4-4) }}
- 对
- 错
●选择题
(5)输人6 3 1 5 3 7 8 4,则输出为
{{ select(4-5) }}
- 1
- 3
- 4
- 5
(6)程序的时间复杂度为()。
{{ select(4-6) }}
- O(n)
- O(logn)
- O(nlogn)
- O()
第5题【NOIP】2015
#include <iostream>
#include <string>
using namespace std;
int main() {
int len, maxlen;
string s, ss;
7 maxlen = 0;
do {
cin >> ss;
len = ss.length();
if (ss[0] == '#')break;
12 if (len > maxlen) {
s = ss;
maxlen = len;
}
} while (true);
cout << s << endl;
return 0;
}
●判断题
(1)输出可以包含#。
{{ select(5-1) }}
- 对
- 错
(2)如果去掉第7行的初始化，程序可能得不到正确答案。
{{ select(5-2) }}
- 对
- 错
(8)输出一定有字符
{{ select(5-3) }}
- 对
- 错
(4)如果把第12行的>改为>=，程序结果不会改变。
{{ select(5-4) }}
- 对
- 错
●选择题
(5)程序的时间复杂度级别为()
{{ select(5-5) }}
- 线性
- 对数
- 常数
- 平方
(6)输人I am a citizen of China #,输出( )。
{{ select(5-6) }}
- am
- a
- citizen
- China
第6题【NOIP】2018
#include <stdio.h>
int main() {
int x;
scanf("%d", &x);
int res = 0;
for (int i = 0; i < x; ++i) {
if (i * i % x == 1) {
++res;
}
}
11 printf("%d", res);
12 return 0;
}
●判断题
(1)如果把第11行的“%d”改为“%lld”,程序可以正常输出答案。
{{ select(6-1) }}
- 对
- 错
(2)删去12行的语句，运行结果将发生改变。
{{ select(6-2) }}
- 对
- 错
(3)如果输入2147483648,程序输出4。
{{ select(6-3) }}
- 对
- 错
(4)程序输入的数字小于等于40360时，正确性可以保证。
{{ select(6-4) }}
- 对
- 错
●选择题
(5)如果输入100,程序输出()。
{{ select(6-5) }}
- 20
- 4
- 0
- 9
(6)程序的时间复杂度为()
{{ select(6-6) }}
第7题【NOIP】2016
#include <iostream>
using namespace std;
int main() {
int Max, Min, sum, count = 0;
int tmp;
cin >> tmp;
if (tmp == 0)
return 0;
Max = Min = sum = tmp;
count++;
while (tmp != 0) {
cin >> tmp;
if (tmp != 0) {
sum += tmp;
count++;
if (tmp > Max)
Max = tmp;
if (tmp < Min)
Min = tmp;
}
}
22 cout << Max << "," << Min << "," << sum / count << endl;
return 0;
}
●判断题
(1)程序一定会输出3个正个整数并用逗号隔开
{{ select(7-1) }}
- 对
- 错
(2)若把Max,Min,sum的数据类型改为double.则输出结果会改变。
{{ select(7-2) }}
- 对
- 错
(3)输入1 2 0 3 4 5 0 7 0时，count值最终为8.
{{ select(7-3) }}
- 对
- 错
(4)程序的时间复杂度瓶颈在于第22行计算答案过程。
{{ select(7-4) }}
- 对
- 错
●选择题
(5)程序的时间复杂度为()
{{ select(7-5) }}
- O(1)
- O(count)
- O()
- O(tmp)
(6)若输入为1 9 2 8 3 7 4 6 0 5,则会输出()。
{{ select(7-6) }}
- 9,1,5
- 9,1,6
- 9,1,7
- 9,1,8
第8题【NOIP】2012
#include <iostream>
using namespace std;
int n, i, temp, sum, a[100];
int main() {
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n - 1; i++)
if (a[i] > a[i + 1]) {
10 temp = a[i];
11 a[i] = a[i + 1];
12 a[i + 1] = temp;
}
14 for (i = n; i >= 2; i--)
15 if (a[i] < a[i - 1]) {
16 temp = a[i];
17 a[i] = a[i - 1];
18 a[i - 1] = temp;
19 }
sum = 0;
for (i = 2; i <= n - 1; i++)
sum + = a[i];
cout << sum / (n - 2) << endl;
return 0;
}
●判断题 (1)输入的n小于100,否则可能会出现运行时错误。
{{ select(8-1) }}
- 对
- 错
(2)第10行到第12行实现了交换的功能。
{{ select(8-2) }}
- 对
- 错
(3)把sum的数据类型改为double,程序运行结果不会改变。
{{ select(8-3) }}
- 对
- 错
(4)当n为2时，程序可以正常运行。
{{ select(8-4) }}
- 对
- 错
●选择题 (5)程序的时间复杂度为( )。
{{ select(8-5) }}
- O(1)
- O(nlogn)
- O(n)
- O(n²)
(6)14～19行的代码段功能为( )。
{{ select(8-6) }}
- 排序整个序列
- 把序列中的最小值放到序列开头
- 把序列中的最小值放到序列末尾
- 把序列中的最大值放到序列末尾