综合自测与速查手册

15.1 全课程复杂度速查大表

把这张表抄在笔记本第一页。注意三点：n 是数据规模，平均与最坏经常不同，额外空间不含输入本身占用的空间。

15.1.1 线性结构

15.1.2 串与矩阵

15.1.3 树结构

15.1.4 图论算法

15.1.5 查找

15.2 数据结构横向对比

15.2.1 顺序存储 vs 链式存储

15.2.2 栈 vs 队列 vs 双端队列

15.2.3 邻接矩阵 vs 邻接表 vs 链式前向星

15.2.4 十种排序总对比（核心大表，必背）

15.3 C++ STL 容器与算法速查

15.3.1 容器对比

15.3.2 常用算法与技巧速查

#include <bits/stdc++.h>
using namespace std;

int main() {
    /* ---------- 1. 排序与去重 ---------- */
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    sort(a.begin(), a.end());                        // 升序，O(n log n)
    sort(a.begin(), a.end(), greater<int>());        // 降序
    stable_sort(a.begin(), a.end());                 // 稳定排序，O(n log^2 n) 或 O(n log n)
    a.erase(unique(a.begin(), a.end()), a.end());    // 去重（必须先排序）
    reverse(a.begin(), a.end());                     // 反转
    /* random_shuffle 已在 C++17 中废弃，改用 shuffle + 随机数引擎： */
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(a.begin(), a.end(), rng);                // 随机打乱，O(n)

    /* ---------- 2. 二分查找（必须有序） ---------- */
    auto it1 = lower_bound(a.begin(), a.end(), 4);   // 第一个 >= 4 的位置
    auto it2 = upper_bound(a.begin(), a.end(), 4);   // 第一个 >  4 的位置
    bool has = binary_search(a.begin(), a.end(), 4); // 是否存在
    int cnt = upper_bound(a.begin(), a.end(), 4) - lower_bound(a.begin(), a.end(), 4);  // 出现次数

    /* ---------- 3. 最值与统计 ---------- */
    int mx = *max_element(a.begin(), a.end());
    int mn = *min_element(a.begin(), a.end());
    long long sum = accumulate(a.begin(), a.end(), 0LL);   // 注意初值写 0LL 防溢出

    /* ---------- 4. 排列 ---------- */
    sort(a.begin(), a.end());
    do {
        // 处理当前排列
    } while (next_permutation(a.begin(), a.end()));  // 枚举全排列 O(n!)

    /* ---------- 5. 小根堆的两种写法 ---------- */
    priority_queue<int, vector<int>, greater<int>> pqMin;
    priority_queue<int> pqMax;                       // 默认大根堆
    pqMin.push(3); pqMin.push(1);
    int top = pqMin.top();                           // 1
    pqMin.pop();
    /* 对 pair 排序：先比 first 再比 second；大根堆取负值即可变相实现小根堆 */

    /* ---------- 6. 万能头与快读 ---------- */
    ios::sync_with_stdio(false);                     // 关同步，cin/cout 提速
    cin.tie(nullptr);

    /* ---------- 7. 常用常量与边界 ---------- */
    const int INF = 0x3f3f3f3f;                      // 10^9 级，两个 INF 相加不溢出 int
    const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
    /* memset 只能按字节填充：0 / -1 / 0x3f 是安全的，其它值不要用 memset */

    /* ---------- 8. 字符串流分割 ---------- */
    string line = "10 20 30";
    istringstream iss(line);
    int x;
    while (iss >> x) { /* 依次读出 10 20 30 */ }

    return 0;
}

15.4 算法模板库

下面这些模板可以直接复制到作业与比赛中使用，全部经过验证。

15.4.1 基础工具

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

