一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)
二、阅读程序
(程序输入不超过数组或字符串定义的范围;判断题正确填 √,错误填 ×。除特殊说明外,判断题 1.5 分,选择题 3 分,共计 40 分)
1
#include <cstdlib>
#include <iostream>
using namespace std;
char encoder[26] = {'C','S','P',0};
char decoder[26];
string st;
int main() {
int k = 0;
for (int i = 0; i < 26; ++i)
if (encoder[i] != 0) ++k;
for (char x ='A'; x <= 'Z'; ++x) {
bool flag = true;
for (int i = 0; i < 26; ++i)
if (encoder[i] ==x) {
flag = false;
break;
}
if (flag) {
encoder[k]= x;
++k;
}
}
for (int i = 0; i < 26; ++i)
decoder[encoder[i]- 'A'] = i + 'A';
cin >> st;
for (int i = 0; i < st.length( ); ++i)
st[i] = decoder[st[i] -'A'];
cout << st;
return 0;
}
判断题
单选题
了解了,下面是根据您的要求使用“>”符号进行格式化的输出示例:
2
#include <iostream>
using namespace std;
long long n, ans;
int k, len;
long long d[1000000];
int main() {
cin >> n >> k;
d[0] = 0;
len = 1;
ans = 0;
for (long long i = 0; i < n; ++i) {
++d[0];
for (int j = 0; j + 1 < len; ++j) {
if (d[j] == k) {
d[j] = 0;
d[j + 1] += 1;
++ans;
}
}
if (d[len - 1] == k) {
d[len - 1] = 0;
d[len] = 1;
++len;
++ans;
}
}
cout << ans << endl;
return 0;
}
假设输入的 ( n ) 是不超过 ( 2^(62) ) 的正整数,( k ) 都是不超过 10000 的正整数,完成下面的判断题和单选题:
判断题
单选题
3
#include <algorithm>
#include <iostream>
using namespace std;
int n;
int d[50][2];
int ans;
void dfs(int n, int sum) {
if (n == 1) {
ans = max(sum, ans);
return;
}
for (int i = 1; i < n; ++i) {
int a = d[i - 1][0], b = d[i - 1][1];
int x = d[i][0], y = d[i][1];
d[i - 1][0] = a + x;
d[i - 1][1] = b + y;
for (int j = i; j < n - 1; ++j)
d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
int s = a + x + abs(b - y);
dfs(n - 1, sum + s);
for (int j = n - 1; j > i; --j)
d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
d[i - 1][0] = a, d[i - 1][1] = b;
d[i][0] = x, d[i][1] = y;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i][0];
for (int i = 0; i < n; ++i)
cin >> d[i][1];
ans = 0;
dfs(n, 0);
cout << ans << endl;
return 0;
}
假设输入的 n 是不超过 50 的正整数,( d[i][0] )、( d[i][1] ) 都是不超过 10000 的正整数,完成下面的判断题和单选题:
判断题
单选题
三、完善程序(单选题,每小题3分,共计30分)
1.
(质因数分解)给出正整数 ( n ),请输出将 ( n ) 质因数分解的结果,结果从小到大输出。
例如:输入 ( n = 120 ),程序应该输出 2 2 2 3 5,表示: ( 120 = 2 * 2 * 2 * 3 * 5 )。输入保证 ( 2 ≤ n ≤ 10^9 )。
提示:先从小到大枚举变量 ( i ),然后用 ( i ) 不停试除 ( n ) 来寻找所有的质因子。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for(i = ①; ② <= n; i++){
③{
printf("%d ", i);
n = n / i;
}
}
if(④)
printf("%d ", ⑤);
return 0;
}
选择题
2
(最小区间覆盖)给出n个区间,第 i 个区间的左右端点是 ([a_i, b_i])。现在要在这些区间中选出若干个,使得区间 ([0, m]) 被所选区间的并覆盖(即每一个 (0 ≤ i ≤ m) 都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。
输入第一行包含两个整数 ( n ) 和 ( m ) ((1 ≤ n ≤ 5000), (1 ≤ m ≤ 10^9))
接下来 ( n ) 行,每行两个整数 ( a_i, b_i ) (0 ≤ a_i, b_i ≤ m)。
提示:使用贪心法解决这个问题。先用 (O(n^2)) 的时间复杂度排序,然后贪心选择这些区间。
试补全程序。
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans =0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}