OA 选择题 · 即时判分

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

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

只显示：复杂度 · 查看全部科目

66 道题

下面代码的时间复杂度是？（n = len(a)，取最紧的界）
```
def reverse_copy(a):
    out = []
    for x in a:
        out.insert(0, x)
    return out
```
- O(1)
- O(n log n)
- O(n²)
- O(n)
下面代码的时间复杂度是？（取最紧的界）
```
def build(n):
    a = []
    for i in range(n):
        a.append(i)
    return a
```
- O(n²)
- O(n log n)
- O(log n)
- O(n)
下面代码的时间复杂度是？（n = len(a)，取最紧的界）
```
def normalize(a):
    return [x / max(a) for x in a]
```
- O(n log n)
- O(1)
- O(n²)
- O(n)

下面代码在最坏情况下的时间复杂度是？（n = len(a)）

def count_repeats(a):
    seen = []
    repeats = 0
    for x in a:
        if x in seen:
            repeats += 1
        else:
            seen.append(x)
    return repeats

O(n²)
O(n log n)
O(n³)
O(n)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def has_pair(a, target):
    seen = set()
    for x in a:
        if target - x in seen:
            return True
        seen.add(x)
    return False

O(1)
期望 O(n)
O(n²)
O(n log n)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def most_common(a):
    best = None
    for x in a:
        if best is None or a.count(x) > a.count(best):
            best = x
    return best

O(n³)
O(n log n)
O(n²)
O(n)

words 有 n 个词，vocab 是一个有 m 个键的 dict。时间复杂度是？

def count_known(words, vocab):
    known = 0
    for w in words:
        if w in list(vocab):
            known += 1
    return known

O(n + m)
O(n·m)
O(n)
O(m log n)

下面代码在 s 是回文时的时间复杂度是？（n = len(s)）
```
def is_pal(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and is_pal(s[1:-1])
```
- O(n log n)
- O(2^n)
- O(n)
- O(n²)

下面 Java 方法的时间复杂度是？

static String repeatX(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s += "x";
    }
    return s;
}

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

a 里都是非负整数，k ≥ 0。下面代码的时间复杂度是？（n = len(a)）

def longest(a, k):
    best = lo = total = 0
    for hi in range(len(a)):
        total += a[hi]
        while total > k:
            total -= a[lo]
            lo += 1
        best = max(best, hi - lo + 1)
    return best

O(n log n)
O(n·k)
O(n)
O(n²)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def count_pairs(a, t):
    a.sort()
    i, j, count = 0, len(a) - 1, 0
    while i < j:
        if a[i] + a[j] <= t:
            count += j - i
            i += 1
        else:
            j -= 1
    return count

O(n²)
O(n log n)
O(log n)
O(n)

a 长度为 n，queries 有 q 个 (l, r) 区间。时间复杂度是？

def range_sums(a, queries):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return [p[r + 1] - p[l] for l, r in queries]

O(n + q)
O(q log n)
O(n log n + q)
O(n·q)

a 长度为 n，queries 有 q 个 (l, r) 区间。最坏情况下的时间复杂度是？
```
def range_sums(a, queries):
    return [sum(a[l:r + 1]) for l, r in queries]
```
- O(q log n)
- O(n·q)
- O(n + q)
- O(q)

初始 hi - lo = n，每次调用 ok 需要 O(m)。时间复杂度是？

def first_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

O(m + log n)
O(m log n)
O(log n)
O(n·m)

a 是有序列表。最坏情况下的时间复杂度是？（n = len(a)）

def contains(a, x):
    if not a:
        return False
    mid = len(a) // 2
    if a[mid] == x:
        return True
    if a[mid] < x:
        return contains(a[mid + 1:], x)
    return contains(a[:mid], x)

O(n log n)
O(log n)
O(n)
O(log² n)

下面代码在最坏情况下的时间复杂度是？（n = len(a)）

from bisect import insort

def sorted_stream(a):
    out = []
    for x in a:
        insort(out, x)
    return out

