普及组

1. 时间复杂度O(n log n)的算法是? {{ select(1) }}

• 冒泡排序
• 快速排序(期望)
• 计数排序
• 插入排序

2. 以下哪种排序算法是稳定的? {{ select(2) }}

• 选择排序
• 堆排序
• 快速排序
• 归并排序

3. 二分查找使用的前提条件是? {{ select(3) }}

• 数组中无重复值
• 数组已按某种顺序排列
• 元素均为整数
• 长度为2的幂

4. 下列哪种数据结构最适合实现广度优先搜索(BFS)? {{ select(4) }}

• 栈(Stack)
• 队列(Queue)
• 优先队列(Priority Queue)
• 并查集(Disjoint Set Union)

5. 位运算中，要将变量x的二进制表示的第k位(从0开始计数)清零，应使用? {{ select(5) }}

• x|(1<<k)
• x&(1<<k)
• x~(1<<k)
• x∧(1<<k)

6. 求1到n的和，在C++中溢出风险最低的写法是? {{ select(6) }}

• n*(n+1)/2
• (long long)n*(n+1)/2
• (n+1)*n/2
• 循环相加

7. 对于一个边权非负的图，求单源最短路，最常用的高效算法是? {{ select(7) }}

• Floyd-Warshall
• Bellman-Ford
• Dijkstra
• SPFA

8. 哈希表的平均查找时间复杂度是? {{ select(8) }}

• O(1)
• O(log n)
• O(n)
• O(n log n)

9. 判断一个年份year是否为闰年的正确条件是? {{ select(9) }}

• 能被4整除
• 能被4整除且不能被100整除，或者能被400整除
• 能被100整除
• 能被400整除

10. 在C/C++中，数组越界访问最可能导致? {{ select(10) }}

• 编译错误
• 链接错误
• 未定义行为(Undefined Behavior)
• 一定会产生段错误(Segmentation Fault)

11. 同时使用路径压缩与按秩合并优化的并查集，其单次操作的均摊时间复杂度是? {{ select(11) }}

• O(log n)
• O(α(n))
• O(1)严格常数
• O(n)

12. 在模m的意义下，整数a存在乘法逆元的充要条件是? {{ select(12) }}

• a为质数
• m为质数
• gcd(a,m)=1
• a<m

13. 快速幂(或称二进制幂)算法计算a^n的时间复杂度是? {{ select(13) }}

• O(log n)
• O(n)
• O(√n)
• O(log²n)

14. 下列哪种排序算法不依赖于元素之间的比较? {{ select(14) }}

• 归并排序
• 堆排序
• 快速排序
• 计数排序

15. 对于一个无权图，求单源最短路应该使用? {{ select(15) }}

• Dijkstra
• BFS
• Floyd-Warshall
• Bellman-Ford

16. "二分答案"技术应用的常见前提是? {{ select(16) }}

• 问题可以哈希
• 数据可以离散化
• 判定函数具有单调性
• 图是连通的

17. 在C++中比较两个浮点数a和b是否相等，推荐的做法是? {{ select(17) }}

• 直接使用==
• 转换为字符串比较
• 取整后比较
• 设定一个极小的精度值eps进行比较

18. C++中，有符号整数(如int)发生溢出，其行为是? {{ select(18) }}

• 未定义行为
• 定义为回绕(wrap-around)
• 抛出异常
• 自动变为0

19. 在C++ STL中，lower_bound函数在一个升序数组中的含义是? {{ select(19) }}

• 查找第一个大于key的元素的位置
• 查找最后一个小于key的元素的位置
• 查找第一个大于或等于key的元素的位置
• 查找最后一个小于或等于key的元素的位置

20. 使用倍增法求最近公共祖先(LCA)，其预处理和单次查询的时间复杂度分别是? {{ select(20) }}

• 预处理O(n²),查询O(1)
• 预处理O(n),查询O(log n)
• 预处理O(n log n),查询O(1)
• 预处理O(n log n),查询O(log n)

21. 在二分查找或线段树中，计算区间[l,r]的中点，为避免l+r可能导致的整数溢出，最稳妥的写法是? {{ select(21) }}

• (l + r) / 2
• l + (r - l) / 2
• (l + r) >> 1
• (unsigned)(l + r) / 2

22. 在C++中，表达式int a = 3 / 2;执行后，变量a的值是? {{ select(22) }}

• 1.5
• 1
• 2
• 0

23. 在C++中，当使用cin >> var;后立即使用getline(cin, str);，为防止getline读到残留的换行符，常见的处理方法是? {{ select(23) }}

