cswork / OA打开练习工作台

OA 选择题 · 即时判分

OA 里的选择题，先在这里练。

621 道原创 OA 风格选择题，覆盖 CS 基础（数据结构与算法、操作系统、数据库、网络、并发、面向对象、Linux 命令行、Git、计算机体系结构、Web 安全、设计模式、Web 前端、机器学习）、读代码（时间复杂度、Python、JavaScript、Java、C++、SQL、NumPy）和数学统计（概率、逻辑推理、统计）。读代码题里问输出的（复杂度题和标为未定义行为的除外），答案都是实际运行得出的。提交后立即判分并给出解析；答过的题按 1、3、7、21 天的间隔回来复习。CPU 调度、页面置换、TCP 和拥塞控制的计算题，可以用操作系统与网络模拟器逐步核对。

只显示：数据结构与算法 · 查看全部科目

复习
86 道题
  1. 在长度为 n 的动态数组（如 Python list）下标 0 处插入一个元素，时间复杂度是？
  2. 动态数组满了以后按倍数扩容（比如容量翻倍），而不是每次固定多开 100 个位置，主要是为了什么？
  3. 用链地址法的哈希表里有 n 个键、m 个桶，负载因子 α = n/m。假设哈希函数把键均匀打散，一次查找失败（键不存在）的期望代价是？
  4. 关于哈希表，下面哪些说法正确？（多选）
  5. 在 Python 里拼一个很长的字符串，为什么推荐先把片段放进列表再 "".join(parts)，而不是循环里 s += part？
  6. 只含小写字母的两个长度为 n 的字符串，用一个大小为 26 的计数数组判断它们是否互为字母异位词。时间和额外空间分别是？
  7. 找两数之和等于 target 的对撞双指针（和太小就左指针右移，太大就右指针左移），在什么前提下才正确？
  8. 求「和不超过 K 的最长子数组」时，常用的滑动窗口是：右端每次扩一格，和超过 K 就收缩左端。这个做法依赖什么条件？
  9. 前缀和数组 P 定义为 P[0] = 0，P[i] = a[0] + … + a[i-1]。闭区间 a[l..r] 的和等于？
  10. 合并一组可能重叠的区间，标准做法和时间复杂度是？
  11. 对长度为 n 的数组做 q 次「给 a[l..r] 全部加 v」的操作，最后只读一次整个数组。用差分数组，总时间是？
  12. lo, hi = 0, len(a)；while lo < hi：mid = (lo + hi) // 2；若 a[mid] < x 则 lo = mid + 1，否则 hi = mid。对有序数组 a，循环结束时 lo 是什么？
  13. 「二分答案」（在答案的取值范围上二分，每次用 check(mid) 判断可行）需要满足什么条件？
  14. 在 Java 或 C++ 里，为什么常写 mid = lo + (hi - lo) / 2，而不是 mid = (lo + hi) / 2？
  15. 用「自底向上」的方法（从最后一个非叶子节点开始依次下沉）把 n 个无序元素建成二叉堆，时间复杂度是？
  16. 要在数据流里始终保留最大的 k 个数，用堆的标准做法是？
  17. 下列场景里，哪一个最适合用单调栈？
  18. 从一组区间中选出最多个互不重叠的区间，正确的贪心策略是每次选？
  19. 硬币面值是 {1, 3, 4}，要凑出 6。「每次拿不超过剩余金额的最大硬币」的贪心用几枚？最少需要几枚？
  20. Floyd 判圈算法（慢指针一次一步，快指针一次两步）中，两个指针在环里相遇后，怎样找到环的入口？
  21. 一个同时保存 head 和 tail 指针的单链表，下面哪个操作不是 O(1)？
  22. 链表题里常在头节点前加一个哑节点（dummy），它主要解决什么问题？
  23. 在 n 个节点、高度为 h 的二叉树上做递归 DFS，额外空间（调用栈）是？
  24. 满二叉树（每个节点要么有 0 个、要么有 2 个孩子）如果有 n 个内部节点，它有几个叶子？
  25. 要自底向上算出每棵子树的高度，需要先处理完左右子树再处理当前节点。这对应哪种 DFS 顺序？
  26. 「二叉树中任意两点间的最大路径和」：递归函数返回给父节点的值应该是什么？（L、R 是左右孩子返回的值）
  27. 统计二叉树里和为 target 的向下路径数，常用做法是 DFS 时用哈希表记录根到当前节点路径上各前缀和出现的次数。为什么回溯（离开节点）时要把当前前缀和的计数减 1？
  28. 节点值互不相同时，下面哪些遍历组合能唯一确定一棵二叉树？（多选）
  29. 由前序和中序重建二叉树时，先建一个「值 → 中序下标」的哈希表，带来的改变是？
  30. 验证二叉搜索树时，只检查每个节点满足「左孩子 < 当前节点 < 右孩子」为什么不够？
  31. 把 1, 2, …, n 按顺序插入一棵不做平衡的普通二叉搜索树，树高（边数）是多少？
  32. 从 BST 中删除一个有两个孩子的节点，标准做法是？
  33. 在无权网格上求从起点到终点的最少步数，哪种搜索直接给出答案？
  34. BFS 为什么通常在把格子加入队列时就标记为已访问，而不是出队时才标记？
  35. R×C 网格里有 k 个源点，要求每个格子到最近源点的距离。高效的做法是？
  36. 并查集同时使用路径压缩和按秩（或按大小）合并后，每次操作的均摊时间是？
  37. 用并查集判断无向图有没有环：依次处理每条边 (u, v)，什么时候说明出现了环？
  38. n 个顶点、处理完 m 条边后，并查集中成功合并（两端原本不在同一集合）的次数为 s。连通分量有几个？
  39. 用 Kahn 算法（反复取出入度为 0 的点）做拓扑排序，结束时输出的顶点数少于 n，说明什么？
  40. 基于 DFS 的拓扑排序，结果是哪个顺序？
  41. 有向图有负权边但没有负权环，求单源最短路，应该用哪个算法？
  42. 边权只有 0 和 1 的图上做「0-1 BFS」，用双端队列时边的处理规则是？
  43. Kruskal 算法按权值从小到大考虑每条边，什么情况下跳过这条边？
  44. 一个有 V 个顶点的连通无向带权图，下面哪些说法正确？（多选）
  45. 用回溯生成 n 个不同元素的所有子集，每个子集都复制成一个列表输出。总时间是？
  46. 生成 [1, 1, 2] 的不重复全排列，常用规则是：先排序，在同一层里遇到 nums[i] == nums[i-1] 且 nums[i-1] 没有被使用时跳过 nums[i]。这条规则保证了什么？
  47. 回溯生成 n 对括号的所有合法组合时，什么条件下可以追加一个右括号「)」？
  48. 3 对括号能组成多少个合法（配对正确）的括号串？
  49. N 皇后问题中，位于 (r1, c1) 和 (r2, c2) 的两个皇后恰好在同一条斜线上，当且仅当？
  50. 组合总和问题里，候选数都是正数并且已经升序排序。当 candidates[i] 大于剩余目标值时，为什么可以直接 break，而不只是跳过这一个？
  51. 哪两条性质让一个问题适合用动态规划？
  52. 关于记忆化搜索（自顶向下）和递推（自底向上），哪些说法正确？（多选）
  53. 在 3×3 的格子里，从左上角的格子走到右下角的格子，每步只能向右或向下，一共有多少条路径？
  54. 网格 DP 压缩成一维数组时，按 j 从左到右执行 dp[j] = dp[j] + dp[j-1]。赋值之前，dp[j] 和 dp[j-1] 分别代表什么？
  55. 0/1 背包压成一维时写作 for w in range(W, wt - 1, -1): dp[w] = max(dp[w], dp[w - wt] + val)。为什么容量要从大到小遍历？
  56. 0/1 背包的 O(n·W) 动态规划通常被称为「伪多项式时间」，原因是？
  57. 硬币 coins = [1, 2]，金额 3。执行 ways = [1, 0, 0, 0]；for c in coins: for a in range(c, 4): ways[a] += ways[a - c]。ways[3] 是多少？
  58. 最长递增子序列的 O(n log n) 解法维护一个数组 tails。tails[k] 表示什么？
  59. 数组 [8, 3, 6, 1, 7, 4, 9, 2] 的最长严格递增子序列长度是？
  60. 把 "abc" 变成 "yabd" 的编辑距离（插入、删除、替换各算一步）是？
  61. 求两个长度为 m、n 的字符串的最长公共子序列长度，二维 DP 需要 O(m·n) 空间。只要长度、不要具体子序列时，空间最少能压到多少？
  62. 用「中心扩展」找回文子串，长度为 n 的字符串一共要从多少个中心向两边扩展？
  63. 区间 DP 求最长回文子序列：dp[i][j] 依赖 dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1]。下面哪种填表顺序是对的？
  64. 打家劫舍的环形版本（首尾两间房相邻，不能同时偷）通常怎么做？
  65. 股票买卖含一天冷冻期，用三个状态：hold（持有）、sold（今天刚卖出）、rest（不持有且不在冷冻期）。今天买入应该从昨天的哪个状态转移过来？
  66. 股价依次是 [6, 2, 9, 1, 4, 8]，可以买卖任意多次，但手里最多持有一股（卖出后才能再买）。最大利润是？
  67. 「最多交易 k 次」的股票问题，n 天价格。当 k ≥ n / 2 时可以怎么处理？
  68. 带权区间调度（选互不重叠的区间使权值和最大）：区间按结束时间排序后，dp[i] = max(dp[i-1], w[i] + dp[p(i)])。p(i) 是什么，整体复杂度是多少？
  69. 给一组会议时间段，最少需要几间会议室？下面哪个说法正确？
  70. 两人轮流从数组两端取数，都按最优策略。区间 DP 写作 dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1])。dp[i][j] 表示什么？
  71. 「矩阵中的最长递增路径」用带记忆化的 DFS 求解，为什么不需要 visited 数组防止走回头路？
  72. 实现一个支持 push、pop、top 和 O(1) getMin 的栈，常见做法是？
  73. Python 里做 BFS 的队列，为什么用 collections.deque 而不是 list 加 pop(0)？
  74. 要让 LRU 缓存的 get 和 put 都是 O(1)，标准结构是？
  75. LRU 缓存里的链表为什么要用双向链表，单向的不行吗？
  76. 字典树（Trie）里已经存了 N 个单词，查找一个长度为 L 的单词是否存在，时间是？
  77. 为什么把二叉树序列化成「带空节点标记（如 #）的前序遍历」就足以还原，而普通的前序遍历不行？
  78. 对正整数 x，x & (x - 1) == 0 成立意味着什么？
  79. [7, 3, 5, 3, 7] 中所有数的按位异或结果是？
  80. 在补码表示下，x & -x 的结果是什么？以 x = 12 为例。
  81. 「能否跳到最后一个下标」（a[i] 是从 i 出发最多能跳的步数）：贪心从左到右扫描，记录目前能到达的最远下标 far。什么时候可以判定跳不到？
  82. 回溯枚举字符串 s（长度 n）的所有回文划分时，先预处理一张表 pal[i][j]（s[i..j] 是否为回文），带来的改变是？
  83. 在网格里用回溯找单词时，为什么要在递归前把当前格子标记为「使用中」，返回后再恢复？
  84. 把 n 个互不相同的有序数建成一棵高度平衡的 BST（递归时传下标区间，不切片）。每个子区间选谁当根，总时间是多少？
  85. 二叉树的直径（任意两节点间最长路径的边数）一定经过根节点吗？
  86. 带手续费的股票买卖：每天写 hold = max(hold, cash - p)；cash = max(cash, hold + p - fee)，第二行用到的是刚更新过的 hold。为什么这样原地更新不会出错？

作答记录只保存在这台设备的浏览器里；登录后再打开本页，会存进账号。