该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

1. 执行下列代码后，cnt的值是（ ）

int x = 2026, cnt = 0;
while(x){
  x &= x - 1;
  cnt++;
}

{{ select(1) }}

• 6
• 7
• 11
• 8

2. 用权值{1, 2, 3, 4, 5, 6, 7, 8}构造哈夫曼树，其带权路径长度是（ ） {{ select(2) }}

• 108
• 96
• 99
• 102

3. 把1到1000的所有整数按十进制写出，数字"1"总共出现了多少次（ ） {{ select(3) }}

• 300
• 271
• 301
• 320

4. 将5封信随机装入5个写好地址的信封（每封一个），恰好有2封装对的方案数是（ ） {{ select(4) }}

• 44
• 24
• 10
• 20

5. $3^{2026} \bmod 100$的值是（ ） {{ select(5) }}

• 29
• 9
• 43
• 81

6. 有5堆石子排成一行，重量依次为4, 1, 3, 2, 5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ） {{ select(6) }}

• 36
• 35
• 34
• 33

7. 树状数组维护长度n=16的序列。查询前缀和sum(11)与单点修改add(3, x)分别需要访问树状数组中多少个下标（ ） {{ select(7) }}

• 3和4
• 4和4
• 3和5
• 4和3

8. 有向无环图G顶点集为{1, 2, 3, 4}，边集为{(1, 2), (1, 3)}，顶点4与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ） {{ select(8) }}

• 12
• 8
• 4
• 6

9. 某分治算法满足$T(n) = T(n/3) + T(2n/3) + \Theta(n)$，$T(1) = O(1)$，则$T(n)$是（ ） {{ select(9) }}

• $\Theta(n \log n)$
• $\Theta(n^2)$
• $\Theta(n^{1.5})$
• $\Theta(n)$

10. 无根树含9个结点（编号为1—9），边集为{(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (6, 7), (7, 8), (5, 9)}。该树的直径（以边数计）与重心分别是（ ） {{ select(10) }}

• 直径6，重心为结点3
• 直径7，重心为结点2
• 直径8，重心为结点1
• 直径7，重心为结点1

11. 一张有向图缩点后得到的有向无环图含6个顶点，其中入度为0的顶点有3个、出度为0的顶点有4个。为使原图变成强连通图，至少需要添加多少条有向边（ ） {{ select(11) }}

• 7
• 6
• 4
• 3

12. 含6个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ） {{ select(12) }}

• 42
• 429
• 132
• 720

13. 字符串S="ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ） {{ select(13) }}

• 4
• 6
• 7
• 5

14. 用归并排序统计逆序对，合并部分的核心代码为

//归并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统计出的结果是（ ） {{ select(14) }}

• 完全不变
• 变为原来的两倍
• 变为满足$i < j$且$a[i] >= a[j]$的数对个数
• 变为原来的一半

15. 执行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;
}

{{ select(15) }}

• 576
• 376
• 976
• 176

16. 当输入为32个'0'时，程序输出12个0。（ ） {{ select(16) }}

• True
• False

17. 程序运行结束后，数组a中下标从0到31的元素一定全部为0。（ ） {{ select(17) }}

• True
• False

18. 若将第12～14行（为a[32]到a[43]补0的循环）删除，会改变程序输出结果。（ ） {{ select(18) }}

• True
• False

19. 关于第6行定义的数组gen，下列说法正确的是（ ） {{ select(19) }}

• gen共有12个元素，表示一个12位的除数
• gen共有13个元素，表示一个13位的被除数
• gen共有13个元素，其中gen[0]是除数的最高位
• gen共有13个元素，其中gen[12]是除数的最高位

20. 该程序实现的功能，最准确的说法是（ ） {{ select(20) }}

• 将输入的32位串看成二进制数M，输出M与13位二进制数1100000001111按位异或的结果
• 将输入串视为32位二进制数M，在其后补12个0（即计算$M \times 2^{12}$），再对它用1100000001111作模2除法求余数，并输出12位余数
• 对输入的32位串逐位取反并输出结果
• 统计输入串中1的个数，并把该个数用12位二进制表示后输出

21. 若将第16行if(a[i] == 0) continue;删除，说法正确的是（ ） {{ select(21) }}