/* 快速幂：a^b mod p，O(log b) */
ll qpow(ll a, ll b, ll p = MOD) {
    ll r = 1; a %= p;
    while (b) {
        if (b & 1) r = r * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return r;
}

/* 最大公约数 / 最小公倍数 */
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

/* 埃氏筛：求 [1,n] 内所有质数，O(n log log n) */
vector<int> sieve(int n) {
    vector<bool> is(n + 1, true);
    vector<int> primes;
    is[0] = is[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (!is[i]) continue;
        primes.push_back(i);
        if ((ll)i * i <= n)
            for (ll j = (ll)i * i; j <= n; j += i) is[j] = false;
    }
    return primes;
}

/* 欧拉线性筛：同时求质数与最小质因子，O(n) */
vector<int> linearSieve(int n, vector<int>& minp) {
    vector<bool> comp(n + 1, false);
    vector<int> primes;
    minp.assign(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        if (!comp[i]) { primes.push_back(i); minp[i] = i; }
        for (int p : primes) {
            if ((ll)i * p > n) break;
            comp[i * p] = true;
            minp[i * p] = p;
            if (i % p == 0) break;
        }
    }
    return primes;
}

/* 扩展欧几里得：求 ax + by = gcd(a,b) 的一组解 */
ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) { x = 1; y = 0; return a; }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    cout << qpow(2, 10) << "\n";        // 1024
    cout << gcd(12, 18) << "\n";       // 6
    auto ps = sieve(30);
    for (int p : ps) cout << p << ' ';
    cout << "\n";
    return 0;
}

15.4.2 并查集 / 堆 / 哈希

#include <bits/stdc++.h>
using namespace std;

/* ================= 并查集（路径压缩 + 按大小合并） ================= */
struct DSU {
    vector<int> fa, sz;
    explicit DSU(int n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); }
    int find(int x) {                       // 路径压缩：均摊 O(α(n))
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        fa[b] = a; sz[a] += sz[b];
        return true;
    }
    bool same(int a, int b) { return find(a) == find(b); }
};

/* ================= 手写小根堆（也可直接用 priority_queue） ================= */
struct MinHeap {
    vector<int> h;
    void push(int x) {
        h.push_back(x);
        int i = h.size() - 1;
        while (i && h[(i - 1) / 2] > h[i]) { swap(h[i], h[(i - 1) / 2]); i = (i - 1) / 2; }
    }
    int top() const { return h[0]; }
    void pop() {
        h[0] = h.back(); h.pop_back();
        int i = 0, n = h.size();
        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, m = i;
            if (l < n && h[l] < h[m]) m = l;
            if (r < n && h[r] < h[m]) m = r;
            if (m == i) break;
            swap(h[i], h[m]); i = m;
        }
    }
    bool empty() const { return h.empty(); }
};

/* ================= 防卡哈希（竞赛必备） ================= */
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
/* 用法：unordered_map<long long, int, custom_hash> mp; */

int main() {
    DSU d(10);
    d.unite(1, 2); d.unite(2, 3);
    cout << d.same(1, 3) << "\n";        // 1
    MinHeap hp;
    for (int x : {5, 1, 9, 3}) hp.push(x);
    cout << hp.top() << "\n";            // 1
    return 0;
}

15.4.3 图论模板（一次拷全）

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100005;        /* 顶点数上限 */
const int MAXM = 200005;        /* 边数上限（无向图要开 2 倍） */

/* ================= 链式前向星（竞赛主流写法，与第 08 讲一致） =================
   head[u] = 顶点 u 的第一条出边下标（-1 表示没有）
   to[i] / w[i] / nxt[i] = 第 i 条边的终点 / 边权 / 同起点的下一条边
   etot = 下一个可用的边结点下标 */
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM];
int etot = 0;

void initGraph(int n) {
    memset(head, -1, sizeof(int) * (n + 1));   /* 加边之前必须先 memset 成 -1 */
    etot = 0;
}
void addEdge(int u, int v, int weight = 1) {
    to[etot] = v; w[etot] = weight; nxt[etot] = head[u]; head[u] = etot++;
}
/* 无向图调用两次 addEdge(u, v, w); addEdge(v, u, w); */