• fflush(stdin)
• cin.ignore()
• rewind(stdin)
• cin.setbuf(0)

24. 使用memset将一个int类型的数组a全部初始化为-1，下列说法正确的是? {{ select(24) }}

• memset(a, -1, sizeof a)可以正确工作，但不推荐
• memset(a, 1, sizeof a)可以将数组元素初始化为1
• 使用fill(a, a + n, -1)是更安全通用的方法
• memset(a, -1, n)语法错误或逻辑错误

25. 在C++11的范围for循环中，如果要修改容器内的元素，正确的方式是? {{ select(25) }}

• for(auto x : v) { x = ...; }
• for(auto& x : v) { x = ...; }
• for(const auto x : v) { x = ...; }
• 在循环内修改，然后v.push_back(x)

26. 使用printf函数输出一个long long类型的变量，应使用的格式化占位符是? {{ select(26) }}

• %d
• %u
• %lld
• %ld

27. 判断一个整数x是奇数还是偶数，最快且对负数也正确的写法是? {{ select(27) }}

• x % 2 == 1
• x & 1
• x % 2
• x % 2 != 0

28. C++ STL中unordered_map的平均和最坏情况下的查找时间复杂度分别是? {{ select(28) }}

• 平均O(1)，最坏O(n)
• 平均O(log n)，最坏O(log n)
• 平均O(1)，最坏O(1)
• 平均O(n)，最坏O(n)

29. 在C/C++中，对一个负数进行左移，或者左移的位数超过该类型本身的位数，其行为是? {{ select(29) }}

• 定义良好
• 未定义行为
• 由具体实现定义
• 产生运行时报错

30. 在同一个程序中混用cin/cout和scanf/printf，为了避免IO错乱并提升性能，推荐的做法是? {{ select(30) }}

• 直接混用，没有问题
• 关闭同步并解绑输入输出流(ios::sync_with_stdio(false); cin.tie(nullptr);)
• 只需要关闭同步
• 只需要解绑输入输出流

31. 需要支持"区间批量增加一个值"和"查询单个点的值"两种操作，最简单高效的数据结构是? {{ select(31) }}

• 树状数组
• 线段树(带懒标记)
• 差分数组
• 可持久化线段树

32. 需要支持"多次查询区间最小值"和"多次对区间批量增加一个值"两种操作，应选择? {{ select(32) }}

• 并查集
• 堆
• 线段树(带懒标记)
• 稀疏表(Sparse Table)

33. 判断一个图是否为二分图，通常应使用? {{ select(33) }}

• 拓扑排序
• DFS/BFS染色法
• Tarjan算法求强连通分量
• 最小生成树算法(Prim/Kruskal)

34. 对于大量字符串，需要高效地查找其中哪些字符串以某个特定前缀开头，最佳的数据结构是? {{ select(34) }}

• KMP算法
• Trie树(字典树)
• Z算法
• 后缀数组

35. 一个队列在n次入队和出队操作后，保证最坏情况下的单次操作均摊时间复杂度为O(1)，可以如何实现? {{ select(35) }}

• 使用两个栈实现队列
• 使用循环数组实现队列
• 使用链表实现队列
• 使用二叉堆实现队列

36. 给定两个不大于10⁹⁹的整数a和b，求它们的最大公约数gcd(a,b)，应选择? {{ select(36) }}

• 暴力枚举公共因子
• 分解质因数
• 欧几里得算法
• 扩展欧几里得算法

37. 在一个图中，边权可能为负，但保证没有负权环。求单源最短路应选择? {{ select(37) }}

• Dijkstra算法
• Bellman-Ford算法
• Floyd-Warshall算法
• SPFA算法

38. 在竞赛中，需要将一个大数组(如int dist[MAXN])初始化为一个"极大值"(表示无穷远)，最稳妥的写法是? {{ select(38) }}

• memset(dist, 0x3f, sizeof(dist))
• fill(dist, dist + n, INF)(其中INF是一个合适的常量)
• memset(dist, INF, sizeof(dist))
• new动态分配后不进行初始化

39. 当模数p是一个质数，且a ≡ 0 (mod p)时，a在模p意义下的乘法逆元? {{ select(39) }}

• 存在
• 不存在
• 取决于a是否为奇数
• 需要对a开根号

40. 动态规划中的背包问题，如果每种物品可以无限次使用，这属于哪种背包模型? {{ select(40) }}

• 0/1背包
• 完全背包
• 多重背包
• 分组背包