学习C++从娃娃抓起！学习下帝都的对标CSP的BCSP考试，记录下CSP-J备考学习的每一个瞬间。
单选题
第1题
计算机在工作过程中突然停电，（ ）中的信息不会丢失。
A.显存
B.寄存器
C.RAM
D.ROM
【答案】：D
第2题
中缀表达式a*(b+c)-d的后缀形式是（ ）。
A.abcd*±
B.abc+*d-
C.abc*+d-
D.-+*abcd
【答案】：B
第3题
设栈S的初始状态为空，元素a，b，c，d，e依次入栈，以下出栈序列不可能出现的有（ ）。
A.a，b，c，e，d
B.b，c，a，e，d
C.a，e，c，b，d
D.d，c，e，b，a
【答案】：C
第4题
已知7个结点的二叉树的先根遍历是1245637（数字为结点编号），中根遍历是4265173，则该二叉树的后根遍历是（ ）。
A.4652731
B.4652137
C.4231547
D.4653172
【答案】：A
第5题
在C++中， 若变量x为int类型且已被赋值为40， 则x&(x-1) 的值为（ ）。
A.79
B.47
C.32
D.0
【答案】：C
第6题
有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098，中间一项是486，请问以下那个数是可能的公比（ ）。
A.2
B.3
C.4
D.5
【答案】：B
第7题
设变量x为float类型且己赋值， 则以下语句能将x中的数值四舍五入到小数点后第2位的是（ ）。
A.x = (x * 100 + 0.5) / 100.0
B.x = x * 100 + 0.5 / 100.0
C.x = (x / 100 + 0.5) * 100.0
D.x = (int)(x * 100 + 0.5) / 100.0
【答案】：D
第8题
十六进制下，7 * 7的运算结果为（ ）。
A.31
B.38
C.41
D.48
【答案】：A
第9题
（ ）是一种选优搜索法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。
A.回溯法
B.枚举法
C.动态规划
D.贪心
【答案】：A
第10题
1TB代表的字节数是（ ）。
A.2的10次方
B.2的20次方
C.2的30次方
D.2的40次方
【答案】：D
第11题
原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC"共有（ ）个不同的非空子串。
A.3
B.12
C.36
D.45
【答案】：C
第12题
1958年以前的第一代计算机主要用于科学计算、军事研究。这些计算机以（ ）为主要的逻辑元件。
A.晶体管
B.电子管
C.集成电路
D.大规模集成电路
【答案】：B
第13题
链表不具备的特点是（ ）。
A.可用O(1)时间随机访问任何一个元素。
B.插入、删除操作不需要移动元素。
C.存储单元在内存中的地址可以不连续。
D.无需事先估计存储空间大小。
【答案】：A
第14题
以下排序算法中，（ ）属于稳定排序算法。
A.堆排序
B.选择排序
C.冒泡排序
D.快速排序
【答案】：C
第15题
完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当在放在数组中的（ ）号位置。
A.2k
B.2k+1
C. ⌈ k / 2 ⌉ \lceil k/2 \rceil ⌈k/2⌉
D. ⌊ k / 2 ⌋ \lfloor k/2 \rfloor ⌊k/2⌋
【答案】：C
阅读程序
#include <iostream>
using namespace std;
int main() {
int n, a[105], avg=0, ans=0;
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
avg += a[i];
}
avg /= n;
for (int i=1; i<n; i++)
if (a[i]<avg) {
a[i+1] -= (avg-a[i]);
ans += (avg-a[i]);
}
else if (a[i]>avg) {
a[i+1] += (a[i]-avg);
ans += (a[i]-avg);
}
cout << ans << endl;
return 0;
}
假设输入的所有数是不超过100的正整数，完成下面的判断题和单选题：
第16题
该程序的算法时间复杂度为O(n)。（ ）
A.正确
B.错误
【答案】：A
第17题
若将第4行的代码改为“int n, a[105], avg, ans;”（声明变量时不赋值）， 程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ）
A.正确
B.错误
【答案】：A
第18题
若将第4行的代码改为“int n, a[100], avg=0, ans=0”（更改数组a的大小），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ）
A.正确
B.错误
【答案】：B
第19题
若将第11行的for循环执行条件改为“i<=n”， 程序仍可以被正常执行， 且对于相同的输入数据，输出结果不变。（ ）
A.正确
B.错误
【答案】：B
第20题
若将第16行的代码改为“else{”（去掉else之后的条件判断） ， 程序仍可以被正常执行， 且对于相同的输入数据，输出结果不变。（ ）
A.正确
B.错误
【答案】：A
第21题
该程序的输出结果不可能为负数。（ ）
A.正确
B.错误
【答案】：A
第22题
若输入数据第一行为“7”，第二行为“1 9 2 8 12 2 8”，则程序将输出（ ）。
A.2
B.16
C.21
D.26
【答案】：C
#include <iostream>
using namespace std;
int n, h[1000005], L, R;
long long m;
int main() {
cin >> n >> m;
for (int i=1; i<=n; i++) {
cin >> h[i];
if (h[i]>R) R = h[i];
}
while (L < R) {
int mid = (L+R+1) / 2;
long long tmp = 0;
for (int i=1; i<=n; i++)
if (h[i]>mid)
tmp += h[i]-mid;
if (tmp<m)
R = mid - 1;
else
L = mid;
}
cout << L << endl;
}
假设输入的所有数是正整数，其中n以及数组元素h[1],h[2],…,h[n]均不超过1000000，m不超过h[1],h[2],…,h[n]之和，完成下面的判断题和单选题：
第23题
若将第011行的while循环执行条件改为“L <= R"， 程序仍可以被正常执行， 且对于相同的输入数据，输出结果不变。（ ）
A.正确
B.错误
【答案】：B
第24题
若将变量m和变量tmp的数据类型都改为int， 程序仍可以被正常执行， 且对于相同的输入数据输出结果不变。（ ）
A.正确
B.错误
【答案】：B
第25题
程序的输出结果有可能是0。（ ）
A.正确
B.错误
【答案】：A
第26题
将第12行的代码改为（ ），程序执行的效果不变。
A.int mid = (L+R) / 2;
B.int mid = (L+R) * 2;
C.int mid = L + R + 1 << 2;
D.int mid = L + R + 1 >> 2;
【答案】：无
第27题
若输入数据第一行为“5 20”，第二行为“4 42 40 26 46”，则程序将输出（ ）。
A.35
B.36
C.37
D.38
【答案】：B
第28题
若输入的n为10000，程序输出结果的最大可能值是（ ）。
A.9999
B.10000
C.999999
D.1000000
【答案】：C
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 5000 + 5;
int n, a[MAXN], d[MAXN];
int check(int k) {
memset(d, 0, sizeof(d));
int res = 0;
for (int i=1, s=0; i<=n; i++) {
s += d[i];
if ((a[i]+s)%2==1)
continue;
if (i+k>n+1)
return 1e9;
d[i]++, s++, res++;
d[i+k]--;
}
return res;
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; i++)
scanf("%d", &a[i]);
int ans = 1e9;
for (int k=1; k<=n; k++) {
int tmp = check(k);
if (tmp < ans)
ans = tmp;
}
printf("%d\n", ans);
return 0;
}
假设输入的n是不超过5000的正整数，数组元素a[1],a[2],…,a[n]均是不超过1的非负整数，完成下面的判断题和单选题：
第29题
若将第9行的for循环执行条件改为“i+k-1<=n”， 程序仍可以被正常执行， 且对于相同的输入数据，输出结果不变。（ ）
A.正确
B.错误
【答案】：B
第30题
若将第15行的代码改为"s++, res++; ”（去掉d[i]++） ， 程序仍可以被正常执行， 且对于相同的输入数据，输出结果不变。（ ）
A.正确
B.错误
【答案】：A
第31题
若将第15行中的“s++”改为“s–”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ）
A.正确
B.错误
【答案】：B
第32题
程序的输出结果有可能为0。（ ）
A.正确
B.错误
【答案】：A
第33题
程序的输出结果必然小于输入的n。（ ）
A.正确
B.错误
【答案】：B
第34题
该程序的算法时间复杂度为（ ）。
A. O ( n ) O(n) O(n)
B. O ( n l o g n ) O(nlogn) O(nlogn)
C. O ( n 2 ) O(n^2) O(n2)
D. O ( n 2 l o g n ) O(n^2logn) O(n2logn)
【答案】：C
第35题
若输入数据第一行为“7”，第二行为“0010100”，则程序将输出（ ）。
A.3
B.4
C.5
D.6
【答案】：A
完善程序
（一）给定长度n的整数序列a，a，…，a，以及q个询问。每个询问将指定两个整数l，r，请判断下标在l到r之间的序列元素（包括 a l a_l al与 a r a_r ar）是否互不相同。输入数据保证 1 ≤ n , q ≤ 100000 , 1 ≤ a i ≤ n , l ≤ 1 ≤ r ≤ n 1\le n,q\le 100000,1\le a_i\le n,l\le 1\le r\le n 1≤n,q≤100000,1≤ai≤n,l≤1≤r≤n。
试用最优选项补全程序：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5+5;
int n, q, a[MAXN], last[MAXN], tmp[MAXN], mxlast[MAXN];
int main() {
cin >> n >> q;
for (int i=1; i<=n; i++) {
cin >> a[i];
__1__;
__2__;
__3__;
if (last[i]>mxlast[i])
mxlast[i] = last[i];
}
while (__4__) {
int l, r;
cin >> l >> r;
if (__5__)
cout << "No" << endl; //区间内存在相同元素
else
cout << "YES" << endl; //互不相同
}
return 0;
}
第36题
1处应填（ ）。
A.last[tmp[i]] = a[i]
B.last[i] = tmp[a[i]]
C.tmp[last[i]] = i
D.tmp[a[i]] = i
【答案】：B
第37题
2处应填（ ）。
A.last[tmp[i]] = a[i]
B.last[i] = tmp[a[i]]
C.tmp[last[i]] = i
D.tmp[a[i]] = i
【答案】：D
第38题
3处应填（ ）。
A.mxlast[i] = MAXN
B.mxlast[i] = tmp[i]
C.mxlast[i] = 0
D.mxlast[i] = mxlast[i-1]
【答案】：D
第39题
4处应填（ ）。
A.q–
B.–0
C.!(q–)
D.!(–q)
【答案】：A
第40题
5处应填（ ）。
A.mxlast[l] <= r
B.mxlast[r] <= l
C.mxlast[l] >= r
D.mxlast[r] >= l
【答案】：D
（二）给定正整数n，请编写程序计算它的全部正约数之和。输入数据保证 n ≤ 10000000 n\le 10000000 n≤10000000。
试用最优选项补全程序：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 10000005;
int n, d[MAXN];
bool flag[MAXN];
long long value(int x, int k) {
long long ans = 1;
for (int i=1; i<=k+1; i++)
ans *= x;
return __1__;
}
int main() {
for (__2__) {
if (flag[i]) continue;
for (int j=i; j<MAXN; j+=i) {
if (flag[j]) continue;
flag[j] = true;
__3__;
}
}
cin >> n;
long long ans = 1;
int last = -1, t = 0;
for (; n>1; __4__) {
if (d[n]==last) t++;
else {
ans *= value(last, t);
__5__;
}
}
ans *= value(last, t);
cout << ans << endl;
return 0;
}
第41题
1处应填（ ）。
A.ans / (x-1)
B.ans * (x-1)
C.(ans-1) * (x-1)
D.(ans-1) / (x-1)
【答案】：D
第42题
2处应填（ ）
A.int i=1; i<MAXN; i++
B.int i=1; i<=MAXN; i++
C.int i=2; i<MAXN; i++
D.int i=2; i<=MAXN; i++
【答案】：C
第43题
3处应填（ ）。
A.d[j]=i
B.d[i]=j
C.d[i]=i
D.d[j]=j
【答案】：A
第44题
4处应填（ ）
A.n -= d[n]
B.n -= last
C.n /= d[n]
D.n–
【答案】：C
第45题
5处应填（ ）
A.last = d[n], t=0
B.last = d[n], t=1
C.last = d[n], t–
D.last = -1, t = 0
【答案】：B
标签：BCSP,__,last,真题,int,初赛,答案,ans,tmp From： https://blog.csdn.net/guolianggsta/article/details/139811241