/* ================= 朴素 Dijkstra（邻接矩阵，O(n^2)） ================= */
int n;
vector<vector<int>> g;          // g[u][v] = 权值，无边为 INF
vector<long long> dijkstraNaive(int s) {
    vector<long long> dist(n + 1, LLONG_MAX);
    vector<bool> vis(n + 1, false);
    dist[s] = 0;
    for (int iter = 0; iter < n; ++iter) {
        int u = -1;
        for (int v = 1; v <= n; ++v)
            if (!vis[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (u == -1 || dist[u] == LLONG_MAX) break;
        vis[u] = true;
        for (int v = 1; v <= n; ++v)
            if (g[u][v] < INF && dist[u] + g[u][v] < dist[v])
                dist[v] = dist[u] + g[u][v];
    }
    return dist;
}

/* ================= 堆优化 Dijkstra（链式前向星，O(m log n)） ================= */
vector<long long> dijkstraHeap(int s, int n) {
    vector<long long> dist(n + 1, LLONG_MAX);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dist[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                 // 过期元素，跳过
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (d + w[e] < dist[v]) {
                dist[v] = d + w[e];
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

/* ================= Floyd（O(n^3)，注意 k 在最外层） ================= */
void floyd(vector<vector<long long>>& d, int n) {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i) {
            if (d[i][k] == LLONG_MAX) continue;
            for (int j = 1; j <= n; ++j)
                if (d[k][j] != LLONG_MAX && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
        }
}

/* ================= Kruskal 最小生成树 ================= */
struct Edge { int u, v, w; bool operator<(const Edge& o) const { return w < o.w; } };
long long kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());
    vector<int> fa(n + 1);
    iota(fa.begin(), fa.end(), 0);
    function<int(int)> find = [&](int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); };
    long long total = 0; int used = 0;
    for (const Edge& e : edges) {
        int a = find(e.u), b = find(e.v);
        if (a == b) continue;                      // 成环，丢弃
        fa[b] = a; total += e.w; ++used;
        if (used == n - 1) break;                  // 已经选了 n-1 条边
    }
    return used == n - 1 ? total : -1;             // -1 表示图不连通
}

/* ================= 拓扑排序（Kahn） ================= */
vector<int> topoSort(const vector<vector<int>>& adj, vector<int> indeg, int n) {
    queue<int> q;
    for (int i = 1; i <= n; ++i) if (!indeg[i]) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() != n) return {};         // 有环
    return order;
}

int main() {
    /* 用一个小例子自测：全局数组版必须显式初始化（把 head 清成 -1） */
    initGraph(5);
    addEdge(1, 2, 2); addEdge(2, 3, 3); addEdge(1, 3, 10);
    auto dist = dijkstraHeap(1, 5);
    cout << dist[3] << "\n";                      // 5
    return 0;
}

15.4.4 字符串与动态规划模板

#include <bits/stdc++.h>
using namespace std;

/* ================= KMP：前缀函数 + 匹配 ================= */
vector<int> prefixFunction(const string& P) {
    int m = P.size(); vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int len = pi[i - 1];
        while (len && P[i] != P[len]) len = pi[len - 1];
        if (P[i] == P[len]) ++len;
        pi[i] = len;
    }
    return pi;
}
vector<int> kmpAll(const string& S, const string& P) {     // 返回所有出现位置
    vector<int> res;
    if (P.empty()) return res;
    vector<int> pi = prefixFunction(P);
    int j = 0;
    for (int i = 0; i < (int)S.size(); ++i) {
        while (j && S[i] != P[j]) j = pi[j - 1];
        if (S[i] == P[j]) ++j;
        if (j == (int)P.size()) { res.push_back(i - j + 1); j = pi[j - 1]; }
    }
    return res;
}