• 程序输出的结果不会改变
• 可能造成程序运行错误
• 程序能够正常输出一个12位'0'/'1'串，但是输出结果与输入的s无关
• 程序运行结束后，a[0]的值一定为0

22. 当n=5，a={4, 2, 6, 3, 9}，且仅有一次查询L=2、R=5时，输出为1。（ ） {{ select(22) }}

• True
• False

23. 当某次查询的区间长度为1（即L=R）时，这次查询的输出一定等于a[L]。（ ） {{ select(23) }}

• True
• False

24. 任意一次查询的输出结果一定不小于该查询区间内的最小值。（ ） {{ select(24) }}

• True
• False

25. 对于j≥1，数组dp[i][j]保存的是（ ） {{ select(25) }}

• 从a[i]开始连续j个数的最大公约数
• 从a[i]开始连续$2^j$个数的最大公约数
• a[i]与a[j]的最大公约数
• 从a[1]到a[i]的最大公约数

26. 若把一次求最大公约数的运算视为O(1)，则第17～22行建表过程的时间复杂度为（ ） {{ select(26) }}

• $\Theta(n)$
• $\Theta(n \log n)$
• $\Theta(n^2)$
• $\Theta(mn)$

27. 设x为一次查询的区间长度（即x=R−L+1），则使得lg[x]=5的x的取值范围是（ ） {{ select(27) }}

• [16, 31]
• [17, 32]
• [32, 63]
• [33, 64]

28. 当n=5，fa[2]～fa[5]={1, 2, 3, 4}时，程序输出4。（ ） {{ select(28) }}

• True
• False

29. 程序输出前，f[1]的值一定等于ans的值。（ ） {{ select(29) }}

• True
• False

30. 将第10～12行与第13～15行两个if语句的顺序交换后，程序的输出结果不受影响。（ ） {{ select(30) }}

• True
• False

31. 程序输出的ans表示的是（ ） {{ select(31) }}

• 树中距离最远的两个结点之间路径所经过的边数
• 根结点1到最远叶子结点之间路径所经过的边数
• 树中叶子结点的个数
• 所有结点的父结点编号之和

32. 当n=7，fa[2]～fa[7]={1, 1, 2, 2, 3, 3}时，输出为（ ） {{ select(32) }}

• 2
• 3
• 4
• 5

33. 当n=10，满足输出为9的合法输入种类数为（ ） {{ select(33) }}

• 0
• 9
• 256
• 512

34. ①处应填（ ） {{ select(34) }}

• op[0]=='+' ? 0 : 1
• op[0]=='+'
• op[0]=='+' ? 1 : -1
• op[0]=='-' ? 1 : 0

35. ②处应填（ ） {{ select(35) }}

• hh < n
• tt < n
• hh <= tt
• hh < tt

36. ③处应填（ ） {{ select(36) }}

• d[y] + 1
• d[x] + 1
• d[x]
• d[x] - 1

37. ④处应填（ ） {{ select(37) }}

• c[y] == c[x]
• w[i] == 1
• c[y] != c[x]
• d[y] + 1 != d[x]

38. ⑤处应填（ ） {{ select(38) }}

• ok && c[s] == c[t]
• ok && c[s] != c[t]
• !ok || c[s] == c[t]
• !ok && c[s] != c[t]

39. 处应填（ ） {{ select(39) }}

• 2 * x[i] - m
• -m + 2 * x[i] + 1
• m - 2 * x[i]
• m + 2 * x[i]

40. 处应填（ ） {{ select(40) }}

• mask | (mask >> 1)
• mask ^ (mask >> 1)
• mask & (mask >> 1)
• mask ^ ((mask >> 1) + 1)

41. ③处应填（ ） {{ select(41) }}

• __builtin_ctzll(d) + 1
• __builtin_popcountll(d)
• __builtin_ctzll(g)
• __builtin_ctzll(d)

42. ④处应填（ ） {{ select(42) }}

• 2ll * s[k] * c[k]
• s[k] * c[k]
• 2ll * (s[k] - c[k])
• 2ll * c[k]

43. ⑤处应填（ ） {{ select(43) }}

• v >= (n & 1)
• v > (n & 1)
• v + (n & 1) >= 0
• v * (n & 1) >= 0