O(n²)
O(n)
O(log n)
O(n log n)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def next_greater(a):
    res = [-1] * len(a)
    stack = []
    for i, x in enumerate(a):
        while stack and a[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res

只有输入有序时才是 O(n)
O(n)
O(n²)
O(n log n)

下面代码在最坏情况下的时间复杂度是？（n = len(a)）
```
import heapq

def build(a):
    h = []
    for x in a:
        heapq.heappush(h, x)
    return h
```
- O(n log n)
- O(log n)
- O(n)
- O(n²)

1 ≤ k ≤ n。时间复杂度是？（n = len(a)）

import heapq

def top_k(a, k):
    h = []
    for x in a:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return sorted(h, reverse=True)

O(n·k)
O(n + k)
O(n log k)
O(n log n)

tasks 有 n 个元素。时间复杂度是？

def drain(tasks):
    q = list(tasks)
    done = 0
    while q:
        q.pop(0)
        done += 1
    return done

O(1)
O(n²)
O(n)
O(n log n)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def running_medians(a):
    out = []
    for i in range(1, len(a) + 1):
        s = sorted(a[:i])
        out.append(s[(i - 1) // 2])
    return out

O(n³)
O(n²)
O(n² log n)
O(n log n)

链表有 n 个节点。suffix_lengths 的时间复杂度是？

def length(node):
    n = 0
    while node:
        n += 1
        node = node.next
    return n

def suffix_lengths(head):
    out = []
    while head:
        out.append(length(head))
        head = head.next
    return out

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

树有 n 个节点、高度为 h。时间和额外空间分别是？
```
def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))
```
- O(n) 时间，O(h) 额外空间
- O(n²) 时间，O(n) 额外空间
- O(log n) 时间，O(1) 额外空间
- O(n log n) 时间，O(log n) 额外空间

在有 n 个节点的完全平衡二叉树上调用 balanced(root)，时间复杂度是？

def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

def balanced(node):
    if not node:
        return True
    if abs(height(node.left) - height(node.right)) > 1:
        return False
    return balanced(node.left) and balanced(node.right)

O(log n)
O(n)
O(n log n)
O(n²)

这是一棵不做平衡的普通二叉搜索树。循环部分的总时间是？

def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node

root = None
for k in range(n):
    root = insert(root, k)

O(n²)
O(n)
O(n log n)
O(log n)

在 n 个节点、高度为 h 的 BST 上把 next() 调用 n 次走完整个中序。每次 next() 的代价是？

class InorderIter:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.key

均摊 O(n)
均摊 O(1)，单次最坏 O(h)
每次都是 O(log n)
均摊 O(h)

网格是 R 行 C 列。时间复杂度是？

from collections import deque

def steps(grid, start):
    R, C = len(grid), len(grid[0])
    dist = {start: 0}
    q = deque([start])
    while q:
        r, c = q.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == '.' and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    return dist

O(R·C)
O(R + C)
O(R·C·log(R·C))
O((R·C)²)

n 个元素上做 m 次 find 或 union（m ≥ n），总时间是？

def find(p, x):
    while p[x] != x:
        p[x] = p[p[x]]
        x = p[x]
    return x

def union(p, size, a, b):
    a, b = find(p, a), find(p, b)
    if a == b:
        return False
    if size[a] < size[b]:
        a, b = b, a
    p[b] = a
    size[a] += size[b]
    return True

O(m·α(n))，几乎是线性
O(m·n)
O(m²)
O(m·√n)

n 个元素上做 m 次 find 或 union，最坏情况下总时间是？

def find(p, x):
    while p[x] != x:
        x = p[x]
    return x

def union(p, a, b):
    p[find(p, a)] = find(p, b)

O(m log n)
O(m)
O(m·α(n))
O(m·n)

图有 V = n 个顶点、E 条边，用 n×n 邻接矩阵表示。时间复杂度是？

def components(n, matrix):
    seen = [False] * n

    def dfs(u):
        seen[u] = True
        for v in range(n):
            if matrix[u][v] and not seen[v]:
                dfs(v)

    count = 0
    for u in range(n):
        if not seen[u]:
            count += 1
            dfs(u)
    return count

O(V²)
O(V + E)
O(V·E)
O(E log V)

V = n 个顶点，E = len(edges) 条边。时间复杂度是？

from collections import deque

def topo(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order

O(E log V)
O(V·E)
O(V + E)
O(V²)

图有 V 个顶点、E 条边，边权非负。时间复杂度是？

import heapq

def dijkstra(adj, s):
    dist = {s: 0}
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist.get(v, float('inf')):
                dist[v] = d + w
                heapq.heappush(pq, (d + w, v))
    return dist

O(V² log V)
O(V + E)
O(V·E)
O((V + E) log V)

V = n 个顶点，E = len(edges) 条边。时间复杂度是？

def bellman_ford(n, edges, s):
    dist = [float('inf')] * n
    dist[s] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

O(V³)
O(V·E)
O(E log V)
O(V + E)

d 是 V×V 的距离矩阵。时间复杂度是？

def all_pairs(d):
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

O(V²)
O(V⁴)
O(V³)
O(V² log V)

V = n 个顶点，E = len(edges) 条边，图连通。时间复杂度是？

def kruskal(n, edges):
    p = list(range(n))

    def find(x):
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x

    total = 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:
            p[ru] = rv
            total += w
    return total

O(V + E)
O(E²)
O(E log E)
O(V·E)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def subsets(a):
    out = []

    def go(i, cur):
        if i == len(a):
            out.append(cur[:])
            return
        go(i + 1, cur)
        cur.append(a[i])
        go(i + 1, cur)
        cur.pop()

    go(0, [])
    return out

O(n²)
O(n!)
O(n·2^n)
O(2^n)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def perms(a):
    out = []
    used = [False] * len(a)

    def go(cur):
        if len(cur) == len(a):
            out.append(cur[:])
            return
        for i in range(len(a)):
            if not used[i]:
                used[i] = True
                cur.append(a[i])
                go(cur)
                cur.pop()
                used[i] = False

    go([])
    return out

O(n·n!)
O(n!)
O(2^n)
O(n^n)

下面代码的时间复杂度是？
```
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
```
- Θ(n log n)
- Θ(n²)
- Θ(n)
- 指数级：约 φ^n ≈ 1.618^n

第一次调用 fib(n) 的时间复杂度是？（把整数加法看作 O(1)）

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

O(n)
O(φ^n)
O(n²)
O(log n)

网格 g 是 m 行 n 列。时间和额外空间分别是？

def min_path(g):
    m, n = len(g), len(g[0])
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(m):
        for j in range(n):
            left = dp[j - 1] if j else float('inf')
            dp[j] = g[i][j] + min(dp[j], left)
    return dp[-1]

O(m + n) 时间，O(n) 空间
O(m·n) 时间，O(n) 空间
O(m·n) 时间，O(m·n) 空间
O(m·n·(m + n)) 时间，O(n) 空间

items 有 n 件物品，容量是 W。时间复杂度是？

def knapsack(items, W):
    dp = [0] * (W + 1)
    for wt, val in items:
        for w in range(W, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

O(2^n)
O(n log W)
O(n·W)
O(n + W)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

from bisect import bisect_left

def lis(a):
    tails = []
    for x in a:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

O(n log n)
O(n²)
O(n)
O(n log² n)

m = len(a)，n = len(b)。时间和额外空间分别是？

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            if a[i] == b[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    return dp[m][n]

O(m + n) 时间，O(m + n) 空间
O(m·n) 时间，O(1) 空间
O(2^(m+n)) 时间，O(m + n) 空间
O(m·n) 时间，O(m·n) 空间

n = len(s)，把整数加法看作 O(1)。时间复杂度是？

from functools import lru_cache

def count_decodings(s):
    @lru_cache(maxsize=None)
    def go(t):
        if not t:
            return 1
        ways = go(t[1:]) if t[0] != '0' else 0
        if len(t) >= 2 and '10' <= t[:2] <= '26':
            ways += go(t[2:])
        return ways

    return go(s)

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

n = len(s)。最坏情况下的时间和额外空间分别是？

def count_pal(s):
    n, total = len(s), 0
    for c in range(2 * n - 1):
        lo, hi = c // 2, c // 2 + c % 2
        while lo >= 0 and hi < n and s[lo] == s[hi]:
            total += 1
            lo -= 1
            hi += 1
    return total

O(n²) 时间，O(n²) 空间
O(n²) 时间，O(1) 空间
O(n³) 时间，O(1) 空间
O(n) 时间，O(1) 空间

n = len(s)。时间复杂度是？

def count_pal(s):
    n = len(s)
    return sum(s[i:j] == s[i:j][::-1]
               for i in range(n) for j in range(i + 1, n + 1))

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

n = len(prices)，最多交易 k 次。时间和额外空间分别是？

def max_profit(k, prices):
    buy = [float('-inf')] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for t in range(1, k + 1):
            buy[t] = max(buy[t], sell[t - 1] - p)
            sell[t] = max(sell[t], buy[t] + p)
    return sell[k]

O(n²·k) 时间，O(k) 空间
O(n·k) 时间，O(k) 空间
O(n + k) 时间，O(k) 空间
O(n·k) 时间，O(n·k) 空间

jobs 是 n 个 (开始, 结束, 权值)。时间复杂度是？

from bisect import bisect_right

def best(jobs):
    jobs.sort(key=lambda j: j[1])
    ends = [e for _, e, _ in jobs]
    dp = [0] * (len(jobs) + 1)
    for i, (s, e, w) in enumerate(jobs):
        k = bisect_right(ends, s, 0, i)
        dp[i + 1] = max(dp[i], dp[k] + w)
    return dp[-1]

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

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

from functools import lru_cache

def first_player_margin(a):
    @lru_cache(maxsize=None)
    def go(i, j):
        if i > j:
            return 0
        return max(a[i] - go(i + 1, j), a[j] - go(i, j - 1))

    return go(0, len(a) - 1)

O(n²)
O(n)
O(n³)
O(2^n)

在空队列上执行任意 n 次 push 和 pop，每次操作的代价是？

class Queue:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

每次 pop 都是 O(n)
每次调用都保证 O(1)
均摊 O(log n)
均摊 O(1)，单次最坏 O(n)

get 和 put 每次的时间复杂度是？

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()

    def get(self, key):
        if key not in self.d:
            return -1
        self.d.move_to_end(key)
        return self.d[key]

    def put(self, key, value):
        self.d[key] = value
        self.d.move_to_end(key)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)

O(log cap)
O(cap²)
O(cap)
平均 O(1)

缓存里已有 cap 个键时，一次命中的 get 的时间复杂度是？

class LRU:
    def __init__(self, cap):
        self.cap, self.d, self.order = cap, {}, []

    def get(self, key):
        if key not in self.d:
            return -1
        self.order.remove(key)
        self.order.append(key)
        return self.d[key]

O(cap)
O(log cap)
O(cap²)
O(1)

把一组单词建成字典树，时间复杂度是？

def build(words):
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node['$'] = True
    return root

O(S·L)，L 是最长单词的长度
O(S)，S 是所有单词的长度之和
O(S log S)
O(单词个数)

x 是非负整数。循环执行的次数等于？
```
def ones(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count
```
- 固定 32 次
- x 的二进制位数
- x 本身的大小
- x 中 1 的个数
a、b 是正整数，把一次取模看作 O(1)。时间复杂度是？
```
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
```
- O(√a)
- O(min(a, b))
- O(log min(a, b))
- O(a + b)

n ≥ 1。时间复杂度是？（取最紧的界）

def primes(n):
    is_p = [True] * (n + 1)
    is_p[0] = is_p[1] = False
    i = 2
    while i * i <= n:
        if is_p[i]:
            for j in range(i * i, n + 1, i):
                is_p[j] = False
        i += 1
    return [k for k in range(n + 1) if is_p[k]]

O(n log log n)
O(n log n)
O(n)
O(n√n)

bits 是低位在前的二进制计数器，从全 0 开始调用 increment n 次（位数足够）。总时间是？
```
def increment(bits):
    i = 0
    while i < len(bits) and bits[i] == 1:
        bits[i] = 0
        i += 1
    if i < len(bits):
        bits[i] = 1
```
- 总共 O(n²)
- 均摊每次 O(log n)
- 总共 O(n)，均摊每次 O(1)
- 总共 O(n log n)

下面代码在最坏情况下的时间复杂度是？（把一次取模看作 O(1)）

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

O(log n)
O(√n)
O(n log n)
O(n)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]

O(n²)
O(n log n)
O(n)
O(n log² n)

调用 range_max(a, 0, n - 1)。时间复杂度是？

def range_max(a, lo, hi):
    if lo == hi:
        return a[lo]
    mid = (lo + hi) // 2
    return max(range_max(a, lo, mid), range_max(a, mid + 1, hi))

O(n)
O(n²)
O(n log n)
O(log n)

下面代码的时间复杂度是？（n = len(a)，取最紧的界）
```
def halves(a):
    if len(a) <= 1:
        return 0
    return sum(a) + halves(a[:len(a) // 2])
```
- O(log n)
- O(n²)
- O(n log n)
- O(n)

下面代码的时间复杂度是？

def work(n):
    if n <= 1:
        return 1
    total = 0
    for _ in range(n):
        total += 1
    return total + work(n // 2) + work(n // 2) + work(n // 2)

Θ(n²)
Θ(n^(log₂3)) ≈ n^1.585
Θ(3^n)
Θ(n log n)

输入是已经升序排好的 n 个不同的数。时间复杂度是？

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = a[0]
    smaller = [x for x in a[1:] if x < pivot]
    larger = [x for x in a[1:] if x >= pivot]
    return quick_sort(smaller) + [pivot] + quick_sort(larger)

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

下面代码的时间复杂度是？

def count(n):
    c = 0
    for i in range(n):
        j = 1
        while j < n:
            j *= 2
            c += 1
    return c

O(log n)
O(n²)
O(n log n)
O(n)

下面代码的时间复杂度是？

def count(n):
    c = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            c += 1
    return c

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

下面代码的时间复杂度是？

def count(n):
    c = 0
    for i in range(n):
        for j in range(i, n):
            c += 1
    return c

O(n²)
O(n³)
O(n)
O(n log n)