/* ================= 字符串哈希（双模数，防碰撞） ================= */
struct StrHash {
    static const int M1 = 1000000007, M2 = 998244353, B = 131;
    vector<long long> h1, h2, p1, p2;
    explicit StrHash(const string& s) {
        int n = s.size();
        h1.assign(n + 1, 0); h2.assign(n + 1, 0);
        p1.assign(n + 1, 1); p2.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            h1[i + 1] = (h1[i] * B + s[i]) % M1;
            h2[i + 1] = (h2[i] * B + s[i]) % M2;
            p1[i + 1] = p1[i] * B % M1;
            p2[i + 1] = p2[i] * B % M2;
        }
    }
    pair<long long, long long> get(int l, int r) const {   // 0 基，闭区间
        long long a = ((h1[r + 1] - h1[l] * p1[r - l + 1]) % M1 + M1) % M1;
        long long b = ((h2[r + 1] - h2[l] * p2[r - l + 1]) % M2 + M2) % M2;
        return {a, b};
    }
};

/* ================= 01 背包（一维滚动数组） ================= */
int knapsack01(const vector<int>& w, const vector<int>& v, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < (int)w.size(); ++i)
        for (int j = W; j >= w[i]; --j)              // 必须倒序！否则变成完全背包
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[W];
}

/* ================= 完全背包（一维滚动数组） ================= */
int knapsackComplete(const vector<int>& w, const vector<int>& v, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < (int)w.size(); ++i)
        for (int j = w[i]; j <= W; ++j)              // 正序！
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[W];
}

/* ================= 最长上升子序列 LIS：O(n log n) ================= */
int lis(const vector<int>& a) {
    vector<int> tails;                               // tails[i] = 长度 i+1 的上升子序列的最小结尾
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);   // 严格递增
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

/* ================= 最长公共子序列 LCS ================= */
int lcs(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp[i][j] = (a[i - 1] == b[j - 1]) ? dp[i - 1][j - 1] + 1
                                              : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[n][m];
}

int main() {
    for (int p : kmpAll("ABABABCABABABCABA", "ABABCABA")) cout << p << ' ';   // 2 9
    cout << "\n";
    cout << knapsack01({1, 3, 4}, {15, 20, 30}, 4) << "\n";                    // 35
    cout << lis({10, 9, 2, 5, 3, 7, 101, 18}) << "\n";                        // 4
    cout << lcs("abcde", "ace") << "\n";                                      // 3
    return 0;
}

15.5 五十条易错概念辨析

15.5.1 绪论与复杂度

1. 大 O 是上界，不是精确值。 2n² + 3n 和 n² 都是 O(n²)，但不能说它们「一样快」。
2. O(1) 不等于「执行一次」。 执行 1000 条语句仍是 O(1)。
3. 循环变量的变化方式是判断复杂度的关键。 i *= 2 是 O(log n)，i = sqrt(i) 是 O(log log n)。
4. 递归的时间复杂度要写递推式。 不能只看循环层数。
5. 空间复杂度算的是额外空间，递归要算栈深度。
6. 算法的「有穷性」指在有限步内结束，不是「不能有循环」。
7. 逻辑结构与存储结构是两个独立维度：同一逻辑结构可以有多种存储结构。

15.5.2 线性表

8. 顺序表插入的平均移动次数是 n/2，删除是 (n−1)/2（教材常都近似为 n/2）。
9. 头结点不是首元结点。 头结点不存数据（或存长度），是为了统一空表与非空表的操作。
10. 「在 p 结点前插入」单链表做不到 O(1)，除非已知前驱；但「在 p 结点后插入」可以 O(1)（交换数据域的技巧）。
11. 双向链表删除结点不需要找前驱，这是它相对单链表最大的优势。
12. 静态链表的 next 存的是数组下标（游标），不是地址。
13. 快慢指针判环时，快指针每次走 2 步，两者一定会在环内相遇（如果有环）。

15.5.3 栈与队列

