提高组

1. A* 搜索算法通过 f(n) = g(n) + h(n) 来评估节点，其中启发函数 h(n) 的作用是？ {{ select(1) }}

• 计算从起点到节点n的实际代价
• 估计从节点n到终点的代价，且必须小于等于实际代价
• 记录节点n的父节点
• 节点n的深度

2. 在竞赛中，快速傅里叶变换（FFT）最主要的应用是？ {{ select(2) }}

• 求解线性方程组
• 高效计算大整数乘法或多项式乘法
• 排序浮点数数组
• 信号的频谱分析

3. 经典的Nim游戏中，判断先手必胜/必败状态的依据是？ {{ select(3) }}

• 所有石子堆数量的总和
• 所有石子堆数量的异或（XOR）和
• 石子堆数量的最大值
• 石子堆的数量是否为奇数

4. Manacher算法被用来解决什么问题？ {{ select(4) }}

• 线性时间内求解字符串的最长公共子序列
• 线性时间内求解字符串的最长回文子串
• 对字符串进行字典序排序
• 在一个文本串中查找多个模式串

5. 在现代C++中，std::move 函数的主要作用是？ {{ select(5) }}

• 移动内存中的数据块
• 复制一个对象
• 将一个左值强制转换为右值引用，以启用移动语义
• 交换两个对象的值

6. 中国剩余定理（Chinese Remainder Theorem）主要用于解决什么问题？ {{ select(6) }}

• 求解高次多项式的根
• 求解一组线性同余方程
• 计算组合数 C(n, m)
• 判断一个大数是否为质数

7. 求解二分图最大匹配问题的经典算法是？ {{ select(7) }}

• Dijkstra 算法
• Tarjan 算法
• 匈牙利算法
• Kruskal 算法

8. 相较于 const，使用 constexpr 声明常量的主要优势是？ {{ select(8) }}

• constexpr 可以修饰函数
• constexpr 声明的常量保证在编译期被计算出来
• constexpr 只能用于整数类型
• constexpr 变量的内存占用更小

9. 容斥原理计算三个集合 A, B, C 的并集大小 |A∪B∪C| 的公式是？ {{ select(9) }}

• |A|+|B|+|C|
• |A|+|B|+|C| - |A∩B| - |A∩C|
• |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
• |A∩B|+|A∩C|+|B∩C| - |A∩B∩C|

10. Treap（树堆）是一种平衡二叉搜索树，它如何维持树的平衡？ {{ select(10) }}

• 通过红黑染色和旋转
• 通过严格限制左右子树的高度差
• 通过为每个节点分配一个随机优先级，并维持堆的性质
• 通过分裂和合并操作

11. "折半搜索"（Meet-in-the-middle）算法思想适用于解决什么样的问题？ {{ select(11) }}

• 搜索空间巨大但可以被分解为两个独立且规模减半的子问题
• 具有最优子结构性质的问题
• 数据呈现单调性的查找问题
• 所有顶点都需要被访问一次的图遍历问题

12. 在C++ Lambda表达式中，[=, &x] 表示的捕获方式是？ {{ select(12) }}

• 以引用方式捕获所有外部变量，但以值方式捕获x
• 以值方式捕获所有外部变量，但以引用方式捕获x
• 只捕获x，方式为值捕获
• 语法错误

13. 状态压缩动态规划（State Compression DP）通常在什么情况下使用？ {{ select(13) }}

• DP状态的某一维度数值很大
• DP状态的某一维度取值范围很小，可以用一个整数的二进制位表示
• DP转移方程非常复杂
• 问题是关于几何图形的

14. 卢卡斯定理（Lucas's Theorem）用于高效计算什么？ {{ select(14) }}

• 大数的阶乘模一个合数
• 组合数 C(n, m) 模一个质数 p，尤其当p很小时
• 费波那契数列的第n项
• 两个大数的最大公约数

15. C++的 std::bitset 相比于 bool 数组的主要优点是？ {{ select(15) }}

• 动态调整大小
• 极高的空间效率和支持快速位运算
• 可以存储任意类型
• 线程安全

16. 在二维计算几何中，向量 a 和 b 的叉积（Cross Product）的正负号可以用来判断？ {{ select(16) }}

• 两个向量的长度关系
• 两个向量的夹角大小
• 向量 b 相对于向量 a 的旋转方向（顺时针或逆时针）
• 两个向量是否平行

17. 一个2-SAT问题有解的充要条件是？ {{ select(17) }}

• 构造出的图是连通的
• 构造出的图是一个有向无环图（DAG）
• 对于任何变量 x，x 和其否定 ¬x 不在同一个强连通分量中
• 图中所有节点的入度都等于出度

18. 在现代C++中，推荐使用 nullptr 而非 NULL 的主要原因是？ {{ select(18) }}

• nullptr 是一个关键字，输入更快
• nullptr 有明确的指针类型，可以避免函数重载时的歧义
• NULL 即将被废弃
• nullptr 可以指向任何类型的对象

19. 莫队算法（Mo's Algorithm）是一种用于处理区间查询的离线算法，其核心思想是？ {{ select(19) }}

• 对查询区间使用分块数据结构
• 对查询进行特殊排序，通过移动左右端点来高效地得到所有查询的答案
• 将查询转化为前缀和的差
• 使用主席树记录历史版本

20. 高斯消元法（Gaussian Elimination）主要用于求解？ {{ select(20) }}

