选 单项选择题（共 15 题，共 0 分）
执行下列代码后，cnt 的值是（ ）。
int x = 2026, cnt = 0;
while (x) {
x &= x - 1;
cnt++;
}
用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ ）。
把 1 到 1000 的所有整数按十进制写出，数字“1”总共出现了多少次（ ）。
将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ ）。
32026mod100 的值是（ ）。
有 5 堆石子排成一行，重量依次为 4、1、3、2、5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）。
树状数组维护长度 n=16 的序列，查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问树状数组中多少个下标（ ）。
有向无环图 G 顶点集为 {1,2,3,4}，边集为 {(1,2),(1,3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。
某分治算法满足 T(n)=T(n/3)+T(2n/3)+Θ(n)，T(1)=O(1)，则 T(n) 是（ ）。
无根树含 9 个结点（编号为 1—9），边集为 {(1,2),(1,3),(2,4),(2,5),(3,6),(6,7),(7,8),(5,9)}。该树的直径（以边数计）与重心分别是（ ）。
一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个，出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ ）。
含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）。
字符串 S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ）。
用归并排序统计逆序对，合并部分的核心代码为：
// 分并 a[l..mid] 与 a[mid+1..r]，同时累加逆序对
if (a[i] <= a[j]) {
tmp[k++] = a[i++]; // 取左半段元素
} else {
tmp[k++] = a[j++]; // 取右半段元素
ans += mid - i + 1;
}
若把判断条件中的 a[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果（ ）。
执行 power(2, 100, 1000) 调用下列函数，返回值是（ ）。
long long power(long long a, long long b, long long p) {
long long r = 1 % p;
while (b) {
if (b & 1)
r = r * a % p;
a = a * a % p;
b >>= 1;
}
return r;
}
阅 阅读程序（共 18 题，共 0 分）
#include <iostream>
#include <string>
using namespace std;
int a[100];
string s;
int gen[13] = {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
int main() {
cin >> s;
for (int i = 0; i < 32; ++i) {
a[i] = s[i] - '0';
}
for (int i = 32; i < 44; ++i) {
a[i] = 0;
}
for (int i = 0; i < 32; ++i) {
if (a[i] == 0) continue;
for (int j = 0; j < 13; ++j) {
a[i + j] ^= gen[j];
}
}
for (int i = 32; i < 44; ++i) {
cout << a[i];
}
cout << endl;
return 0;
}
当输入为 32 个 '0' 时，程序输出 12 个 0。（ ）
程序运行结束后，数组 a 中下标从 0 到 31 的元素一定全部为 0。（ ）
若将第 12—14 行（为 a[32] 到 a[43] 补 0 的循环）删除，会改变程序输出的结果。（ ）
关于第 6 行定义的数组 gen，下列说法正确的是（ ）。
该程序实现的功能，最准确的说法是（ ）。
若把第 16 行 if (a[i] == 0) continue; 删除，说法正确的是（ ）。
#include <iostream>
using namespace std;
int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];
int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}
int main() {
cin >> n >> m;
for (i = 1; i <= n; i++) cin >> a[i];
t = 0;
pw[0] = 1;
for (i = 1; i <= 24; i++) pw[i] = pw[i - 1] * 2;
for (i = 1; i <= 100000; i++)
if (pw[t + 1] >= i) lg[i] = t;
else { t++; lg[i] = t; }
for (i = 1; i <= n; i++) {
dp[i][0] = a[i];
}
for (j = 1; j <= lg[n]; j++) {
for (i = 1; i + pw[j] - 1 <= n; i++) {
dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]);
}
}
for (i = 1; i <= m; i++) {
cin >> L >> R;
cout << gcd(dp[L][lg[R - L + 1]], dp[R - pw[lg[R - L + 1]] + 1][lg[R - L + 1]]) << endl;
}
return 0;
}
当 n=5，a={4,2,6,3,3}，且仅有一次查询 L=2,R=5 时，输出为 1。（ ）
当某次查询的区间长度为 1（即 L=R）时，该次查询的输出一定等于 a[L]。（ ）
任意一次查询的输出结果一定不小于该查询区间内的最小值。（ ）
对于 j≥1，数组 dp[i][j] 保存的是（ ）。
若把一次求最大公约数的运算视为 O(1)，则第 17—22 行建表过程的时间复杂度为（ ）。
设 x 为一次查询的区间长度（即 x=R−L+1），则使得 lg[x] = 5 的 x 的取值范围是（ ）。
#include <iostream>
using namespace std;
int n, fa[100007], f[100007], ans;
int main() {
cin >> n;
for (int i = 2; i <= n; ++i) {
cin >> fa[i];
}
for (int i = n; i >= 2; --i) {
if (f[fa[i]] + f[i] + 1 > ans) {
ans = f[fa[i]] + f[i] + 1;
}
if (f[i] + 1 > f[fa[i]]) {
f[fa[i]] = f[i] + 1;
}
}
cout << ans << endl;
return 0;
}
当 n=5，f**a[2]∼f**a[5]={1,2,3,4} 时，程序输出 4。（ ）
程序输出前，f[1] 的值一定等于 ans 的值。（ ）
将第 10—12 行与第 13—15 行两个 if 语句的顺序交换后，程序输出结果不受影响。（ ）
程序输出的 ans 表示的是（ ）。
当 n=7，f**a[2]∼f**a[7]={1,1,2,2,3,3} 时，输出为（ ）。
当 n=10，满足输出为 9 的合法输入种类数为（ ）。
完 完善程序（共 10 题，共 0 分）
#include <iostream>
constexpr int N = 200005;
constexpr int M = 400005;
int n, m, s, t;
int h[N], e[M << 1], ne[M << 1], w[M << 1], idx;
int q[N], d[N], c[N];
void add(int a, int b, int z) {
e[idx] = b;
w[idx] = z;
ne[idx] = h[a];
h[a] = idx++;
}
int main() {
std::cin >> n >> m >> s >> t;
for (int i = 1; i <= n; i++)
h[i] = d[i] = c[i] = -1;
for (int i = 0; i < m; i++) {
int a, b;
char op[2];
std::cin >> a >> b >> op;
int z = /* ① */;
add(a, b, z);
add(b, a, z);
}
int hh = 0, tt = 0;
int p = 0, ng = 0, ok = 1;
q[tt++] = s;
d[s] = c[s] = 0;
while (/* ② */) {
int x = q[hh++];
for (int i = h[x]; i != -1; i = ne[i]) {
int y = e[i];
if (w[i] > 0) p = 1;
if (w[i] < 0) ng = 1;
if (d[y] == -1) {
d[y] = /* ③ */;
c[y] = c[x] ^ 1;
q[tt++] = y;
} else if (/* ④ */)
ok = 0;
}
}
if (d[t] == -1) {
std::cout << -1;
return 0;
}
if (!p || !ng) {
std::cout << d[t];
return 0;
}
if (/* ⑤ */) std::cout << 0;
else std::cout << 1;
return 0;
}
①处应填（ ）。
②处应填（ ）。
③处应填（ ）。
④处应填（ ）。
⑤处应填（ ）。
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main() {
int n, m;
cin >> n >> m;
vector<ll> x(n), c(n);
for (int i = 0; i < n; i++) {
cin >> x[i];
c[i] = /* ① */;
}
vector<string> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> s(n, -1);
vector<ll> q(m, 0);
ll C = 0, S = 0;
for (int i = 0; i < n; i++) {
C -= c[i];
for (int j = 0; j < m; j++) {
if (a[i][j] == 'A') q[j]--;
else q[j]++;
}
}
for (int j = 0; j < m; j++) S += abs(q[j]);
ll ans = C + S;
ull best = 0, lst = 0;
for (ull mask = 1; mask < (1ULL << n); mask++) {
ull g = /* ② */;
ull d = g ^ lst;
int k = /* ③ */;
C -= /* ④ */;
for (int j = 0; j < m; j++) {
ll old = q[j];
int v = (a[k][j] == 'A' ? 1 : -1);
q[j] -= 2ll * s[k] * v;
S += abs(q[j]) - abs(old);
}
s[k] = -s[k];
if (C + S > ans) {
ans = C + S;
best = g;
}
lst = g;
}
for (int i = 0; i < n; i++) {
if ((best >> i) & 1) s[i] = 1;
else s[i] = -1;
}
string res(m, 'A');
for (int j = 0; j < m; j++) {
ll v = 0;
for (int i = 0; i < n; i++) {
if (a[i][j] == 'A') v += s[i];
else v -= s[i];
}
if (/* ⑤ */) res[j] = 'A';
else res[j] = 'B';
}
①处应填（ ）。
②处应填（ ）。
③处应填（ ）。
④处应填（ ）。
⑤处应填（ ）。