14. 共享栈的栈满条件是 top1 + 1 == top0（两个栈顶相邻），不是相等。
15. 链栈通常不设头结点，栈顶就是链表的第一个结点。
16. 循环队列「牺牲一个单元」是为了区分队空与队满：队空 front == rear，队满 (rear+1)%M == front。
17. 循环队列元素个数 = (rear − front + M) % M，不要漏掉 +M。
18. 链队列在出队后若队列为空，必须把 rear 重新指向头结点，否则 rear 悬空。
19. 中缀转后缀时，右括号不入栈；遇到右括号要一直弹到左括号为止（左括号弹出但不输出）。
20. 后缀表达式求值时，遇到运算符弹出的是「先右后左」两个操作数，减法与除法的顺序不能反。

15.5.4 串

21. 子串必须连续，子序列可以不连续。
22. π[i] 表示的是真前后缀，长度不能等于 i+1（不包含自身）。
23. KMP 中 i 永不回退；回退的是 j，且回退到 π[j-1]。
24. KMP 不是「任何输入都比朴素快」，它胜在最坏情况的保证。
25. BM 只看坏字符规则会出问题（位移可能非正），必须与好后缀规则取最大值。
26. next 数组有三种约定（0 基 π / 1 基教材版 / 位移版），做题前先确认用的是哪一种。

15.5.5 数组、矩阵、树

27. 行优先是「先走完最后一行下标」（C/C++），列优先相反（Fortran/Matlab）。
28. 对称矩阵只需存 n(n+1)/2 个元素；三角矩阵还要多存一个常数 c，是 n(n+1)/2 + 1。
29. 「n₀ = n₂ + 1」这条性质对任何非空二叉树都成立，与是否完全无关。
30. 完全二叉树的深度是 ⌊log₂n⌋ + 1，注意是下取整加一。
31. 已知前序 + 后序无法唯一确定一棵二叉树；必须要有中序。
32. 赫夫曼树不唯一（左右子树可互换、相同权值的合并顺序可不同），但 WPL 唯一。
33. 赫夫曼编码是前缀编码：任何编码都不是另一个编码的前缀，因此可以唯一译码。
34. 树的「左孩子右兄弟」表示法得到的是二叉树，且该二叉树没有右子树（对单棵树而言）。

15.5.6 图与图论算法

35. 无向图度数和 = 2e（握手定理）；有向图入度和 = 出度和 = e。
36. 无向图 e ≤ n(n−1)/2；有向图 e ≤ n(n−1)。别把两者搞混。
37. 无向连通图的生成树有恰好 n−1 条边，生成树不唯一但边数是确定的。
38. Prim 适合稠密图，Kruskal 适合稀疏图；两个算法都基于贪心。
39. Dijkstra 不能处理负权边，因为它依赖「已确定的最短距离不会再变小」这一贪心前提。
40. Floyd 的三重循环必须把 k 放在最外层，i/j 放外层会导致结果错误。
41. 拓扑排序存在 ⟺ 图是有向无环图（DAG）；有环则排序结果不足 n 个顶点。
42. 关键路径是 AOE 网中从源点到汇点的最长路径，它的长度等于工程的最短完成时间。
43. 关键活动是 e(a) == l(a) 的活动；缩短非关键活动不改变总工期。
44. DFS 用栈（或递归）、BFS 用队列；求最短路径必须用 BFS（无权图）或 Dijkstra 等（带权图）。

15.5.7 查找与排序

45. 折半查找要求顺序存储 + 有序，链表上无法实现 O(log n) 的折半查找。
46. 插值查找在数据均匀分布时才快，分布极端不均会退化到 O(n)。
47. 哈希表删除元素必须用墓碑标记，直接把位置清空会截断探测链，导致后面的元素查不到。
48. 线性探测法会产生堆积（聚集），平方探测可缓解但对表长有要求（4j+3 形式的质数）。
49. 比较排序的下界是 Ω(n log n)，证明用决策树：n 个元素的排列有 n! 种，决策树至少 n! 个叶子，树高 ≥ ⌈log₂(n!)⌉ = Ω(n log n)。
50. 「快些选堆」四个不稳定，其余稳定；稳定性只在比较关键字相等的元素时才有意义。