• 微分方程
• 线性方程组
• 非线性规划问题
• 图的着色问题

21. 树形动态规划（Tree DP）在计算时，信息传递的常见方向是？ {{ select(21) }}

• 从根节点向叶子节点传递
• 在兄弟节点之间传递
• 通过一次深度优先搜索，信息从子节点向父节点合并
• 随机选择节点进行更新

22. 对一个已排序的 std::vector 调用 std::unique 函数后，其返回值是？ {{ select(22) }}

• vector中不重复元素的个数
• 一个指向最后一个不重复元素之后位置的迭代器
• 一个布尔值，表示是否存在重复元素
• void

23. 莫比乌斯反演（Möbius Inversion）在数论中是一种重要的技巧，它建立了什么关系？ {{ select(23) }}

• 一个函数与其在所有质数幂次处取值的关系
• 一个函数 f(n) 与另一个函数 g(n) = Σ_{d|n} f(d) 之间的关系
• 一个数与其质因数个数的关系
• 组合数与阶乘的关系

24. 可持久化数据结构（Persistent Data Structure）最大的特点是？ {{ select(24) }}

• 数据可以被永久保存在硬盘上
• 在修改数据时，能够保留其历史版本，并可以访问和查询
• 对所有操作都提供常数时间复杂度
• 只能插入，不能删除

25. 一个64位无符号整数类型 (unsigned long long) 能表示的最大值是？ {{ select(25) }}

• 2^63 - 1
• 2^63
• 2^64 - 1
• 2^64

26. 差分约束系统（Difference Constraints System）可以被转化成哪类图论问题来求解？ {{ select(26) }}

• 最大流问题
• 二分图匹配问题
• 单源最短路问题
• 最小生成树问题

27. 一个总是能给出正确结果，但运行时间不确定的随机化算法，被称为？ {{ select(27) }}

• 蒙特卡洛算法
• 拉斯维加斯算法
• 贪心算法
• 模拟退火算法

28. 笛卡尔树（Cartesian Tree）同时满足以下哪两种数据结构的性质？ {{ select(28) }}

• 完全二叉树和B+树
• 二叉搜索树（对键）和最小堆（对优先级）
• 哈希表和链表
• 数组和红黑树

29. 组合数学中的"插板法"（Stars and Bars）常用于解决哪类问题？ {{ select(29) }}

• n个不同物品的全排列
• 从n个不同物品中选k个的组合
• 将k个相同物品放入n个不同盒子的方案数
• 欧拉路径计数

30. 在C++模板元编程中，std::enable_if 的主要用途是？ {{ select(30) }}

• 提升模板函数的编译速度
• 根据模板参数的某些条件，决定一个模板是否参与重载决议（SFINAE）
• 启用C++11的特定新特性
• 强制进行内联优化

31. Z-算法（扩展KMP）计算出的Z数组，其中 Z[i] 的含义是？ {{ select(31) }}

• 字符串S的第 i 个后缀与整个S的最长公共子串长度
• 字符串S的第 i 个后缀与整个S的最长公共前缀长度
• 字符串S中长度为 i 的子串出现的次数
• 字符串S的反串

32. C++中的"严格别名规则"（Strict Aliasing Rule）指出？ {{ select(32) }}

• 一个变量只能有一个别名
• 只能使用&来创建引用，不能使用指针
• 通过不兼容类型的指针访问一个对象是未定义行为
• 全局变量必须在使用前声明

33. 欧拉定理（Euler's Totient Theorem）是费马小定理的推广，其内容是？ {{ select(33) }}

• 若 gcd(a, n)=1，则 a^n ≡ a (mod n)
• 若 gcd(a, n)=1，则 a^(n-1) ≡ 1 (mod n)
• 若 gcd(a, n)=1，则 a^φ(n) ≡ 1 (mod n)
• φ(ab) = φ(a)φ(b)

34. 霍夫曼编码（Huffman Coding）是一种经典的无损数据压缩算法，它利用了什么原理？ {{ select(34) }}

• 为出现频率高的字符分配更短的编码
• 将连续重复的字符进行压缩
• 将数据加密
• 丢弃不重要的信息

35. 在C++中，x & (x-1) 这个位运算操作可以实现什么功能？ {{ select(35) }}

• 将x最低位的1变为0
• 判断x是否为2的幂
• 计算x的二进制表示中1的个数（lowbit）
• 将x最高位的1变为0

36. 一个随机变量X的期望值E[X]，满足 E[X+Y] = E[X] + E[Y]，这个性质被称为？ {{ select(36) }}

• 期望的齐次性
• 期望的线性性质
• 全期望公式
• 马尔可夫不等式

37. Dancing Links X (DLX) 算法是解决哪类问题的最高效实现？ {{ select(37) }}

• 八皇后问题
• 线性规划问题
• 精确覆盖问题
• 任务调度问题

38. 解决n个盘子的汉诺塔（Tower of Hanoi）问题，其递归解法的时间复杂度是？ {{ select(38) }}

• O(n)
• O(n log n)
• O(n²)
• O(2^n)

39. 在C++中，std::atomic 类型的主要作用是？ {{ select(39) }}

• 保证变量的线程安全性
• 提高变量的访问速度
• 自动进行内存管理
• 实现多态

40. 在计算机图形学中，Bresenham算法主要用于？ {{ select(40) }}

• 绘制直线
• 计算多边形面积
• 进行图像压缩
• 实现3D渲染