15.6 模拟自测卷

共 16 题，满分 94 分（选择题 10×2 + 填空题 7 空×2 + 计算与作图 4×10 + 算法设计 2×10）， 建议 120 分钟内完成。选择题、计算与作图、算法设计题的答案与解析都在题下折叠，请先做完再看； 填空题的答案直接给出，当作默写清单用。

一、选择题（每题 2 分，共 20 分）

1. 以下关于数据结构的说法，正确的是（　）

A. 数据的存储结构是数据元素之间的逻辑关系的抽象表示
B. 顺序存储结构的插入删除效率一定高于链式存储结构
C. 同一逻辑结构可以采用不同的存储结构实现
D. 抽象数据类型与具体的存储结构一一对应

2. 设 n 为问题规模，下面程序段的时间复杂度是（　）

int i = 1, s = 0;
while (i <= n) { s += i; i *= 3; }

A. O(n)　B. O(log₃n)　C. O(n log n)　D. O(√n)

3. 在一个长度为 n 的顺序表中删除第 i 个元素（1 ≤ i ≤ n），需要移动的元素个数为（　）

A. n − i　B. n − i + 1　C. n − i − 1　D. i

4. 已知循环队列的存储空间为数组 Q[0..M-1]，front 指向队头元素、 rear 指向队尾元素的下一个位置，则队列中元素个数为（　）

A. rear − front　B. (rear − front + M) % M　C. (rear − front) % M + 1　D. rear − front − 1

5. 设模式串 P = "ababaa"，采用 0 基前缀函数 π，则 π[4] 的值是（　）

A. 2　B. 3　C. 4　D. 1

6. 一棵二叉树中有 30 个叶子结点、20 个度为 1 的结点，则该二叉树的结点总数为（　）

A. 79　B. 80　C. 81　D. 无法确定

7. 关于有向图的拓扑排序，下列说法正确的是（　）

A. 有向图存在拓扑序列的充要条件是它是无环图（DAG）
B. 任何有向图都存在拓扑序列
C. 一个 DAG 的拓扑序列一定唯一
D. 拓扑序列的长度等于图中边的条数

8. 用 Dijkstra 算法求下图单源最短路径（图中有负权边），结果是（　）

A. 一定正确　B. 可能出错　C. 一定出错　D. 只对无向图出错

9. 对 8 个元素进行折半查找，查找成功时最多需要比较几次？

A. 2　B. 3　C. 4　D. 8

10. 以下排序算法中，时间复杂度为 O(n log n) 且稳定的是（　）

A. 快速排序　B. 堆排序　C. 归并排序　D. 希尔排序

二、填空题（每空 2 分，共 14 分）

1. 一个具有 n 个顶点的无向连通图，至少有 n−1 条边；至多有 n(n−1)/2 条边。
2. 在含 n 个元素的有序表中进行折半查找，查找成功的平均查找长度约为 log₂(n+1) − 1。
3. 深度为 5 的完全二叉树最多有 31 个结点，最少有 16 个结点。
4. 赫夫曼树中不存在度为 1 的结点（因为每次合并都会生成一个度为 2 的新结点）。
5. 设哈希表长 m = 11，哈希函数 H(k) = k mod 11，用线性探测法处理冲突， 依次插入 {12, 23, 45, 57, 20, 3}，则元素 3 最终存放的下标是 6。
   解析：12 % 11 = 1 → 存 1；23 % 11 = 1，冲突 → 2；45 % 11 = 1，冲突 → 2、3； 57 % 11 = 2，冲突 → 3、4；20 % 11 = 9；3 % 11 = 3，冲突 → 4、5、6。 最终哈希表为 [_,12,23,45,57,_,3,_,_,20,_]。

三、计算与作图题（每题 10 分，共 40 分）

11. 已知一棵二叉树的前序遍历为 ABDECFG，中序遍历为 DBEAFCG， 请画出这棵二叉树，并写出它的后序遍历序列。

12. 给定权值集合 W = {5, 7, 2, 3, 11}，构造赫夫曼树并计算 WPL， 写出各字符的赫夫曼编码（按每次合并权值最小者、相同权值取先出现的规则）。

13. 已知无向网的邻接矩阵如下（∞ 表示无边）， 用 Prim 算法从顶点 1 出发求最小生成树，写出加边的顺序与总权值。

14. 对序列 {49, 38, 65, 97, 76, 13, 27, 49} 分别写出 一趟快速排序（以第一个元素为基准）与一趟归并排序（二路归并，步长 1）后的结果。

四、算法设计题（每题 10 分，共 20 分）

15. 设计一个算法，判断单链表中是否存在环；若存在，找出环的入口结点。要求空间复杂度 O(1)，并说明原理。

#include <iostream>
using namespace std;

struct Node { int val; Node* next; Node(int v): val(v), next(nullptr) {} };

/* 快慢指针（Floyd 判环）
   阶段一：slow 每次 1 步、fast 每次 2 步，若相遇则有环。
   阶段二：让一个指针回到头结点，两个指针每次都走 1 步，再次相遇处即为环入口。
   原理：设头到环入口距离 a，入口到相遇点距离 b，相遇点到入口距离 c。
         相遇时 slow 走了 a+b，fast 走了 a+b+k(b+c) 且是 slow 的 2 倍，
         可得 a = (k-1)(b+c) + c，即从相遇点走 c 步到入口 = 从头走 a 步到入口。 */
Node* detectCycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {                 // 阶段一：相遇，有环
            Node* p = head;
            while (p != slow) {             // 阶段二：找入口
                p = p->next;
                slow = slow->next;
            }
            return p;                       // 环入口
        }
    }
    return nullptr;                         // 无环
}

int main() {
    Node* n1 = new Node(1); Node* n2 = new Node(2);
    Node* n3 = new Node(3); Node* n4 = new Node(4);
    n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n2;   // 4 指回 2
    Node* entry = detectCycle(n1);
    cout << (entry ? entry->val : -1) << "\n";   // 2
    return 0;
}

16. 给定整数数组 a[] 与整数 target，求所有满足 a[i] + a[j] = target 的下标对 (i, j)（i < j）。要求时间 O(n)、空间 O(n)， 并说明为什么不能简单地先排序再用双指针（提示：考虑下标要求与重复元素）。

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

/* 哈希表一次遍历：对每个 a[j]，看 target - a[j] 是否出现过
   时间 O(n)、空间 O(n) */
vector<pair<int,int>> twoSum(const vector<int>& a, int target) {
    unordered_map<int, int> lastSeen;      // 值 → 最近一次出现的下标
    vector<pair<int,int>> res;
    for (int j = 0; j < (int)a.size(); ++j) {
        int need = target - a[j];
        auto it = lastSeen.find(need);
        if (it != lastSeen.end()) res.push_back({it->second, j});
        lastSeen[a[j]] = j;                // 后出现的覆盖先出现的，保证 i < j
    }
    return res;
}

/* 若允许 O(n log n) 且只要求「是否存在」，可以排序 + 双指针：
   sort(a.begin(), a.end());
   int i = 0, j = n - 1;
   while (i < j) {
       int s = a[i] + a[j];
       if (s == target) return true;
       else if (s < target) ++i;
       else --j;
   }
   但排序会打乱原始下标，若题目要求返回下标就必须额外记录位置；
   而且要返回「所有」下标对时，排序 + 双指针还要处理重复元素的组合，容易漏解或重复。 */

int main() {
    vector<int> a = {2, 7, 11, 15, 3, 6};
    for (auto& p : twoSum(a, 9)) cout << p.first << "," << p.second << "  ";   // 0,1  4,5
    cout << "\n";
    return 0;
}

15.7 复习路线图