算法应用：代码填空技巧与案例解析

本篇整理“【软件设计】数据结构及算法应用”的 3 篇课件：复杂度回顾、代码填空技巧与实战演练。保留 7 组技巧题图和 2 道完整案例，教学图片均已本地化。“原课件参考答案”与“补充解析／修正版”分别标注，避免把题图原样代码当成已经验证的完整程序。

概念与选择题配套阅读：算法基础：复杂度、查找、排序与算法策略。

一、代码题中的复杂度口径

时间复杂度衡量基本操作次数如何随输入规模增长，不直接等于实际耗时秒数。常见量级为：

O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(n³)、O(2ⁿ)。

辅助空间需统计同时占用的数组、动态内存、调用栈等，不能只看局部变量声明。输入本身是否计入应先约定；常量个局部变量通常是 O(1)，长度为 n 的局部数组、堆分配数组或深度为 n 的递归栈则不是。

分析题应依次写清：n 代表什么 → 循环／递归实际做几次 → 每次做什么 → 取最好、平均还是最坏情况 → 是否计调用栈与动态内存。 动态规划即使使用自顶向下递归，只要缓存状态，也不一定是指数时间。

动态规划代码：先把一个格子的含义说完整

看到二维数组，先写一句“dp[i][j] 表示什么”，再解释下标范围、初值、转移和答案位置。数组外形相同，含义也可能完全不同：

状态含义	典型依赖	为什么这样遍历	答案通常在哪里
前 i 个物品、容量上限 j 的最优值	上一行的若干格子	先处理更少的物品	dp[n][W]
两个前缀的最长公共子序列长度	上、左、左上	所依赖的较短前缀先完成	dp[m][n]
恰好以两个当前位置结尾的公共子串长度	左上，失配时归零	必须保持连续，不能跨过不匹配字符	全表最大值
区间 [i,j] 的最小代价	更短区间	按区间长度递增	覆盖完整区间的格子

例如 AXBYC 与 ABC 的公共子序列可以取 ABC，长度为 3；公共子串必须连续，最长只有 1。求“以这里结尾”的状态不能直接当成“截至这里的全局最优”。这一区分也决定代码是更新一个全局最大值，还是直接返回最后一格。

下面用独立的爬台阶例子练习把文字转成代码：一次迈 1 级或 2 级，问到达第 n 级的不同走法数。

1. 定义 ways[i] 为恰好到第 i 级的走法数。
2. 最后一步只能从 i-1 或 i-2 来，两组走法不重叠，因此相加。
3. ways[0]=1 表示空序列是一种走法，ways[1]=1；边界不是根据“数组初始为零”猜出来的。
4. i 递增时依赖项已经求出。长度 n+1 的表需要 O(n) 空间；只保存前两项可降为 O(1) 个变量。

def count_ways(n):
    if n < 0:
        raise ValueError("n must be nonnegative")
    previous, current = 1, 1  # ways[0], ways[1]
    for i in range(2, n + 1):
        previous, current = current, previous + current
    return previous if n == 0 else current

n=0,1,2,3,4 的结果依次是 1,1,2,3,5。循环开始处理第 i 级时，两变量分别保存 ways[i-2]、ways[i-1]，这就是用于核对更新语句的**循环不变式**。Python 的同时赋值先计算右侧；改写成 C 时应先用临时变量保存旧值。考试按整数加法为常数时间计，此例时间 O(n)；实际大整数的位数也会随 n 增长。

填空的答案需要通过哪些边界

检查位置	要问的问题
第一次循环	初值是否有效；是否访问了下标 −1 或尚未计算的格子
最后一次循环	要处理的最后一个元素是否遗漏；< n 和 <= n 对应哪种编号
相等分支	比较是 < 还是 <=；相等元素的顺序是否影响稳定性或重复计数
无解或空输入	返回 −1、0 还是特殊值；题目是否允许这个输入
回溯返回	撤销的是刚才设置的标记，还是已经被覆盖的新下标
复杂度	状态数乘每个状态的工作量；递归深度与递归总调用次数分别统计

填空题一般保留题给算法和变量，不因为另一种写法更熟悉就重写整个程序。即使结果数值相同，也要检查这一行是否破坏后续依赖。

二、代码填空的七种检查方法

1. 检查变量是否在使用前赋值

原技巧：仔细检查所有用到的变量，必要时代入小数据在纸上模拟。

补充解析

题图初始化了 pos[1..N]，下一句却马上用 j 判断循环与访问数组，因此必须先确定当前处理的行。按“从第一个皇后开始”应填 j=1。

内层循环是在当前列不能放置时继续尝试下一列；若 isplace 返回 1 表示合法，条件应为 isplace(pos,j)==0。不能只凭变量名猜 0/1 的含义，须回看函数的返回语句。

count=1 在此表示下一个打印的方案编号，不等于已经找到 1 个方案。完整题目见后面的 N 皇后案例。

2. 对照变量说明和数组含义

原代码说明：cost[i][j] 表示矩阵链 A(i+1)×…×A(j+1) 的最优计算代价；trace[i][j] 记录对应的最优划分位置 k。数组要么已有初始化值，要么须在代码中写入后再读取。

补充解析

代码找到了更小代价时，既更新 tempCost，也记录 tempTrace=k。循环结束写入 cost[i][j]=tempCost 后，对应空格应填 trace[i][j]=tempTrace。

若约定 j=i+p、划分为 [i,k] 与 [k+1,j]，k 的循环条件为 k<j。设第 t 个矩阵的维度为 dim[t−1]×dim[t]，采用数组下标从 0 起的上述状态，则候选代价是：

cost[i][k] + cost[k+1][j] + dim[i] * dim[k+1] * dim[j+1]

dim 是本笔记补充的维度数组名，题图省略了对应原始声明，不能把这个名字当作原题唯一填法。先统一矩阵编号与数组下标，再套公式。

单个矩阵的乘法代价为 0，即 cost[i][i]=0；外层按链长度递增，保证所依赖的短链已经算出。典型时间 O(n³)、空间 O(n²)。

3. 根据变量的作用补齐更新

原技巧：max/min 常记录最大／最小值，temp 常保存临时值或交换中间值；命名是提示，仍需检查上下文。

补充解析

条件是 max<c[i][j]，后面记录 maxi=i、maxj=j，因此缺失的赋值为 max=c[i][j]。只有坐标更新而没有值更新，会使“当前最大值及其位置”的状态不一致。

4. 将伪代码逐句映射到代码

原题背景：给定主串 t 和模式串 s，在 t 中寻找 s；匹配成功返回 s 在 t 中的起始位置，否则返回 −1。KMP 用 next 数组避免主串指针反复回退。

原伪代码要点：i=j=0；两串仍有字符时继续；若 j==-1 或 t[i]==s[j]，i、j 同时加 1；否则令 j=next[j]。

补充解析与可读代码

按图中顺序填 j<ls、t[i]==s[j]、j=next[j]、i-ls。也可将成功返回写成 i-j，因为此时 j=ls。

int kmp(const int next[], const char *t, const char *s,
        int lt, int ls) {
    int i = 0, j = 0;
    while (i < lt && j < ls) {
        if (j == -1 || t[i] == s[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    return j >= ls ? i - ls : -1;
}

这里采用 next[0]=-1 的 next 定义，失配时 j 回退而 i 保持不动。j==-1 || … 利用 C 的短路求值，避免读取 s[-1]。课件把这个步骤说成“j 向右滑动”，更准确的是模式整体右移、模式下标回退；不同版本的 next 或前缀函数不能直接混用。

图中的 Int 应改为 C 的小写 int。函数假定传入长度和 next 数组有效；空模式在这版约定下返回 0。next 构造成本 O(ls)，完整匹配成本 O(lt+ls)。

5. 按递推公式核对分支

参考答案与补充解析

补充解析：这是最长公共子串

依次填 x[i-1]==y[j-1]、max=c[i][j]、c[i][j]=0。第 0 行和第 0 列也要预先置零。

这组公式计算的是**最长公共子串**，要求连续；c[i][j] 表示以 x[i−1] 和 y[j−1] 结尾的公共后缀长度。字符不同时必须归零，全局答案取所有格子的最大值。

基础篇的**最长公共子序列**允许不连续，字符不同时取 max(C[i−1][j],C[i][j−1])。不要因为都叫“LCS”或都使用二维表，就混用递推式。

下面将图中递推整理为可执行 Python 示例，明确输出内容与长度：

def longest_common_substring(x, y):
    c = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]
    best = end = 0
    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                if c[i][j] > best:
                    best, end = c[i][j], i
            else:
                c[i][j] = 0
    return x[end - best:end], best

例如 ABCBDAB 与 BDCABA 的最长公共子序列长度是 4，但最长公共子串长度只有 2。这能直接检验是否把两种递推混淆。

6. 找到算法特有的状态变化

原技巧：分治常递归求解子问题，动态规划查询已经计算的状态，回溯在不能继续时退回上一层。这些是线索，不能据此断言“所有动态规划都调用递归”。

补充解析与题图片段局限

根据注释，向下一层前的空可填 visited[x[k]]=1；返回上一层的空可填 k=k-1。

但题图在回退分支中先执行 x[k]=0，再执行 visited[x[k]]=0，后一句实际清除的是 visited[0]，已经丢失了原顶点下标。若目的是撤销当前顶点标记，通常应先用原下标取消标记，再清除 x[k]；若当前层尚未成功访问任何顶点，则还需依据完整状态机决定应撤销哪一层。

此处只有局部代码，不能据两个填空就宣称整个回溯程序正确。通用检查顺序是：做选择 → 更新路径／标记 → 继续搜索 → 撤销相应选择，保证撤销的对象与设置的对象相同。

7. 将注释、边界和公式一起检查

参考答案与补充解析

补充解析

依图中顺序，两处赋值为 size[1][j]=1、size[i][j]=size[i-1][j]。

对排列 π，状态 size[i][j] 可理解为前 i 个上端点与编号不超过 j 的下端点所能形成的最大不交叉连接数。若 j<π(i)，当前连接不可选，继承上一行；否则比较“不选”和“选择当前连接”两种情况。

图中的三目运算符实现：

max(size[i-1][j], size[i-1][pi[i]-1] + 1)

这是公式描述，并非假设 C 自带名为 max 的函数。图中一处注释写成 j>=c[i]，按变量应为 j>=pi[i]。

另外，图中外层为 for(i=2;i<n;i++)。如果要处理全部 n 个端点并读取 size[n][n]，应执行到 i<=n；片段未显示后续代码，不能把图示循环原样当作完整正确实现。

下面按 1 起始的排列编号补全递推，保留空输入边界：

def max_noncrossing(pi):
    # pi 是 1..n 的排列，Python 列表下标从 0 开始。
    n = len(pi)
    size = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        endpoint = pi[i - 1]
        for j in range(n + 1):
            size[i][j] = size[i - 1][j]
            if j >= endpoint:
                size[i][j] = max(size[i][j],
                                 size[i - 1][endpoint - 1] + 1)
    return size[n][n]

例如排列 [2,1,4,3] 的答案为 2；与该排列的最长严格递增子序列长度一致。这个二维实现的时间、空间均为 O(n²)，不要把它与更快的最长递增子序列实现混淆。

三、实战案例：希尔排序

原题说明与代码

阅读下列说明和 C 代码，回答问题 1 至问题 3。

希尔排序算法又称最小增量排序算法，其基本思想是：

1. 构造步长序列 delta1、delta2、…、deltak，其中 delta1=n/2，后面的每个 delta 是前一个的 ½，deltak=1。
2. 根据步长序列进行 k 趟排序。
3. 对第 i 趟排序，根据步长 delta，将等步长位置元素分组，对同组元素在原位置上进行直接插入排序。

变量说明：data 为长度 n 的待排序数组，数据在 data[0]～data[n−1]；n 为元素个数，delta 为步长数组。原题把 n 的说明误写成“数组 a”，此处统一为 data。希尔排序更常称**缩小增量排序**；整数步长采用整除。

问题 1（8 分）：根据说明和 C 代码，填充空（1）～（4）。

问题 2（4 分）：该算法的时间复杂度（5）O(n²)（小于、等于或大于）；该算法是否稳定（6）（是或否）。

问题 3（3 分）：对数组 (15,9,7,8,20,-1,4) 用希尔排序方法排序，经过第一趟排序后的数组为（7）。

参考答案与补充解析

原课件参考答案

空号	原参考答案
（1）	k=k/2
（2）	k>1
（3）	data[k]<data[k-dk]
（4）	data[j+dk]=t
（5）	小于
（6）	否
（7）	(4,9,-1,8,20,7,15)

补充解析：填空如何推出来

（1）（2）负责生成增量：先把 k 减半并保存，继续条件是 k>1，这样最后会保存 1。不能用 k>=1，否则还会生成 0。

（3）检查当前元素与同组前一个元素的关系；只有当前值较小才需要前移。保存为 t 后，每次将同组的大元素右移 dk 个位置，直到 j<0 或 data[j]<=t。

（4）循环停止后，待插入位置为 j+dk，因此应写回 t，不能误写 data[j]=t。

第一趟 dk=7/2=3，按下标分成三组：

下标	原值	组内排序后
0、3、6	15、8、4	4、8、15
1、4	9、20	9、20
2、5	7、−1	−1、7

写回各自原下标得到 (4,9,-1,8,20,7,15)；第二趟 gap=1 后全部有序，结果为 (-1,4,7,8,9,15,20)。

复杂度与原代码缺陷

原参考答案（5）“小于”按讲义的经验表述保留，但不是这个折半增量程序的通用最坏界。 希尔排序的复杂度依赖增量序列；n/2、n/4、…、1 的最坏时间可以达到 Θ(n²)。大 O 是函数集合／上界记号，本身也不宜简单用“小于”比较；严格分析应明确是在比较平均表现还是最坏渐近增长率。

稳定性答案“否”正确：不同增量组中的相等元素可能发生相对越位，即使每一组内部的插入排序是稳定的，也不能保证整个希尔排序稳定。

题图中还有独立于四个填空的 C 代码问题：

• 用 malloc(sizeof(int)*(n/2)) 分配 delta，却没有给最后一个增量 1 后面的元素写入 0；外层 while((dk=delta[i])>0) 最终会读取未初始化值，较小 n 时可能直接越界。应保存有效步长数量并按数量遍历，或正确分配并设置终止元素。
• n<2 时，原 do…while 与零长度分配不安全，需要提前返回。
• malloc 需要 <stdlib.h>，要检查分配失败并最终 free(delta)。
• 该题图实际申请了 n/2 个 int，辅助空间是 O(n)；即使实际步长只有 O(log n) 个，也不能将已申请的空间忽略。下方直接生成步长的修正版才是 O(1) 辅助空间。

可运行修正版

下面保留折半增量与分组插入思想，直接生成 gap，去掉原题有缺陷的步长数组管理；这是补充实现，不替换原题四个填空。

#include <stdio.h>

void shellsort(int data[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int k = gap; k < n; ++k) {
            int t = data[k];
            int j = k - gap;
            while (j >= 0 && data[j] > t) {
                data[j + gap] = data[j];
                j -= gap;
            }
            data[j + gap] = t;
        }
    }
}

int main(void) {
    int data[] = {15, 9, 7, 8, 20, -1, 4};
    int n = (int)(sizeof data / sizeof data[0]);
    shellsort(data, n);
    for (int i = 0; i < n; ++i) {
        printf("%d%s", data[i], i + 1 == n ? "\n" : " ");
    }
    return 0;
}

输出：-1 4 7 8 9 15 20。n 为 0 或 1 时不进入排序循环。算法约定 n≥0 且 n>0 时 data 指向至少 n 个可写 int。

四、实战案例：N 皇后

原题说明与代码

阅读下列说明和 C 代码，回答问题 1 至问题 3。

N 皇后问题是在 n 行 n 列的棋盘上放置 n 个皇后，使任意两个皇后不在同一行、同一列和同一条对角线上。

原题思路：第 i 个皇后放在第 i 行；从当前行第一列开始尝试，合法就考虑下一个皇后，冲突就尝试下一列；超过最后一列后返回上一行，重新确定上一个皇后的位置，直到找到所有方案。

变量说明：pos[i] 表示第 i 行皇后的列号；count 为方案计数相关变量；i、j、k 为循环变量；N 为皇后数。图中 N=4，数组从 1 起使用。

问题 1（10 分）：填充 C 代码中的空（1）～（5）。

问题 2（2 分）：算法采用了（6）设计策略。

问题 3（3 分）：上述 C 代码的输出为（7）。

参考答案与补充解析

原课件参考答案

空号	原参考答案
（1）	pos[i]==pos[k]
（2）	j=1
（3）	isplace(pos,j)==0
（4）	j<N
（5）	j=j-1
（6）	回溯法
（7）	方案1：2 4 1 3；方案2：3 1 4 2

补充解析：状态、冲突与回退

一行只放一个皇后，因此“不同行”由构造方式保证。检查第 k 行时，只需比较已经确定的第 1～k−1 行：

• 同列冲突：pos[i]==pos[k]。
• 同对角线冲突：abs(i-k)==abs(pos[i]-pos[k])，即行距与列距相同。

isplace 有冲突返回 0，无冲突返回 1。主循环中 j 表示正在处理的行；pos[j] 表示当前尝试的列。进入内层循环前先加 1，是“尝试下一列”；冲突就继续加，直到合法或超过 N。

当前状态	动作
当前行找到合法列，且 j<N	j++，进入下一行
已完成第 N 行	打印方案，然后返回上一行继续枚举
当前行所有列都失败	清空本行 pos[j]=0，再 j--
j 退到 0	所有分支都搜索完，终止

由于前 N−1 行已经各占不同的列，最后一行至多剩一列可用，所以原代码打印完整方案后直接退回上一行，不会漏掉“同一前缀下另一种最后一行方案”。回退前把本行重置为 0，也保证以后再次进入这一行时从第 1 列重新尝试。

可运行整理版

下面与原填空答案保持同一枚举顺序；把整数差值的 fabs 改为 <stdlib.h> 中的 abs，并将成功结束返回值改为 0。原图 return 1 不改变打印方案，但通常表示非零退出状态。

#include <stdio.h>
#include <stdlib.h>

#ifndef N
#define N 4
#endif

int isplace(const int pos[], int k) {
    for (int i = 1; i < k; ++i) {
        if (pos[i] == pos[k] ||
            abs(i - k) == abs(pos[i] - pos[k])) {
            return 0;
        }
    }
    return 1;
}

int main(void) {
    int pos[N + 1] = {0};
    int count = 1;
    int j = 1;
    while (j >= 1) {
        ++pos[j];
        while (pos[j] <= N && isplace(pos, j) == 0) {
            ++pos[j];
        }
        if (pos[j] <= N && j == N) {
            printf("方案%d:", count++);
            for (int i = 1; i <= N; ++i) {
                printf(" %d", pos[i]);
            }
            printf("\n");
        }
        if (pos[j] <= N && j < N) {
            ++j;
        } else {
            pos[j] = 0;
            --j;
        }
    }
    return 0;
}

输出与原参考答案一致：

方案1: 2 4 1 3
方案2: 3 1 4 2

例如第一种方案表示 (行,列)=(1,2)、(2,4)、(3,1)、(4,3)，不是在第一行依次摆四个皇后。列号互不相同，任意两行的行距与列距也不同，因此互不攻击。

这个迭代实现辅助空间 O(N)。时间取决于候选状态数量和冲突检测成本；isplace 一次最多检查 O(N) 行，回溯搜索最坏仍具有组合爆炸，不能因代码只显式写了少数循环就判断为 O(N²)。若改用列与两类对角线的占用标记，可将单次冲突检查降为 O(1)，但仍需搜索候选分支。

五、做代码题的实际顺序

1. 先确定数组下标从 0 还是 1 开始，变量代表“长度”“位置”还是“当前最优值”。
2. 标出初始化、循环条件、状态更新、终止与返回值，不急着给算法贴标签。
3. 从题干公式、伪代码和注释找对应语句；注意“可放置”函数的真假返回值。
4. 代入最小输入与给定样例，重点检查第一次进入循环、最后一次迭代和回退动作。
5. 最后分析复杂度，计入查表、扫描、递归栈和动态分配；原程序与优化程序分别分析。

“看到关键字就选答案”只能帮助定位。真正避免错题的是把**定义、状态变化和边界条件**连起来：例如 Shell 的增量决定复杂度，KMP 的 next 定义决定回退语句，回溯的标记必须与撤销操作配对。

历年大题练习

本节按年份由近到远收录 17 道完整历年大题。先展开题干独立作答，再展开其中的答案与解析；平台答案与整理补充继续分别保留。

题目复用题库中的同一份正文，题图使用本地文件。普通 Markdown 阅读器可通过原题链接进入；完整性与剩余试卷见大题整理进度。

本节保留算法题中的 C 语言代码。2023 年下半年的算法原题代码残缺，另见原题及缺失说明，不计入完整题数。

2024年下半年 · 第 2 题：二叉排序树的查找、插入与构造

展开原题（先作答，再查看解析）

二叉排序树的查找、插入与构造

（二）（15分）
【说明】
二叉排序树（BST）是一种动态查找方法，具有广泛的应用。二叉排序树的定义、构造和查找操作如下：
定义：二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树：
1）若其左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若其右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）其左、右子树也分别为二叉排序树。
构造：从空二叉树开始，通过反复插入结点构造二叉排序树。
在二叉排序树中插入键值等于key的元素步骤如下：
1）若二叉排序树为空树，则插入元素作为树根结点：
2）若根结点的键值等于key，则插入失败；
3）若key小于根结点的键值，则插入到根的左子树上；否则，插入到根的右子树上。
查找：查找键值等于key的元素步骤如下：
1）若二叉排序树为空树，则查找失败，返回；
2）若根结点的键值等于key，则查找成功，返回；
3）若根结点的键值大于key，则到根的左子树上继续查找；否则，到根的右子树上继续查找。
下面的C程序实现二叉排序树的构造和查找。
【C代码】

#include <stdio.h>
#include <stdlib.h>
/*定义树的结点*/
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/*初始化一棵空二叉树*/
void InitBiTree(BiTree *BST){
    *BST =NULL;
}
/*在二叉树上查找关键字为key的元素。
找到则返回1，且q指向该结点，p指向其父结点；
否则返回0，且p指向查找失败的最后一个结点*/
int SearchBST(BiTree BST, BiTNode **p, BiTNode **q, int key){
    int flag = 0;
    *q=BST;
    while((*q)!= NULL){
        if(key > (*q)->data){
            *p=*q;
            *q=(*q)->rchild;
        }else if(key < (*q)->data){
            *p=*q;
            (1);
        }else{
            flag= 1;
            (2);
        }
    }
    return flag;
}
/*在二叉排序树BST上插入关键字为key的元素*/
int InsertBST(BiTree *BST,int key){
    BiTNode*p,*q,*s;
    int flag = 0;
    p=*BST;
    if(SearchBST(*BST,&p,&q,key)==0){ //未找到，可插入
        s =(BiTNode *)malloc(sizeof(BiTNode));
        if(s ==NULL){
            printf ("\n Error\n");
            exit(-1);
        }
        s->data = key;
        s->lchild = NULL;
        s->rchild = NULL;
        flag = 1;
        if(p==NULL){
            (3);
        }else{
            if(key > p->data){
                (4);
            } else{
                p->lchild =s;
            }
        }
    }
    return flag;
}
/*创建二叉排序树*/
void CreateBST(BiTree *BST, int keys[], int n){
    int i;
    for(i =0;i < n;i++){
        (5);
    }
}

01（10分）
根据以上说明和C代码，填充C代码中的空（1）~（5）。
02（5分）
（a) 对n个数据构造二叉排序树，则树的高度（层数）最大为（6）。
（b）若输入数据序列为：36,26,41,38,44,68,12,6,15,51，则构造的二叉排序树为（7）。

答案与解析

平台参考答案（原意保留）

平台参考答案（错误见下方解析）：

1. *q=(*q)->lchild
2. break
3. p=s
4. p->rchild=s
5. insertBST(BST, keys[i])
6. n 个数据构成的二叉排序树最大高度为 n。
7. 平台答案图：

解析与纠错

解析与纠错：

1. 查找键值较小时进入左子树，所以（1）为 *q = (*q)->lchild。
2. 命中结点后设置 flag = 1，必须退出循环，因此（2）为 break。
3. BST 是根指针的地址。空树首次插入必须写回调用方的根指针，因此（3）应为 *BST = s。平台的 p = s 只改变局部变量，函数虽返回插入成功，外部根仍为 NULL，并且新结点失去可达引用。已用程序复现这一错误。
4. 较大的 key 放到父结点右子树，因此（4）为 p->rchild = s。
5. 现有函数名是区分大小写的 InsertBST，因此（5）应为 InsertBST(BST, keys[i])；平台的 insertBST 与声明不一致。平台解析写出的 InsertBST(BiTree BST, int key) 也不是题干实际签名；实际首参为 BiTree *BST。
6. 高度按层数计，插入 n 个互异键的最坏高度为 n，升序或降序插入可达到。如果 n 表示包含重复键的输入个数，重复键会被拒绝，实际结点数是去重后的 m，高度至多 m ≤ n；空树高度为 0。
7. 给定序列的结构与平台答案图一致，最大高度为 5；中序遍历是 6, 12, 15, 26, 36, 38, 41, 44, 51, 68。

36
├─左 26
│     └─左 12
│           ├─左 6
│           └─右 15
└─右 41
      ├─左 38
      └─右 44
            └─右 68
                  └─左 51

还有一处不属于填空的接口细节：题干的 SearchBST 没有在入口初始化 *p。查到根结点时，父指针可能保留调用前的值；查空树亦然。完整示例额外加入 *p = NULL，使“返回父结点”的约定在根结点与空树情况下也成立。这一补充使函数接口满足其父结点返回约定。

C17 编译和测试通过：空树、首次插入、根的父指针、重复键、给定序列的树结构与中序遍历、成功／失败查找、升序／降序最坏高度及整数边界。

补充与完整修正示例

完整修正示例：

示例保留题目的指针接口，补全五处填空，并增加父指针初始化、内存释放和 main；内存分配失败时退出。

#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void InitBiTree(BiTree *BST) {
    *BST = NULL;
}

int SearchBST(BiTree BST, BiTNode **p, BiTNode **q, int key) {
    int flag = 0;
    *p = NULL; /* 补充：查找根结点或空树时，父结点也应明确为空。 */
    *q = BST;
    while (*q != NULL) {
        if (key > (*q)->data) {
            *p = *q;
            *q = (*q)->rchild;
        } else if (key < (*q)->data) {
            *p = *q;
            *q = (*q)->lchild; /* (1) */
        } else {
            flag = 1;
            break; /* (2) */
        }
    }
    return flag;
}

int InsertBST(BiTree *BST, int key) {
    BiTNode *p, *q, *s;
    int flag = 0;
    p = *BST;
    if (SearchBST(*BST, &p, &q, key) == 0) {
        s = (BiTNode *)malloc(sizeof(BiTNode));
        if (s == NULL) {
            fprintf(stderr, "Allocation failed\n");
            exit(EXIT_FAILURE);
        }
        s->data = key;
        s->lchild = NULL;
        s->rchild = NULL;
        flag = 1;
        if (p == NULL) {
            *BST = s; /* (3) */
        } else if (key > p->data) {
            p->rchild = s; /* (4) */
        } else {
            p->lchild = s;
        }
    }
    return flag;
}

void CreateBST(BiTree *BST, int keys[], int n) {
    for (int i = 0; i < n; ++i) {
        InsertBST(BST, keys[i]); /* (5) */
    }
}

void DestroyBST(BiTree BST) {
    if (BST == NULL) return;
    DestroyBST(BST->lchild);
    DestroyBST(BST->rchild);
    free(BST);
}

#ifndef BST_NO_MAIN
int main(void) {
    int keys[] = {36, 26, 41, 38, 44, 68, 12, 6, 15, 51};
    BiTree tree;
    BiTNode *parent, *found;
    InitBiTree(&tree);
    CreateBST(&tree, keys, (int)(sizeof(keys) / sizeof(keys[0])));
    int ok = SearchBST(tree, &parent, &found, 51);
    printf("found=%d, key=%d, parent=%d\n", ok, found->data, parent->data);
    DestroyBST(tree);
    return 0;
}
#endif

2024年上半年 · 第 3 题：哈夫曼树的构造、编码与译码

展开原题（先作答，再查看解析）

哈夫曼树的构造、编码与译码

阅读下列说明和C代码，回答问题。
【说明】
哈夫曼树也称为最优二叉树，是指对于一组带有确定权值的叶子结点，构造具有最小带权路径长度的二叉树。
构造哈夫曼树的基本思想为：
（1）由给定的n个字符{c1,c2...,cn}和对应的权值{w1,w2,....wn}（wi＞0，1≤i≤n）构造n棵只有根结点的二叉树，从而得到一个二叉树集合F{T1,T2...,Tn}，其中每棵二叉树Ti中只有权值为wi的根结点，其左右子树均为空。
（2）在F中选取根结点的权值最小和次小的二叉树分别作为其左右子树构造一棵新的二叉树，这棵新的二叉树的根结点权值为其左右子树根结点权值之和。
（3）在集合F中删除第（2）步中选取的最小和次小的二叉树，并将新构造的二叉树加入到F中。
（4）重复第（2）步和第（3）步，直到F中只剩下一棵二叉树为止。这棵二叉树就是要构建的哈夫曼树。
对构造完成的哈夫曼树的叶子结点进行哈夫曼编码，编码过程从根结点开始，若该结点有左孩子，则左分支标记为0；若该结点有右孩子，则右分支标记为1。依次类推，直到叶子结点。从根结点到叶子结点的二进制串即为该叶子结点对应字符的哈夫曼编码。译码是指将二进制编码翻译为信息原文。
【C代码】
（1）主要变量说明
n：字符数
HT：哈夫曼树
HC：字符集编码指针
buff：待译码的01串
s：s[0]、s[1]分别表示最小权值和次小权值的二叉树的根结点下标
（2）函数定义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
#define HUFFCMAX 40
typedef struct {
char ch;
int weight;
unsigned int parent;
unsigned int lchild;
unsigned int rchild;
}HTNode, *HuffmanTree;
//选择权值最小的两棵子树
int* select(HuffmanTree HT, int n){
int i, j, k;
int *s = (int *)malloc(2*sizeof(int));
for(i=1;i<=n;i++){
if(HT[i].parent==0){
s[0]=i;
break;
}
}
for(k=1;k<=n;k++){
if(HT[k].weight < HT[s[0]].weight && HT[k].parent==0){
s[0]=k;
}
}
for(j=1;j<=n;j++){
if(HT[j].parent==0 && j!=s[0]){
s[1]=j;
break;
}
}
for(k=1;k<=n;k++){
if(k!= s[0] && HT[k].weight < HT[s[1]].weight && HT[k].parent==0){
( 1 );
}
return s;
}
}
//w[]存放n个字符的权值，构造哈夫曼树HT，并求出n个字符的编码存入HC
HuffmanTree HuffmanCoding(HuffmanTree HT,char **HC,int *w,char *ch, int n) {
if(n <= 1) return NULL;
int m=2*n-1;
HT = (HuffmanTree)malloc(2 * n * sizeof(HTNode));
int i, start,c,f;
int *s;
char *cd = (char *)malloc( n * sizeof(char) );
for(i=1;i<=n;i++){
HT[i].weight = w[i-1];
( 2 );
HT[i].parent=0;
HT[i].lchild = HT[i].rchild=0;
}
for(i=n+1; i<=m; i++) {//构造哈夫曼树,m=2*n-1
s = select(HT,i-1);
HT[s[0]].parent=i;
HT[s[1]].parent=i;
( 3 );
HT[i].rchild = s[1];
HT[i].weight = HT[s[0]].weight + HT[s[1]].weight;
}
HC = (char **)malloc( (n+1) * sizeof(char*));
cd[n-1]='\o';
for(i=1;i<=n;i++) {
start=n-1;
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
if(HT[f].lchild==c) ( 4 );
else cd[--start]='1';
HC[i] = (char *)malloc( (n - start) * sizeof(char) );
strcpy(HC[i]. &cd[start]);
printf("\n%c: %s\n", HT[i].ch, HC[i]);
}
return HT;
}
//译码，m是树根的编号
void Decoding(HuffmanTree HT, int m, char *buff) {
int p=m;
int i=0;
while(*buff!="\0' && p!=0){
if(*buff=='0') {
p = HT[p].lchild;
}else{
p = HT[p].rchild;
}
buff+ +;
if(HT[p].lchild==0 && ( 5 ) ){
printf("%c",HT[p].ch);
P= m;//重新从树根出发进行译码
}
}
}

01（10分）
根据以上说明和C代码，填充C代码中的空（1）~（5）。

02（5分）
给定字符集合{a, b, c, d, e, f}和对应的权值{45,13,12,16,9,5}，则构造的哈夫曼树中，字符a和c的编码分别为 （6） 和 （7） 。对字符串“110001001101”译码为 （8） 。

答案与解析

平台参考答案（原意保留）

平台参考答案：

1. s[1] = k
2. HT[i].ch = ch[i-1]
3. HT[i].lchild = s[0]
4. cd[--start] = '0'
5. HT[p].rchild == 0
6. 字符 a 的编码：0。
7. 字符 c 的编码：100。
8. 110001001101 译码为 face。

解析与纠错

解析与纠错：

五处填空分别完成次小根下标更新、叶子字符赋值、新父结点左孩子设置、逆向生成左分支编码、确认译码到达叶子。平台填空与算法意图一致；它们不足以修复题干已有的非填空错误。

按题意将较小权值子树放左侧，合并过程为 5+9=14、12+13=25、14+16=30、25+30=55、45+55=100。得到：

字符	权值	编码
a	45	0
b	13	101
c	12	100
d	16	111
e	9	1101
f	5	1100

因此 110001001101 = 1100 · 0 · 100 · 1101，译码为 face；带权路径长度为224。存在相同权值时，不同合法的选择次序可能产生不同码字，但都可具有相同最优带权路径长度。

题干还包含以下问题：

• select 中 return s 位于最后一次扫描的 for 循环内部，会只考察第一个 k 就返回，无法保证选到次小权值。对于权值 7,50,3,4，应选下标3和4，原位置却会返回3和1。
• malloc 后仅初始化了叶子结点，新增内部结点的 parent 未置零；后续选择根和沿parent回溯可能读取未初始化值。应初始化整个结点数组，或逐一初始化全部内部结点。
• 编码缓冲区末尾应为字符 \0，题干写成了 \o；strcpy 两个实参之间应为逗号，题干写成了点号。
• 译码循环应与字符字面量 '\0' 比较；题干的引号不匹配。buff+ + 应是 buff++，重新回到根的变量应为小写 p，而非 P。
• HC 按值传入，在函数内重新分配只改变局部指针，调用者得不到新编码表。可以把输出参数改为 char ***HC，或返回包含树和编码表的结构。
• 原代码未完整检查内存分配失败，也没有释放选择数组和编码临时缓冲区。合法译码还应区分非法字符、末尾停在非叶子处的截断码字与正常结束。

C17 编译和测试通过：给定序列的全部码字、face译码、带权路径长度224、编码／译码往返、前缀无歧义、相同权值、两个字符、非法权值、空输入码串、非法／截断码串、输出容量与较大权值和。示例沿用题干拒绝 n≤1 的接口范围；空字符集和单字符输入均返回失败。

补充与完整参考实现

完整参考实现：

示例使用输出参数返回编码表，初始化全部结点并检查译码边界。字符数限定为2—100，权值须为正；相同权值按原下标先后选择。权值和使用较宽的整数类型。单字符集合的特殊编码约定没有在此示例中另行扩展。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char ch;
    unsigned long long weight;
    unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;

static int SelectTwo(HuffmanTree HT, int limit, int s[2]) {
    s[0] = s[1] = 0;
    for (int i = 1; i <= limit; ++i) {
        if (HT[i].parent != 0) continue;
        if (s[0] == 0 || HT[i].weight < HT[s[0]].weight) {
            s[1] = s[0];
            s[0] = i;
        } else if (s[1] == 0 || HT[i].weight < HT[s[1]].weight) {
            s[1] = i;
        }
    }
    return s[0] != 0 && s[1] != 0;
}

void FreeHuffman(HuffmanTree HT, char **HC, int n) {
    if (HC != NULL) {
        for (int i = 1; i <= n; ++i) free(HC[i]);
        free(HC);
    }
    free(HT);
}

/* HC通过输出参数交还调用者。沿用题目n>1的范围，本例另限n<=100。 */
HuffmanTree HuffmanCoding(char ***HC, const int *w, const char *ch, int n) {
    if (HC == NULL) return NULL;
    *HC = NULL;
    if (w == NULL || ch == NULL || n < 2 || n > 100) return NULL;
    for (int i = 0; i < n; ++i) if (w[i] <= 0) return NULL;
    int m = 2 * n - 1;
    HuffmanTree HT = calloc((size_t)(m + 1), sizeof(*HT));
    char **codes = calloc((size_t)(n + 1), sizeof(*codes));
    char *cd = malloc((size_t)n);
    if (HT == NULL || codes == NULL || cd == NULL) {
        free(cd); FreeHuffman(HT, codes, n); return NULL;
    }
    for (int i = 1; i <= n; ++i) {
        HT[i].weight = (unsigned int)w[i - 1];
        HT[i].ch = ch[i - 1];
    }
    for (int i = n + 1; i <= m; ++i) {
        int s[2];
        if (!SelectTwo(HT, i - 1, s)) {
            free(cd); FreeHuffman(HT, codes, n); return NULL;
        }
        HT[s[0]].parent = HT[s[1]].parent = (unsigned int)i;
        HT[i].lchild = (unsigned int)s[0];
        HT[i].rchild = (unsigned int)s[1];
        HT[i].weight = HT[s[0]].weight + HT[s[1]].weight;
    }
    cd[n - 1] = '\0';
    for (int i = 1; i <= n; ++i) {
        int start = n - 1;
        for (unsigned int c = (unsigned int)i, f = HT[c].parent;
             f != 0; c = f, f = HT[f].parent) {
            cd[--start] = HT[f].lchild == c ? '0' : '1';
        }
        codes[i] = malloc((size_t)(n - start));
        if (codes[i] == NULL) {
            free(cd); FreeHuffman(HT, codes, n); return NULL;
        }
        strcpy(codes[i], &cd[start]);
    }
    free(cd);
    *HC = codes;
    return HT;
}

/* HT和root须来自HuffmanCoding；失败时清空out，不输出部分译文。 */
int Decoding(HuffmanTree HT, int root, const char *bits, char *out, size_t cap) {
    if (out == NULL || cap == 0) return 0;
    out[0] = '\0';
    if (HT == NULL || root <= 0 || bits == NULL) return 0;
    int p = root;
    size_t used = 0;
    for (; *bits != '\0'; ++bits) {
        if (*bits != '0' && *bits != '1') goto fail;
        p = (int)(*bits == '0' ? HT[p].lchild : HT[p].rchild);
        if (p <= 0 || p > root) goto fail;
        if (HT[p].lchild == 0 && HT[p].rchild == 0) {
            if (used + 1 >= cap) goto fail;
            out[used++] = HT[p].ch;
            p = root;
        }
    }
    if (p != root) goto fail;
    out[used] = '\0';
    return 1;
fail:
    out[0] = '\0';
    return 0;
}

#ifndef HUFFMAN_NO_MAIN
int main(void) {
    const char symbols[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    const int weights[] = {45, 13, 12, 16, 9, 5};
    char **HC = NULL, decoded[32];
    HuffmanTree HT = HuffmanCoding(&HC, weights, symbols, 6);
    if (HT == NULL) return EXIT_FAILURE;
    for (int i = 1; i <= 6; ++i) printf("%c: %s\n", HT[i].ch, HC[i]);
    int ok = Decoding(HT, 11, "110001001101", decoded, sizeof(decoded));
    if (ok) puts(decoded);
    FreeHuffman(HT, HC, 6);
    return ok ? EXIT_SUCCESS : EXIT_FAILURE;
}
#endif

2023年上半年 · 第 4 题：图的连通分量与邻接表

展开原题（先作答，再查看解析）

图的连通分量与邻接表

阅读下列说明和C代码，回答问题1至问题2，将解答写在答题纸的对应栏内。

【说明】
下面的C程序采用深度优先遍历（DFS）来计算图G中的连通分量数。其中图G采用邻接表表示。
【C代码】
（1）主要变量说明
G：图，用邻接表存储
visited[]：数组，长度为Max Vnum，visited[i] = 0 表示顶点i未被访问；visited[i] = 1 表示顶点i已经被访问
count：图G的连通分量数
（2）函数定义

#include < stdio.h >
#define Max Vnum 100
int visited[Max Vnum]={0};
/* 顶点节点 */
typedef struct ArcNode{
int adjvex; /*顶点编号，从0开始*/
struct ArcNode *nextarc; /*指向下一个邻接点*/
}ArcNode;
/* 顶点单链表头节点 */
typedef struct {
char *data; /*顶点标签，如“v1" */
ArcNode *firstarc; /*指向第一个邻接点*/
}AdjList[Max Vnum];
/* 图 */
typedef struct {
int vexnum, arcnum; /*图的顶点数和边数*/
AdjList vertices; /*图的邻接表*/
}AGraph;

/* 从顶点v开始深度优先遍历DFS图G */
void DFS(AGraph G, int v){
ArcNode *p;
visited[v]= 1;
p = G.vertices[v].firstarc;
while(p!= NULL){
if(visited[__(1)___]==0){
DFS(G,p- > adjvex);
}

_____(2)_____;

}
}
/* 计算图G的连通分量数 */
int getNum(AGraph G){
int i, count = 1;
____(3)____;
for(i = 0; i < G.vexnum;i++){
if(visited[i] ==0){
____(4)____;
DFS(G,i);
}
}
____(5)____;
}

【问题1】（10分）
根据以上说明和C代码，填充C代码中的空(1) ~ (5)。
【问题2】（5分）
给出图4-1中图G的邻接表表示。

答案与解析

平台参考答案（原意保留）

【问题1】

（1）p- > adjvex

（2）p = p- > nextarc

（3）count=0

（4）count++

（5）return count

【问题2】

解析与纠错

填空。 （1）p->adjvex；（2）p = p->nextarc；（3）count = 0；（4）count++；（5）return count。DFS检查当前邻接节点所指顶点，递归后沿nextarc继续扫描。外层每从一个未访问顶点启动DFS，就发现一个尚未计数的连通分量。声明中的count = 1会被（3）覆盖，不能在保留该初值时漏掉归零。

邻接表。 按顶点标签V1～V5对应下标0～4，图中有三角形V1—V2—V3—V1和一条V4—V5的边。无向边应在两端各记录一次，邻接节点排列顺序可不同。

顶点（下标）	邻接顶点下标
V1（0）	1，2
V2（1）	0，2
V3（2）	0，1
V4（3）	4
V5（4）	3

共有2个连通分量。平台答案图里的数字是下标，不是标签末尾的数字。

代码纠错。 题干代码的Max Vnum不是合法的单个宏标识符，#include < stdio.h >、p- >也需修正为可编译拼写。更关键的是，平台填空未重置全局visited：对同一个单顶点图连续调用两次getNum，结果为1、0，而应为1、1。修正示例让每次getNum创建独立访问数组，并传递图指针，避免递归时按值复制整个邻接表头数组。该算法用于无向图的连通分量，不是有向图的强连通分量算法。

对有效邻接表，DFS遍历本身的时间复杂度为O(V+E)，递归栈最多O(V)。通常按V分配并清零访问数组时，总辅助空间为O(V)；下面示例使用固定100个访问槽并全部清零，输入顶点数限制为100，图和顶点下标需有效。C17验证覆盖空图、孤立点、原图、重复调用、自环、平行边、合并分量及100顶点链。

补充与完整参考实现

以下为按题意编写并验证的修正示例，包含填空之外的修正与边界处理。

#include <stdio.h>
#include <stdlib.h>

#define MaxVnum 100

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef struct {
    const char *data;
    ArcNode *firstarc;
} Vertex;
typedef struct {
    int vexnum, arcnum;
    Vertex vertices[MaxVnum];
} AGraph;

/* Precondition: a valid undirected adjacency list, 0 <= vexnum <= MaxVnum. */
static void DFS(const AGraph *g, int v, int visited[MaxVnum]) {
    visited[v] = 1;
    for (const ArcNode *p = g->vertices[v].firstarc; p; p = p->nextarc) {
        if (!visited[p->adjvex]) DFS(g, p->adjvex, visited);
    }
}
static int getNum(const AGraph *g) {
    int visited[MaxVnum] = {0};
    int count = 0;
    for (int i = 0; i < g->vexnum; ++i) {
        if (!visited[i]) {
            ++count;
            DFS(g, i, visited);
        }
    }
    return count;
}
static int addEdge(AGraph *g, int u, int v) {
    if (u < 0 || v < 0 || u >= g->vexnum || v >= g->vexnum) return 0;
    ArcNode *a = malloc(sizeof *a), *b = malloc(sizeof *b);
    if (!a || !b) { free(a); free(b); return 0; }
    *a = (ArcNode){v, g->vertices[u].firstarc};
    g->vertices[u].firstarc = a;
    *b = (ArcNode){u, g->vertices[v].firstarc};
    g->vertices[v].firstarc = b;
    ++g->arcnum;
    return 1;
}
static void clearGraph(AGraph *g) {
    for (int i = 0; i < g->vexnum; ++i) {
        ArcNode *p = g->vertices[i].firstarc;
        while (p) { ArcNode *next = p->nextarc; free(p); p = next; }
        g->vertices[i].firstarc = NULL;
    }
    g->arcnum = 0;
}
#ifndef DFS_NO_MAIN
int main(void) {
    AGraph g = {.vexnum = 5};
    if (!addEdge(&g, 0, 1) || !addEdge(&g, 1, 2) ||
        !addEdge(&g, 2, 0) || !addEdge(&g, 3, 4)) {
        clearGraph(&g); return 1;
    }
    printf("components=%d\n", getNum(&g));
    clearGraph(&g);
    return 0;
}
#endif

2022年下半年 · 第 4 题：堆排序的程序填空与执行过程

展开原题（先作答，再查看解析）

堆排序的程序填空与执行过程

使用顺序存储的大顶堆，把n个元素排序为非递减序列。元素位于R[1]～R[n]；初始堆规模为n，最大元素在R[1]，末元素在R[n]。

先建立大顶堆，再交换堆顶与堆中末元素，使末元素退出堆、规模减1，并将余下元素重新调整为大顶堆。重复这一过程直到堆中只剩一个元素，数组即完成非递减排序。

主要变量：n是待排序数组长度；R[]存放待排数据，使用下标1～n。下面给出C代码。

#include

#define MAXITEM 100

void Heapify(int R[MAXITEM], int v, int n){

int i, j;

i = v;

j = 2 * i;

R[0] = R[i];

while (j <= n) {

if (j < n && R[j] < R[j + 1]) {

j++;

}

if (（1）){

R[i] = R[j];

i = j;

j = 2 * i;

}

else{

j = n + 1;

}

}

R[i] = R[0];

}

void HeapSort(int R[MAXITEM], int n){

int i;

for (i = n / 2; i >= 1; i--){

（2）;

}

for (i = n;（3）; i--){

R[0] = R[i];

R[i] = R[1];

（4）;

Heapify(R, 1, i - 1);

}

}

// 测试主函数

int main(){

int arr[MAXITEM] = {0, 5, 3, 8, 1, 9}; // 下标0闲置，数据从1开始

int len = 5;

HeapSort(arr, len);

for (int k = 1; k <= len; k++){

printf("%d ", arr[k]);

}

return 0;

}

【问题1】（8分）填写代码中的空（1）～（4）。

【问题2】（2分）算法时间复杂度为（5），用O符号表示。

【问题3】（5分）给定R=(7，10，13，15，4，20，19，8)、n=8：构建的初始大顶堆为（6）；第一次让堆顶元素退出堆并调整剩余元素后，整个数组R为（7）。

答案与解析

平台参考答案（原文保留）

【问题1】
1：R[0] < R[j]
2：Heapify(R,i,n)
3：i > 1
4：R[1]=R[0]
【问题2】
5：O(nlog ₂ n)【O(nlogn)、O(nlgn)写法也是可以的】

【问题3】
6：｛20，15，19，10，4，13，7，8｝或其树形结构。
7：｛19，15，13，10，4，8，7，20｝

解析与纠错

（1）R[0] < R[j]；（2）Heapify(R,i,n)；（3）i > 1；（4）R[1]=R[0]。R[0]保存当前待下沉元素，j总是两个孩子中较大的一个；若该孩子较大，就把它上移并继续向下找位置，否则停止。每次比较必须使用尚未放回的R[0]，不能使用已经被覆盖的R[i]。

自最后一个非叶结点n/2向根调整可在线性时间建堆。随后n−1次取最大值并下沉，每次至多沿树高走O(log n)步，因此（5）为O(n log₂ n)，底数不影响渐近量级。Heapify在此用循环实现；平台解析中的“归并排序”“递归调用”均不符合本段堆排序代码。其调整对象是以i为根的子树，也不是数组下标i～n组成的任意连续区间。

对给定8个元素，建堆时按i=4、3、2、1处理，得到（6）(20，15，19，10，4，13，7，8)。交换20与末元素8后，对前7个元素下沉，得到（7）(19，15，13，10，4，8，7，20)，最后的20已排定而不再属于堆。

原题首行确为单独的#include，没有头文件名；测试主函数、int main、return 0及最后闭括号均完整，随后进入问题1。该预处理指令残缺，原段直接编译仍会失败；补写#include <stdio.h>属于整理修正，不是原题原文。平台解析开头误称“归并排序”也已核实为原页错误。MAXITEM=100而R[0]作临时单元，所以此数组最多容纳99个有效待排元素。代码注释虽说下标0闲置，算法实际会读写R[0]。

2022年上半年 · 第 4 题：矩阵链乘的计算顺序

展开原题（先作答，再查看解析）

矩阵链乘的计算顺序

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
某工程计算中经常要完成多个矩阵相乘（链乘）的计算任务，对矩阵相乘进行以下说明。
（1）两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定，假设采用标准的矩阵相乘算法，计算Amxn*Bnxp需要m*n*p次行乘法运算的次数决定、乘法运算，即时间复杂度为O（m*n*p）。
（2）矩阵相乘满足结合律，多个矩阵相乘时不同的计算顺序会产生不同的计算量。以矩阵A1 _5×100 ，A2 _100*8 ，A3 _8x50 三个矩阵相乘为例，若按（A1*A2）*A3计算，则需要进行5*100*8+5*8*50=6000次乘法运算，若按A1*（A2*A3）计算，则需要进行100*8*50+5*100*50=65000次乘法运算。
矩阵链乘问题可描述为：给定n个矩阵，对较大的n，可能的计算顺序数量非常庞大，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若A1*A2**An的一个最优计算顺序从第k个矩阵处断开，即分为A ₁ *A ₂ *…*A _k 和A _k+1 *A _k+2 *...*A _n 两个子问题，则该最优解应该包含 A ₁ *A ₂ *…*A _k 的一个最优计算顺序和 A _k+1 *A _k+2 *...*A _n 的一个最优计算顺序。据此构造递归式：

其中，cost[i][j]表示A _i+1 *A _i+2 *...A _j+1 的最优计算的计算代价。最终需要求解cost[0][n-1]。

【C代码】
算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量，然后依次计算3个矩阵、4个矩阵、…、n个矩阵相乘的最小计算量及最优计算顺序。下面是该算法的语言实现。
（1） 主要变量说明
n：矩阵数
seq[]：矩阵维数序列
cost[i][j]：二维数组，长度为n*n，其中元素cost[i][j]表示Ai+1*Ai+2**Aj+1的最优的计算代价。
trace[][]:二维数组，长度为n*n，其中元素trace[i][j]表示Ai+1*Ai+2**Aj+1的最优计算顺序对应的划分位置，即k。
（2）函数cmm

#define N100

int cost[N[N];

int trace[N][N];

int cmm(int n,int seq[]){

int tempCost;

int tempTrace;

int i,j,k,p;

int temp;

for( i=0;i < n;i++){ cost[i][i] = 0;}

for(p=1;p < n;p++){

for(i=0; i < n-p;i++){

（1）;

tempCost = -1;

for(k = i; （2）;k++){

temp= （3）;

if(tempCost==-1 || tempCost > temp){

tempCost = temp;

tempTrace=k;

}

}

cost[i][j] = tempCost;

（4）;

}

}

return cost[0][n-1];

}

【问题1】（8分）
根据以上说明和C代码，填充C代码中的空（1）～（4）。
【问题2】（4分）
根据以上说明和C代码，该问题采用了（5）算法设计策略，时间复杂度为（6）（用O符号表示）。
【问题3】（3分）
考虑实例n=4，各个矩阵的维数为A1为15*5，A2为5*10，A3为10*20，A4为20*25，即维度序列为15，5，10，20和25。则根据上述C代码得到的一个最优计算顺序为（7）（用加括号方式表示计算顺序），所需要的乘法运算次数为 （8）。

答案与解析

平台参考答案（原意保留）

【问题1】
（1） j=i+p
（2）k < j

（3） cost[i][k]+cost[k+1][j]+seq[i]*seq[k+1]*seq[j+1]
（4） trace[i][j] = tempTrace
【问题2】
（5）动态规划算法
（6）O（n ³ ）
【问题3】
（7）A1*((A2*A3)*A4)
（8）5375

解析与纠错

填空与状态定义。 （1）j = i + p；（2）k < j；（3）cost[i][k] + cost[k+1][j] + seq[i]*seq[k+1]*seq[j+1]；（4）trace[i][j] = tempTrace。（5）动态规划；（6）O(n³)。cost[i][j]处理从Aᵢ₊₁到Aⱼ₊₁的链，p是下标差，所以链长为p+1；在k处划分后，左、右结果维数分别为seq[i]×seq[k+1]和seq[k+1]×seq[j+1]。

单个矩阵不需要相乘，cost[i][i]=0。先求较短区间，才可使用其结果求较长区间；对每个区间枚举全部划分点。三重循环的总量为O(n³)，代价表和划分表的空间为O(n²)。

给定实例。 （7）A1*((A2*A3)*A4)；（8）5375。先算A2A3，花费5×10×20=1000；再乘A4，花费5×20×25=2500；最后与A1相乘，花费15×5×25=1875，共5375。原题开头的5×100、100×8、8×50示例对应6000与65000，也与标准矩阵乘法计数一致。

纠错。 平台解析把问题1、问题2的说明顺序写反，但参考答案的空号对应关系正确。“通过贪心策略尝试”只能帮助猜测，不能保证最优。例如维度2、3、7、3，先选眼前乘法次数最少的前两个矩阵，总代价42+42=84；先乘后两个则为63+18=81。动态规划应比较全部划分，不能以局部最小替代递推。

已回看原页确认，三处加粗行来自页面标题样式，标题标记不是代码字符；宏和数组声明本身仍有原始错误。原题中的宏和数组声明需改成#define N 100、int cost[N][N]才能得到可编译声明。int乘积也可能溢出，例如50000×50000×50000。补充实现保持相同区间状态和划分逻辑，改用64位无符号代价并检查每次乘加；遇到溢出的候选划分时跳过，仍寻找其他可表示的最优方案。所有候选均超出表示范围时才报告溢出。合法输入要求1≤n≤100、维度数为n+1且每一维大于0；单矩阵代价为0，空链不作为此接口的合法输入。

C17验证包括两组题内数值、单矩阵／双矩阵、等价最优方案、非法规模／零维度、重复调用、100矩阵、32位溢出示例、64位边界与溢出分支，以及240组小规模输入对所有括号方案的穷举比较。

补充与完整参考实现

平台解析附图（原图保留）：

以下是按题意编写并验证的完整修正示例，含填空之外的语法修正与边界处理。

#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>
#include <inttypes.h>

#define N 100
typedef struct {
    uint64_t cost[N][N];
    int trace[N][N];
    bool valid[N][N];
} MatrixPlan;
typedef enum { MC_OK, MC_INVALID, MC_OVERFLOW } MatrixStatus;

static bool mul_ok(uint64_t a, uint64_t b, uint64_t *result) {
    if (a && b > UINT64_MAX / a) return false;
    *result = a * b; return true;
}
static bool add_ok(uint64_t a, uint64_t b, uint64_t *result) {
    if (b > UINT64_MAX - a) return false;
    *result = a + b; return true;
}
MatrixStatus matrix_chain(size_t n, const uint64_t seq[], size_t length,
                          MatrixPlan *plan) {
    if (!seq || !plan || n == 0 || n > N || length != n + 1) return MC_INVALID;
    for (size_t i = 0; i < length; ++i) if (!seq[i]) return MC_INVALID;
    *plan = (MatrixPlan){0};
    for (size_t i = 0; i < n; ++i) {
        plan->valid[i][i] = true;
        plan->trace[i][i] = -1;
    }
    for (size_t p = 1; p < n; ++p) {
        for (size_t i = 0; i + p < n; ++i) {
            size_t j = i + p;
            for (size_t k = i; k < j; ++k) {
                uint64_t product, subtotal, candidate;
                if (!plan->valid[i][k] || !plan->valid[k + 1][j]) continue;
                if (!mul_ok(seq[i], seq[k + 1], &product) ||
                    !mul_ok(product, seq[j + 1], &product) ||
                    !add_ok(plan->cost[i][k], plan->cost[k + 1][j], &subtotal) ||
                    !add_ok(subtotal, product, &candidate)) continue;
                if (!plan->valid[i][j] || candidate < plan->cost[i][j]) {
                    plan->valid[i][j] = true;
                    plan->cost[i][j] = candidate;
                    plan->trace[i][j] = (int)k;
                }
            }
        }
    }
    return plan->valid[0][n - 1] ? MC_OK : MC_OVERFLOW;
}
void print_order(const MatrixPlan *plan, size_t i, size_t j) {
    if (i == j) { printf("A%zu", i + 1); return; }
    size_t k = (size_t)plan->trace[i][j];
    putchar('('); print_order(plan, i, k); putchar('*');
    print_order(plan, k + 1, j); putchar(')');
}
#ifndef MATRIX_NO_MAIN
int main(void) {
    const uint64_t seq[] = {15, 5, 10, 20, 25};
    MatrixPlan plan;
    if (matrix_chain(4, seq, 5, &plan) != MC_OK) return 1;
    print_order(&plan, 0, 3);
    printf("\ncost=%" PRIu64 "\n", plan.cost[0][3]);
    return 0;
}
#endif

2021年下半年 · 第 4 题：字符串编辑距离的程序填空

展开原题（先作答，再查看解析）

字符串编辑距离的程序填空

生物学中可用编辑距离衡量两个物种DNA序列的相似性，以刻画进化关系。编辑距离是把一个字符串变成另一个字符串所需的最少操作数，每次操作可插入一个字符、删除一个字符，或把一个字符替换为另一个字符。

字符数组str1、str2的长度分别为len1、len2；二维数组d保存子问题的最优解，其递推定义如下图。

C程序中的A、B为两个字符数组，d为二维数组，i、j为循环变量，temp为临时变量。

#include <stdio.h>

#define N 100

char A[N]="CTGA";

char B[N]="ACGCTA";

int d[N][N];

int min(int a, int b){

return a < b? a: b;

}

int editdistance(char *str1, int len1, char *str2, int len2){

int i, j;

int diff;

int temp;

for(i=0; i<=len1; i++){

d[i][0]=i;

}

for(j=0; j<=len2; j++){

(1);

}

for(i=1;i<=len1;i++){

for(j=1; j<=len2; j++){

if( (2) ){

d[i][j]=d[i-1][j-1];

}else{

temp=min(d[i-1][j]+1, d[i][j-1]+1);

d[i][j]=min(temp, (3) );

}

}

}

return (4);

}

【问题1】（8分）根据说明和代码，填写空(1)～(4)。

【问题2】（4分）算法采用(5)设计策略，时间复杂度为(6)。用O符号表示复杂度，两个字符串的长度分别记为m、n。

【问题3】（3分）A="CTGA"、B="ACGCTA"时，两者的编辑距离为(7)。

答案与解析

平台参考答案（原文保留）

问题1：
(1) d[0][j]=j
(2) str1[i-1]==str2[j-1]
(3) d[i-1][j-1] +1
(4) d[len1][len2]
问题2：
（5）动态规划法 （6）O(mn)
问题3：
（7）4

解析与纠错

设d[i][j]为str1前i个字符变成str2前j个字符的最少操作数。空串变成长度j的前缀需插入j次，所以(1)填d[0][j]=j；末字符相同无需增加操作，故(2)填str1[i-1]==str2[j-1]。不同时分别比较删除、插入、替换的代价，其中(3)为d[i-1][j-1]+1；最终(4)返回d[len1][len2]。

(5)为动态规划法。两层主循环枚举m×n个子问题，每格用常数时间计算，通常写(6)为O(mn)；连同空串边界初始化，完整计数是O(mn+m+n)。按字符串长度配置二维表时，需要O((m+1)(n+1))空间，通常简写为O(mn)。本段实际固定N=100，必须使两字符串长度均不超过99，以容纳下标0到长度的边界行列。

(7)为4。例如把B="ACGCTA"开头的ACG删除，再在末尾A前插入G，便得到"CTGA"，共4次操作；动态规划验证不存在更少的操作。填空后的函数已与独立的最短编辑路径计算及空串、相同串、99字符边界等用例核对。

公式图把边界条件写成len2=0、len1=0，作为每个子问题d[i][j]的通用递推并不严谨，正确边界应针对前缀下标：d[i][0]=i、d[0][j]=j。图中第一字符串还写为str，与程序的str1命名不一致。原图保留，按程序的初始化和字符串名理解。平台长解析中的d[i-1][i]等下标也是笔误；删除分支应为d[i-1][j]+1。原题给的是完整函数片段，不要求自带main；测试入口是另加的验证代码。

2021年上半年 · 第 4 题：凸多边形三角剖分的程序填空

展开原题（先作答，再查看解析）

凸多边形三角剖分的程序填空

凸多边形内任意两点的连线均位于其边界或内部；相邻顶点间的线段是边，不相邻顶点间位于内部的线段是弦。任意两顶点间都有权重。最优三角剖分要求把凸多边形划为内部互不相交的三角形，使全部三角形的权重之和最小；每个三角形的权重等于三条边的权重之和。

设N个顶点依次为V₁、V₂、…、V_N。在V_k处分出三角形V₁V_kV_N，以及两个子多边形V₁、…、V_k和V_k、V_k+1、…、V_N。若整体剖分最优，其中应包含两个子多边形的最优剖分。

用m[i][j]表示V_i−1、V_i、…、V_j所构成多边形的最优权重，用S[i][j]记录分割位置k。递推定义如下。

其中W(V_i−1V_kV_j)=W_i−1,k+W_k,j+W_j,i−1，这三项分别是三角形三条边的权重。需要求出最小总权重及对应的三角形集合。

下面给出C代码。

＃include ＜ stdio.h＞

＃define N 6 //凸多边形规模

int m[N＋1] [N＋1]; //m[i][j]表示多边形V

i-1

到V

j

最优三角剖分的权值

int S[N＋1] [N＋1]; //S[i][j]记录多边形V

i-1

到V

j

最优三角剖分的k值

int W[N＋1] [N＋1]; //凸多边形的权重矩阵，在main函数中输入

/*三角形的权重a，b，c，三角形的顶点下标*/

int get_ triangle_weight（int a，int b，int c）

{  
return W[a][b]＋W[b][c]＋W[c][a];  
}  
/*求解最优值*/  
void triangle_partition(){  
int i,r,k,j;  
int temp;  
/*初始化*/  
for(i=1;i < =N;i++){  
m[i][i]=0;  
}  
/*自底向上计算m，S*/  
for(r=2;（1）;r++)

{ /*r为子问题规模*/  
for(i=1;i < =N-r+1;i++)

{  
（2）;  
m[i][j]= m[i][i]+m[i+1][j]+get_triangle_weight(i-1,i,j); /*k=i*/  
S[i][j]=i;  
for(k=i+1;k < j;k++)

{ /*计算 [i][j]的最小代价*/  
temp=m[i][k]+m[k+1][j]+ge_triangle_ weight(i-1,k,j);  
if((3))

{ /*判断是否最小值*/  
m[i][j]=temp;  
S[i][j]=k;  
}  
}  
}  
}  
}  
/*输出剖分的三角形i，j：凸多边形的起始点下标*/  
void print_triangle(int i,int j){  
if(i==j) return;  
print_triangle(i,S[i][j]);  
print_ triangle((4));  
print(“V%d- -V%d- -V%d\n“,i-1,S[i][j],j);  
}

【问题1】（8分）填写代码中的空（1）～（4）。

【问题2】（7分）算法采用的设计策略为（5），时间复杂度为（6），空间复杂度为（7）；复杂度用O表示。

答案与解析

平台参考答案（原文保留）

【问题1】（8分）
(1)r < =N或其等价表示形式
(2)j=i+r-1或其等价表示形式
(3)temp < m[i][j] 或其等价表示形式
(4)s[i][j]+1,j或其等价表示形式
【问题2】（7分）
(5)动态规划法
(6)O(n ³)
(7)O(n ²)

解析与纠错

按给定程序的循环结构，(1)的算法意图是r<=N，(2)为j=i+r-1，(3)为temp<m[i][j]。S[i][j]记录最优分割k，左子问题为(i,k)，右子问题为(k+1,j)，因此(4)应写S[i][j]+1,j。平台第(4)空给小写s，与声明的S不同；C区分大小写，这里必须说明修正，不能将平台原答案直接称为可编译答案。

(5)为动态规划。由短区间向长区间计算，每个区间枚举分割位置，时间复杂度为O(n³)；m、S以及权重矩阵均为二维规模，空间复杂度为O(n²)。回溯两个子区间并输出本次三角形，即能得到达到最小权重的三角形集合。

顶点数量与下标的口径不一致：文字说N个点V1～VN，但循环还会计算m[1][N]，按定义该项对应V0～VN，共N+1个点。若把它作为整题结果并调用print_triangle(1,N)，N=6就会得到7点多边形的5个三角形；原段没有给出main或最终调用，不能擅称这就是6点题的实际输出。按文字的V1～VN，目标应是m[2][N]及print_triangle(2,N)，并可排除不需要的V0相关计算；也可统一改用0～N−1编号。这是下标约定的整理说明，不改平台填空。

当前代码还含全角预处理符与标点、get_ triangle_weight/ge_triangle_ weight等函数名、print_ triangle、print以及引号问题。仅填空不能使其编译；原代码保留。测试用整理版本统一了这些语法、标识符及S的大小写，并把区间上界作为参数区分顶点数与区间数，明确属于修正版。该版本通过对全部候选三角剖分的穷举最优值比较，并验证回溯三角形数、边计数、无交叉及权重和；结果不证明原段可直接编译。

原页已核实上述顶点编号、N=6、全角符号及函数名写法；循环中的i < =N、i < =N-r+1和平台第(1)空的r < =N也原样如此。C的“小于等于”运算符应连续写为<=。平台第(4)空确用小写s；原段在末尾print及闭括号后直接进入问题1，没有main。此处保留的是带原题错误的函数片段，不能把整理版当成原文。

2020年 · 第 4 题：希尔排序程序填空

展开原题（先作答，再查看解析）

希尔排序程序填空

题干将希尔排序称为“最小增量排序算法”，给出的过程如下。

1. 构造步长delta₁、delta₂、…、delta_k：delta₁=n/2，此后每项为前一项的½，最后一项为1。
2. 按步长序列进行k趟排序。
3. 第i趟使用对应步长delta，将等步长位置的元素分组，各组在原位置上做直接插入排序。

变量说明：data为待排序数组，长度n，元素位于data[0]～data[n−1]；n的说明原写为“数组a中的元素个数”；delta是步长数组。给出的C程序如下。

#include < stdio.h >  

void shellsort(int data[ ], int n){  
int *delta,k,i,t,dk,j;  
k=n;  
delta=(int *)malloc(sizeof(int)*(n/2));  
i=0;  
do{  
( 1 );  
delta[i++]=k;  
}while ( 2 );  
i=0;  
while((dk=delta[i]) > 0){  
for(k=delta[i];k < n;++k)  
if( ( 3 ) ) {  
t=data[k];  
for(j=k-dk;j > =0&&t < data[j];j-=dk){  
data[j+dk]=data[j];  
}  
( 4 );  
}  
++i;  
}  
}

【问题1】填写C代码的空（1）～（4）。

【问题2】该算法时间复杂度（5）O(n²)（选择“小于、等于或大于”）；该算法是否稳定（6）（选择“是或否”）。

【问题3】用上述希尔排序处理数组（15、9、7、8、20、−1、4），第一趟结束后的数组为（7）。

答案与解析

平台参考答案（原文保留）

【问题1】（8分）
（1）k=k/2
（2）k > 1
（3）data[k] < data[k-dk]
（4）data[j+dk]=t
【问题2】（4分）
（5）小于
（6）否

【问题3】（3分）
（7）(4，9，-1，8，20，7，15)

解析与纠错

四个填空的算法意图依次为k=k/2、k>1、data[k]<data[k-dk]、data[j+dk]=t。先生成整数折半步长，再按每个步长做分组插入；内层循环结束时，j+dk就是暂存值t的插入位置。

n=7时第一趟步长为3。下标0、3、6的组为（15，8，4），排序后变成（4，8，15）；下标1、4的组（9，20）不变；下标2、5的组（7，−1）变为（−1，7）。回填原位置得到（4，9，−1，8，20，7，15），与平台答案一致。

平台第(5)空给“小于”，长解析又给约O(n^1.3)；这不能作为本题折半增量的通用复杂度结论。该增量序列最坏时间为Θ(n²)，尤其未指定平均、最好或最坏情形时，不能笼统比较“大O的大小”。例如n为2的幂，偶数位置依次放递增的大数，奇数位置依次放递增的小数：所有大于1的步长都是偶数，各组已各自有序，但最后步长1仍需处理Θ(n²)个逆序。因此应区分平台所填“小于”与最坏情况的二次增长，不能用经验指数覆盖明确的增量条件。

希尔排序不稳定：如带身份标记的（2，1a，1b，0），步长2后可变为（1b，0，2，1a），最终排序得到（0，1b，1a，2），两个1的相对次序已颠倒。题干“最小增量排序”不是常用名称，通常称缩小增量排序。

原页代码还有独立于填空的风险：步长数组生成后没有写入0哨兵，也没有用已生成步长数限制读取，while会继续读未初始化项或越界；n=2时一项数组用完后即访问delta[1]，n<2时还可能写入零长度分配区。另有malloc所需声明、头文件写法、分开的“> =”及未释放delta等问题。原页已核实仅有#include < stdio.h >，没有stdlib.h；do/while后直接进入上述读取循环，末尾++i;及两个闭括号后即问题1，没有free或main。这是完整的原题函数片段，错误不能归为遗漏的后续代码。题干名称、复杂度问法和平台“小于、约O(n^1.3)”也均已核实。测试用修正版直接按n/2、n/4、…、1迭代步长，避免动态数组和终止哨兵，并处理n<2；整理修正不作为原题原文。

2019年下半年 · 第 4 题：0-1背包的C程序填空

展开原题（先作答，再查看解析）

0-1背包的C程序填空

0-1背包问题给定i个物品的价值v[1…i]、小重量w[1…i]（原文写法）和容量T；每件物品只能选择装入或不装入，要求总价值最大。

该问题具有最优子结构。c[i][T]表示最优装包方案的最大价值，递归式如下。

C程序的变量含义：T为背包容量，v[]为价值数组，w[]为重量数组，c[i][j]为前i个物品在容量j时可取得的最大价值。

#include <stdio.h>

#include <math.h>

#define N 6

#define maxT 1000

int c[N][maxT]={0};

int Memoized_Knapsack(int v[N],int w[N],int T){

int i;

int j;

for(i=0;i<N;i++){

for(j=0;j<=T;j++){

c[i][j]=-1;

}

}

return Calculate_Max_Value(v,w,N-1,T);

}

int Calculate_Max_Value(int v[N],int w[N],int i,int j){

int temp =0;

if(c[i][j]!=-1){

return (1);

}

if(i==0||j==0){

c[i][j]=0;

}else{

c[i][j]= Calculate_Max_Value(v,w,i-1,j);

if( (2) ){

temp= (3);

if(c[i][j] < temp){

(4);

}

}

}

return c[i][j];

}

【问题1】（8分）按说明及C代码填写空（1）～（4）。

【问题2】（4分）算法采用（5）设计策略；求解方向是（6）（选择“自底向上”或“自顶向下”）。

【问题3】（3分）5件物品的数组为v[]={0，1，6，18，22，28}、w[]={0，1，2，5，6，7}，背包容量T=11，最大价值为（7）。

答案与解析

平台参考答案（原文保留）

【问题1】
（1）c[i][j]
（2）i > 0&&j > =w[i]
（3）Calculate_Max_Value(v, w, i-1, j-w[i] ) + v[i]
（4）c[i][j]=temp
【问题2】

（5）动态规划
（6）自顶向下
【问题3】
（7）40

解析与纠错

缓存已计算时，(1)返回c[i][j]。先递归求不选第i件的价值，再在放得下时求选入它的价值；所以(2)按平台为i>0&&j>=w[i]，(3)为Calculate_Max_Value(v,w,i-1,j-w[i])+v[i]。若后者较大，(4)将temp存入c[i][j]。i>0在该else分支已由边界判断保证，保留它不影响结果。

用缓存消除重复子问题属于(5)动态规划；从(N−1,T)向更小子问题递归，是(6)自顶向下的记忆化搜索。数组0号项是占位，实际物品为1～5。T=11时，选择物品3、4，重量5+6=11，价值18+22=40。若选物品5，剩余容量4最多再取物品1、2，总价值35；不选5而选3、4得40，故(7)为40。

平台答案(2)写成分开的“> =”，C中应写连续的>=。所给程序在调用Calculate_Max_Value之前没有可见的声明，现代C需加函数原型；这属于编译整理，不能伪称仅填空后的原文已可直接编译。原页已核实：stdio/math头文件、N/maxT宏及全局c后直接定义Memoized_Knapsack，确无该函数前置声明；最后return c[i][j];及闭括号后即问题1。所给函数片段完整，不能将这些错误归为后续代码遗漏。

数组第二维maxT=1000，而初始化访问到j=T，故容量有效下标为0～999；T=1000会越界。算法还以非负整数容量、正整数重量及不溢出的价值计算为通常适用条件；题目未明确这些边界，不能擅自在可见题干追加。若允许零重量正价值物品，j=0直接返回0的边界也需要修改。

2019年上半年 · 第 4 题：n皇后的C程序填空

展开原题（先作答，再查看解析）

n皇后的C程序填空

n皇后问题要求在n×n棋盘上摆放n个皇后，任意两者不在同一行、同一列或同一斜线上。

算法从第1行开始，第i个皇后放在第i行，每行从第1列依次尝试。若与前面皇后不冲突，就放下并尝试下一行；冲突则改试下一列。若本行无可用位置，退回上一个皇后，在其原位置的下一列继续尝试，直至找到全部合理方案。

变量说明：n是皇后数和棋盘边长；queen[]保存摆放位置，queen[i]为第i个皇后的位置，满足1≤queen[i]≤n。C程序如下。

#include < stdio.h >  
#define n 4  
int queen[n+1];  

void Show(){ /* 输出所有皇后摆放方案 */  
int i;  
printf("(");  
for(i=1;i < =n;i++){  
printf(" %d",queen[i]);  
}  
printf(")\n");  
}  
int Place(int j){ /* 检查当前列能否放置皇后，不能放返回0，能放返回1 */  
int i;  
for(i=1;i < j;i++){ /* 检查与已摆放的皇后是否在同一列或者同一斜线上 */  
if( ( （1） ) ‖ abs(queen[i]-queen[j]) == (j-i) ) {  
return 0;  
}  
}  
return （2）;  
}  
void Nqueen(int j){  
int i;  
for(i=1;i < =n;i++){  
queen[j] = i;  
if( （3） ){  
if(j == n) { /* 如果所有皇后都摆放好，则输出当前摆放方案 */  
Show();  
} else { /* 否则继续摆放下一个皇后 */  
（4）;  
}  
}  
}  
}  

int main(){  
Nqueen (1);  
return 0;  
}

【问题1】（8分）根据说明填写C代码空（1）～（4）。

【问题2】（3分）算法采用的设计策略为（5）。

【问题3】（4分）n=4时共有（6）种摆放方式，分别为（7）。

答案与解析

平台参考答案（原文保留）

【问题1】
（1）queen[i]==queen[j]或其等价形式
（2）1
（3）Place(j)或其等价形式
（4）Nqueen(j+1)
【问题2】
（5）回溯法
【问题3】
（6）2
（7）（2413）或（2,4,1,3）
（3142）或（3,1,4,2）

解析与纠错

queen[j]表示第j行皇后所处的列；逐行摆放已保证行不同。对前面第i行检查时，同列冲突为queen[i]==queen[j]，斜线冲突为两列差的绝对值等于行差j−i，所以(1)填同列条件。所有检查通过后(2)返回1；(3)调用Place(j)验证当前摆放，未到最后一行则(4)调用Nqueen(j+1)。依次试列、失败返回上一层，是(5)回溯法。

n=4只有(6)两种结果：(7)为(2,4,1,3)和(3,1,4,2)，序列按行列出列号，不能把顺序当成任意可交换的集合。原解析的答案图如下，仅在展开后查看。

所给C代码的头文件名空格、分开的< =、表示逻辑或的‖需要分别整理为标准头文件、<=、||，abs还需stdlib.h声明。只有填四空不能修复这些独立问题；测试版本明确补充编译依赖并修正排版，题面仍保留原写法。原页已核实仅有stdio头文件，没有stdlib；i < =n、‖均为原写法。Show、Place、Nqueen与main完整，Nqueen(1);return 0;}后即问题1，没有遗漏后续代码。

2018年下半年 · 第 4 题：RNA最大配对的C程序填空

展开原题（先作答，再查看解析）

RNA最大配对的C程序填空

给定字符序列B=b₁b₂…b_n，每个b_i∈{A,C,G,U}。二级结构S是一组字符对{(b_i,b_j)}，i、j∈{1,2,…,n}，满足以下四项条件。

1. 每对字符只能为(A,U)、(U,A)、(C,G)、(G,C)之一。
2. 配对字符之间至少隔四个字符，即i < j−4。
3. 对每个字符b_k，题目列出两种配对情形：不参与配对，或与满足t < k−4的字符b_t配对。
4. 配对不交叉：若(b_i,b_j)与(b_k,b_l)均在S中且i < k，则不得出现i < k < j < l。

字符对数最多的S称为最优配对方案。用C(i,j)表示子序列b_ib_i+1…b_j的最大配对数，原题给出如下递归式。

C程序中，n是序列长度，B[]保存字符序列，C[][]保存最优配对数量。

#include < stdio.h >  
#include < stdlib.h >  
#define LEN 100  

/*判断两个字符是否配对*/  
int isMatch(char a,char b){  
if((a ==‘A’ && b == ‘U’) || (a == ‘U’ && b == ‘A’))  
return 1;  
if((a == ‘C’ && b == ‘G’) || (a == ‘G’ && b == ‘C’))  
return 1;  
return 0;  
}  

/*求最大配对数*/  
int RNA_2(char B[LEN], int n){  
int i,j,k,t;  
int max;  
int C[LEN][LEN] = {0};  

for(k = 5; k <= n-1; k++){  
for(i = 1;i <=n-k; i++){  
j = i+k;  
(1);  
for( (2) ；t <= j-4; t++){  
if( (3) && max < C[i][t - 1] + 1 + C[t+1][j-1])  
max = C[i][t-1] + 1 +C[t+1][j-1];  
}  
C[i][j] = max;  
printf(“c[%d][%d] = %d--”, i,j, C[i][j]);  
}

}  
return(4);

}

【问题1】（8分）填写C代码空（1）～（4）。

【问题2】（4分）算法设计策略为（5），时间复杂度为（6）（用O表示）。

【问题3】（3分）字符序列ACCGGUAGU按上述算法求得的最大字符对数为（7）。

答案与解析

平台参考答案（原文保留）

【问题1】
（1）max=C[i][j-1]
（2）t=i
（3）isMatch(B[t],B[j])，或isMatch(B[t],B[j])==1，或与其等价的形式
（4）C[1][n]
【问题2】
采用的算法策略：动态规划法
时间复杂度：O(n ³)
【问题3】
最大字符对数：2

解析与纠错

先假设右端字符j不配对，(1)令max=C[i][j-1]；(2)从t=i枚举候选。若b_t与b_j匹配，(3)调用isMatch(B[t],B[j])；选这对后，不交叉条件把其余问题分为[i,t−1]与[t+1,j−1]，总数加1。最后(4)返回C[1][n]。

(5)为动态规划。外层按区间长度增加，中层枚举左端，内层枚举配对点，故(6)时间为O(n³)，表空间O(n²)。原解析把j范围写到n−1、把k起点写成6，均与代码不同；代码k从5到n−1，j最多到n。

原题配对间至少四个字符，要求j−t≥5，即t<j−4。但代码写t<=j−4，会允许只隔三个字符，不能用正确的填空掩盖这个循环边界错误。例如CACCCU中，A在位置2、U在位置6，只隔3个字符；题意最大配对为0，原循环却返回1。学习修正版将内层条件改成严格小于，并与独立枚举核对。

原公式图没有写出内层max的完整t范围，而且把“有匹配”放在整个分段条件中；严谨递推应始终保留不配对项C(i,j−1)，再对i≤t<j−4且两字符匹配的候选取最大值，短区间或空区间为0。文字第3项按“以右端字符作是否配对分类”理解，核心是每个位置至多参与一对，不能让一个字符重复使用。

给定ACCGGUAGU可取(1,9)与(2,8)，或(1,9)与(3,8)，所以(7)为2；两组均满足正确间距和不交叉。该例没有暴露上述边界错误。平台长解析“不交叉”段还写“位置能交叉”，与规则相反，应为不能交叉。

原页已核实文字条件i<j−4、k从5开始及内层t<=j−4，等号与全角分号确为原写法。头文件空格、弯引号等排版问题只在测试版明确整理。函数以return(4);及闭括号结束后即问题1，没有后续main或数组初始化代码；该函数来源完整。代码按1开始访问B、C；LEN=100时应限制n≤99，并在输入中留出0号位置，不能直接将普通从0开始的字符串当作同一布局。

2018年上半年 · 第 4 题：钢条切割收益的C程序填空

展开原题（先作答，再查看解析）

钢条切割收益的C程序填空

某公司购买长钢条，切割后出售，切割成本忽略不计，长度以整英寸计。价格表p中，p_i（i=1,2,…,m）表示长度i英寸钢条的价格，求最大销售收益对应的切割方案。

对于长n英寸的钢条，先令最左段长i英寸，再求余下n−i英寸的最佳切割方案；枚举所有i以得到最大收益r_n。原题递推式为：

r_n=max_1≤i≤n（p_i+r_n−i）

以下C代码分别采用自顶向下、自底向上方式实现。

/* 常量和变量说明  
n：长钢条的长度  
p[]：价格数组  
*/  
#define LEN 100  

int Top_Down_ Cut_Rod(int p[],int n){ /*自顶向下*/  
int r=0;  
int i;  
if(n == 0){  
return 0;  
}  
for(i=1; （1）;i++){  
int tmp = p[i]+Top_Down_Cut_Rod(p,n-i);  
r=(r > =tmp)?r：tmp;  
}  
return r;  
}  

int Bottom_Up_Cut_Rod(int p[],int n){ /*自底向上*/  
int r[LEN]={0};  
int temp=0;  
int i,j;  
for(j=1;j < =n;j++){  
temp=0;  
for(i=1; （2）;i++) {  
temp= （3）;  
}  
（4）;  
}  
return r[n];  
}

【问题1】（8分）填写C代码中的空（1）～（4）。

【问题2】（7分）算法采用的设计策略为（5）；求r_n时，自顶向下方法的时间复杂度为（6），自底向上方法为（7），均用O表示。

答案与解析

平台参考答案（原文保留）

【问题1】
（1）i < =n
（2）i < =j

（3）(temp > =p[i]+r[j-i])?temp:(p[i] + r[j - i])或其等价形式

（4）r[j] = temp

【问题2】
（5） 动态规划法
（6）O(2 ⁿ)
（7）O(n ²)

解析与纠错

(1)枚举第一段长度1～n，填i<=n；(2)求长度j的最优值时枚举1～j，填i<=j。(3)比较本轮已有最大值temp与p[i]+r[j−i]；(4)把最大值存入r[j]。相同子问题的最优值能够用于更长钢条，平台(5)归为动态规划。

但所示Top_Down_Cut_Rod没有记忆表，每次都会重算子问题，是朴素递归；不能因为写着“自顶向下”就说已经记忆化。其递归调用数满足A(0)=1、A(n)=1+ΣA(k)，k从0到n−1，所以A(n)=2ⁿ，(6)为O(2ⁿ)。Bottom_Up_Cut_Rod把子问题值保存在r中，两重循环共n(n+1)/2次，(7)为O(n²)；按n扩展数组时辅助空间为O(n)，递归版栈深也是O(n)。

函数定义Top_Down_ Cut_Rod含空格，与递归调用名不同；分开的<=、>=和全角冒号不能作为对应的C运算符直接编译，测试版明确整理。平台长解析还把(3)三目式写成不配对括号，参考答案中的三目式结构才是有效表达式。原页已核实这些字形；仅有LEN常量定义，无头文件，也未补充m≥n约束。第二函数以return r[n];及闭括号结束后即问题1，没有main、初始化或记忆表，来源完整。

价格只给到m，循环却访问到n，使用原代码需保证0≤n≤m；r[LEN]的LEN=100还要求n≤99。初始化最优值为0隐含价格非负或允许放弃销售；若要求全部钢条出售且价格可为负，n=1、p[1]=−5时原代码返回0而不是−5。题干未给负价情形，例子仅用于说明实现适用条件，不能补进题干。int相加还应处于可表示范围，题面没有给出溢出处理。

2017年下半年 · 第 4 题：Hamilton回路的C程序填空

展开原题（先作答，再查看解析）

Hamilton回路的C程序填空

无向连通图G中的哈密尔顿（Hamilton）回路，从某一顶点出发，将其余所有顶点各访问一次且仅一次，最后回到出发点。

设存在从V₀出发的回路V₀—V₁—…—V_n−1—V₀。算法从V₀访问未访问的邻接顶点V₁，再逐步访问后续未访问邻点；对V_i，若全部邻点均已访问，就退回V_i−1并尝试其下一个未访问邻点，仍记为V_i，直至找到一条回路或确定找不到。

变量说明：n为顶点数，c[][]为邻接矩阵；k为统计变量，原题称当前已访问顶点数为k+1；x[k]保存第k个访问的顶点编号，从0开始；visited[x[k]]取0表示未访问，取1表示已访问。

C程序如下。

#include < stido.h > 
#include < stidb.h > 
#define MAX 100 

void Hamilton（int n,int x［MAX], int c[MAX][MAX]）｛ 
int i; 
int visited[MAX]; 
int k; 
/*初始化x数组和visited数组*/ 
for （i=0:i < n;i++）｛ 
x[i]=0; 
visited [i]=0; 
｝ 
/*访问起始顶点*/ 
k=0 
（1）； 
x[0]=0; 
k=k+1; 
/*访问其他顶点*/ 
while（k > =0）｛ 
x[k]=x[k]+1; 
while（x[k] < n）｛ 
if （（2）&& c [x[k-1]] [x[k]] ==1）｛/*邻接顶点x[k]未被访问过*/ 
break； 
｝else｛ 
x[k] = x[k] +1 
｝ 
｝ 
if（x[k] < n&&k==n-1&&（3）)｛ /*找到一条哈密尔顿回路*/ 
for （k=0;k < n;k++）｛ 
printf（〝%d--〝,x[k] ); /*输出哈密尔顿回路*/ 
｝ 
printf（〝%d\n〝,x[0] ); 
return； 
｝else if (x[k] < n&&k < n-1）｛/*设置当前顶点的访问标志，继续下一个顶点*/ 
（4） 
k=k+1;
｝else｛/*没有未被访问过的邻接顶点，回退到上一个顶点*/ 
x[k]=0； 
visited [x[k]]=0； 
（5）； 
｝ 
｝ 
｝

【问题1】（10分）填写C代码空（1）～（5）。

【问题2】（5分）算法采用的设计策略为（6）；遍历图顶点采用（7）方法，选择深度优先或广度优先。

答案与解析

平台参考答案（原文保留）

【问题1】 1、visited[0] = 1 2、visited[x[k]] == 0 3、c[x[k]] [0]== 1 4、visited[x[k]] = 1 5、k = k - 1 【问题2】 6、回溯法 7、深度优先

解析与纠错

(1)将起点visited[0]设为1；(2)要求候选visited[x[k]]为0；(3)检查最后顶点到0的边；(4)选择顶点后将其访问标志设为1；(5)将k减1退回上一层。(6)为回溯法，沿一条路径深入再撤销选择，(7)为深度优先。

正确填空并不能消除原循环的缺陷。回退分支先令x[k]=0，再清visited[x[k]]，实际清除的是visited[0]；上一层已选顶点仍被标记，换分支时无法再次使用。另一个边界是while(k>=0)：退到k=0后，若候选顶点仍未访问，&&的右侧会读取x[k−1]，触发负下标访问；若左侧均为假，短路会避开这一访问，但并不修复漏解。修正版需在回退时撤销上一层选择，并在退回固定起点后结束搜索；这些是循环修正，不替换平台五个填空。

例如无向图边集{0–1,0–2,0–3,1–2,1–3}存在回路0–2–1–3–0。原程序先试0–1–2，失败后没有清除正确的访问标记，会阻塞后续合法分支；不能因一次试探失败就说图没有回路。

原C还有stido.h/stidb.h拼写、for初始化后的冒号、全角标点、弯引号、分开的>=与缺少分号等问题；第(4)空所在行和平台该项答案都没有分号，编译测试需明确补齐。原页已核实这些符号和回退顺序；顶层首次x[k]=x[k]+1有分号，else中该语句缺分号。函数末三个闭括号后即问题1，没有main或后续代码，函数来源完整。测试只对简单无向图、3≤n≤100验证回路语义；原实现没有给n的合法性检查，使用固定MAX数组必须满足容量限制。

2017年上半年 · 第 4 题：查找较轻假币的C程序填空

展开原题（先作答，再查看解析）

查找较轻假币的C程序填空

有n枚硬币，其中恰好一枚是假币，且已知它较轻；只能使用天平，要求尽量少比较以找出假币。题目给出的处理方法如下。

• n为偶数：比较第1…n/2枚与第n/2+1…n枚，两组数量相等；在较轻的一组继续同样处理。
• n为奇数：比较第1…(n−1)/2枚与第(n+1)/2+1…n枚；若不等重，在较轻一组继续处理；若等重，则第(n+1)/2枚是假币。

以下为C程序。coins[]保存硬币，first、last分别是本次考虑区间的第一个、最后一个下标。

#include < stdio.h >  

int getCounterfeitCoin(int coins[]， int first，int last)  
{  
int firstSum = 0，lastSum = 0;  
int i;  
if(first==last-1){ /*只剩两枚硬币*/  
if(coins[first] < coins[last])  
return first;  
return last;  
}  

if((last - first + 1) % 2 ==0){ /*偶数枚硬币*/  
for(i = first;i < ( 1 );i++){  
firstSum+= coins[i];  
}  
for(i=first + (last-first) / 2 + 1;i < last +1;i++){  
lastSum += coins[i];  
}  
if( 2 ){  
return getCounterfeitCoin(coins,first,first+(last-first)/2;)  
}else{  
return getCounterfeitCoin(coins,first+(last-first)/2+1,last;)  
}  
}  
else{ /*奇数枚硬币*/  
for(i=first;i < first+(last-first)/2;i++){  
firstSum+=coins[i];  
}  
for(i=first+(last-first)/2+1;i < last+1;i++){  
lastSum+=coins[i];  
}  
if(firstSum < lastSum){  
return getCounterfeitCoin(coins,first,first+(last-first)/2-1);  
}else if(firstSum > lastSum){  
return getCounterfeitCoin(coins,first+(last-first)/2+1,last);  
}else{  
return( 3 )  
}  
}  
}

【问题1】（6分）根据说明填写代码空（1）～（3）。

【问题2】（6分）填写设计策略（ ），以及getCounterfeitCoin的时间复杂度（ ）（用O表示）。

【问题3】（3分）输入30枚硬币，最少比较次数为（ ），最多比较次数为（ ）。

答案与解析

平台参考答案（原文保留）

【问题1】
（1）first+(last-first)/2+1 或(first+last)/2+1
（2）firstSum < lastSum
（3）first+(last-first)/2 或(first+last)/2
【问题2】
（4）分治法
（5）O(lgn)
【问题3】
（6）2 （7）4

解析与纠错

令mid=first+(last−first)/2。偶数区间的左半部含mid，循环使用严格小于，所以(1)填mid+1；左半总重量较轻时递归左半，故(2)是firstSum < lastSum；奇数时两侧等重，假币就是中间位置，故(3)填mid。题目通常把不断分成更小子问题的策略归为分治法；这里每次实际只继续一个子区间。

平台复杂度O(lgn)与给定C代码不符。每层两个for合计读取当前区间的n或n−1枚硬币，即Θ(n)工作；最坏递推T(n)=T(⌊n/2⌋)+Θ(n)，总和n+n/2+n/4+…=Θ(n)。O(log n)描述递归层数和天平称量次数的量级，不是逐枚求和实现的总运行时间。平台原答案保留，代码时间复杂度应为O(n)。

按题目二分称量法，30→15：第一次15比15；第二次7比7若平衡，中心那枚是假币，最少2次；不平衡继续7→3，再比较1比1，最多4次。这里一次比较指天平称量，不是把C中if和循环判断逐条计数。题首“尽量少”也不能证明二分法对所有n都全局最优：例如9枚可三等分，最坏2次即可；原二分法最坏需3次。

原代码两条偶数分支递归调用把分号放入参数括号，末尾return空所在行没有分号，另有头文件内部空格与全角逗号。编译用整理版只修这些语法，不改变分支和区间。单枚区间虽然没有显式基例，但两个求和循环都不执行，落入等重分支仍返回该下标；空区间未定义，不纳入题目恰有一枚假币的条件。

原站可见页面截图已核实，两条偶数分支return的分号均位于右括号前，末尾return空所在行没有分号；三个闭括号之后直接是问题1，没有其他基例或后续代码。平台参考答案确为O(lgn)。来源完整；称重次数的O(log n)与逐元素求和代码整体的Θ(n)应分别理解，语法整理不冒充原题。

2016年下半年 · 第 4 题：字符串匹配的C程序填空

展开原题（先作答，再查看解析）

字符串匹配的C程序填空

模式匹配是在主串t中寻找子串s；s称为模式，成功返回其在t中的位置，否则返回−1。KMP用next数组优化匹配，给定过程如下。

1. 初始化比较下标i=j=0。
2. t、s均仍有待比较字符时循环：若j=−1或t[i]=s[j]，i、j各加1，继续比较后续字符；否则令j=next[j]，原题称将j向右滑动到next[j]的位置。
3. s全部比较完时，返回匹配起点，位置从1开始计；否则返回−1。

get_next已给出，用于从模式s计算next。t、s长度分别为lt、ls，next数组长度为ls。C程序如下。

#include < stdio.h > 
#include < stdlib.h > 
#include < string.h > 
/*求next[]的值*/ 
void get_next( int *next, char *s, int ls) { 
int i=0，j=-1; 
next[0]=-1;/*初始化next[0]*/ 
while(i < ls){/*还有字符*/ 
if(j==-1l ls[i]==s[j]){/*匹配*/ 
j++; 
i++; 
if( s[i]==s[j]) 
next[i] = next[j]; 
else 
Next[i] = j; 
} 
else 
j = next[j]; 
} 
} 
int kmp( int *next, char *t,char *s, int lt, int Is ) 
{ 
Int i= 0,j =0; 
while (i < lt && （1） ){ 
if( j==-1 || （2） ){ 
i ++; 
j ++; 
} else 
（3）; 
} 
if (j > = ls) 
return （4）; 
else 
return -1; 
}

【问题1】（8分）根据说明填写代码空（1）～（4）。

【问题2】（2分）主串、子串长度分别为lt、ls，用O记号填写kmp算法时间复杂度（5）。

【问题3】（5分）按代码计算字符串“BBABBCAC”的next数组（6），直接写元素值、以逗号分隔。主串为“AABBCBBABBCACCD”、子串为“BBABBCAC”时，函数Kmp的返回值为（7）。

答案与解析

平台参考答案（原文保留）

【问题1】 （1）：j < ls; （2）：t[i]==s[j]; （3）：j=next[j]; （4）：i-ls+1 或其等价形式; 【问题2】 （5）O(It+Is) 【问题3】 （6）：[-1,-1,1,-1,-1,2,0,0]，（7）6。

解析与纠错

(1)要求j < ls，(2)比较t[i]与s[j]，失配时(3)将j回退到next[j]；主串下标i不回退。完成匹配后j达到ls，i已指向刚匹配区间之后的位置，所以0起始下标为i−ls，题目按1计数则(4)为i−ls+1。平台解析说i指向最后一个已匹配字符不准确，但其返回公式是对的。原题“j向右滑动”指模式相对主串右移，j的数值通常减小，不是数值递增。

get_next中遇到相同字符会继续沿失败链接跳过，因此这里计算的是优化失败表，通常称nextval，不能套用未经优化的next表。模式BBABBCAC得到−1,−1,1,−1,−1,2,0,0；在AABBCBBABBCACCD中从第6个字符起匹配，返回6。

预处理失败表耗时O(ls)，匹配过程i不回退，总耗时O(lt)，包含预处理的KMP为O(lt+ls)，与平台通常口径一致。给出的kmp函数已接收next数组，若单独衡量该函数，预处理不在函数体内；平台O(lt+ls)仍是上界，宜说明采用的计时范围。

原get_next的while(i < ls)存在边界问题：最后一次i++使i变为ls后，循环体不会立即停止，仍比较s[i]并写next[i]，而题目只给next分配ls项。即使C字符串有末尾空字符可读，next[ls]仍越界；平台长解析把i加到ls后直接视作退出循环，漏看了本轮剩余语句。语法整理版已用地址检查确认写越界。明确修正版可将预处理循环限制为i < ls−1，仅填0…ls−1的表项；平台给出的八个值与该修正版一致，表值正确不代表原程序内存安全。

此外原条件j==-1l ls[i]、Next/Int/Is大小写、头文件空格、全角逗号及分开的>=不能直接照抄编译。测试分别保存原式、语法整理版和边界修正版，不将补正当原题。验证覆盖非空模式；空模式的语义和next容量需另作接口约定，原题未提供该边界处理。

原站可见页面截图已核实，get_next的while(i < ls)、字母l似符号的条件、Next/Int/Is字形及分开的>=均为原题写法；i递增后没有提前退出，继续比较字符并写next[i]。return -1及函数闭括号后直接是问题1，没有main或后续代码，来源完整。平台复杂度原文写O(It+Is)，题干长度变量为lt、ls；这里按两串长度说明复杂度，不改原答案字形。

2016年上半年 · 第 4 题：电路板不相交连线的C程序填空

展开原题（先作答，再查看解析）

电路板不相交连线的C程序填空

电路板上下各有n个接线柱，连线(i,π(i))把上端i与下端π(i)连接，称第i条连线。图4-1的排列为{8,7,4,2,5,1,9,3,10,6}。对任意1≤i < j≤n，两条连线相交当且仅当π(i) > π(j)。

制作电路板时，将n条连线分配到若干绝缘层，同层连线不能相交。现需选择一层上的连线，使其数量最多，即求Nets={(i,π(i))，1≤i≤n}的最大不相交子集。

记N(i,j)={t | (t,π(t))∈Nets，t≤i，π(t)≤j}，其最大不相交子集为MNS(i,j)，size(i,j)=|MNS(i,j)|。问题具有最优子结构，递推式如下。

C实现中，size[i][j]表示上端前i个、下端前j个接线柱范围内第一层最大不相交连接数；pi[i]对应π(i)，下标从1开始。

#include "stdlib.h"

#include < stdio.h >

#define N 10 /*问题规模*/

int m=0； /*记录最大连接集合中的接线柱*/

void maxNum(int pi[],int size[N+1][N+1],int n) {/*求最大不相交连接数*/

int i, j;

for(j=0; j < pi[1]; j++) size[1][j] = 0; /*当j < π(1)时 */

for(j=pi[1];j < =n;j++) （1）; /*当j > =π(1)时 */

for(i=2; i < n; i++) {

for(j=0; j < pi[i]; j++) （2）; /*当j < pi[i]时 */

for(j=pi[i];j < =n；j++) {/*当j > =c[i]时,考虑两种情况*/

size[i][j]=size[i-1][j] > =size[i-1][pi[i]-1]+1?size[i-1][j]:size[i-1][pi[i]-1]+1;

}

}

/*最大连接数 */

size[n][n]=size[n-1][n] > =size[n-1][pi[n]-1]+1? size[n-1][n]:size[n-1][pi[n]-1]+1;

}

/*构造最大不相交连接集合，net[i]表示最大不相交子集中第i条连线的上端接线柱的序号 */

void constructSet（int pi[],int size[N+1][N+1],int n,int net[n]）{

int i,j=n;

m=0；

for(i=n; i > 1; i--) { /*从后往前*/

if(size[i][j]!=size[i-1][j]){ /*(i,pi[i])是最大不相交子集的一条连线*/

（3）; /*将i记录到数组net中，连接线数自增1*/

j= pi[i]-1; /*更新扩展连线柱区间*/

}

}

if(j > =pi[1]) net[m++]=1; /*当i=1时*/

}

【问题1】（6分）根据说明与代码填写空（1）～（3）。

【问题2】（6分）算法采用的设计策略为（4）；maxNum、constructSet的时间复杂度分别为（5）、（6），用O表示。

【问题3】（3分）对图示排列{8,7,4,2,5,1,9,3,10,6}，最大不相交连接数为（7），包含的连线为（8），用(i,π(i))形式列出。

答案与解析

平台参考答案（原文保留）

【问题1】

（1）size[1][j]=1

（2）size[i][j]=size[i-1][j]

（3）net[m++]=i;

【问题2】

（4）动态规划法

（5）O(n ²)

（6）O(n)

【问题3】

（7）4
（8）（3，π（3），（5，π（5）），（7，π（7）），（9，π（9））
或：（3，4），（5，5），（7，9），（9，10）

解析与纠错

依上端序号从小到大取连线，其下端序号必须严格递增，才能两两不相交。递推区分第i条是否加入：j < π(i)时不能选它，沿用上一行；否则在“不选”的size[i−1][j]和“选”的size[i−1][π(i)−1]+1之间取大。

i=1时，j能覆盖π(1)就只有一条可选，所以(1)填size[1][j]=1；(2)沿用size[i−1][j]；回溯确定选第i条时，(3)把i记入net[m++]，再令j=π(i)−1以排除相交候选。平台第(3)项已带分号，代码空后也有分号，整理时只需一个；原答案字样保留。

该算法采用动态规划。maxNum填二维状态，为O(n²)；constructSet只沿i逆序走一次，为O(n)。原实现只单独计算第n行的size[n][n]，并未漏算回溯需要的整行：第一次从(n,n)决策后即进入第n−1行，后续所需行都已计算。

给定排列的最优值是4；代码回溯依次得到上端9、7、5、3，按升序写即(3,4)、(5,5)、(7,9)、(9,10)。最优子集可能不唯一，例如上端4、5、7、9也可形成四条不交叉连线；题答给出的是其中一组，不宜把其他最优组一概判错。平台第一套π记号的首项少一个右括号，后面的明确数对无歧义。

原代码中的全角符号、分开的比较运算符和头文件空格需整理才能编译，原文仍保留。此外，若将此函数推广到n=1，第一行初始化后又用第0行覆盖size[1][1]，而函数从未初始化第0行；题给n=10不受此边界影响。明确边界修正版可在第一行初始化后直接处理n=1并返回，不能宣称原程序对任意规模都已完整处理。

仅整理语法的版本已对n=2..8全部46,232个排列，用独立子集穷举验证最优值及回溯不相交性；增加单元素处理的版本覆盖n=1..8共46,233个排列。另核对n=10给定例、递增和递减排列，地址与未定义行为检查通过。

原站可见页面已核实上述循环边界、单独计算末项、原标点及函数结尾；已有首行初始化保留，结尾没有额外初始化或单元素处理。原解析首个π数对的右括号缺失也已确认。 参考答案（8）的第一套π记号也已核实首项缺右括号；其后明确数对完整，原答案两种写法均保留。

补充说明

平台解析给出的最优连线示意图，红线表示其所选的一组答案：

2015年上半年 · 第 4 题：皇后摆放的C程序

展开原题（先作答，再查看解析）

皇后摆放的C程序

在n行n列的棋盘上放置n个皇后，任意两个皇后不能在同一行、同一列或同一条对角线上。

第i个皇后固定放在第i行。从第一行开始，每个皇后由第一列向后尝试：若不与已放置皇后冲突，则确定位置并考虑下一行；冲突就尝试下一列；超过最后一列则回到上一行重新选择。重复直到找出全部方案。

变量含义：pos是一维数组，pos[i]记录第i行皇后所在的列；count统计方案数；i、j、k为变量；N为皇后数。所给C程序如下：

#include < stdio.h >

#include < math.h >

#define N4

/*判断第k个皇后目前放置位置是否与前面的皇后冲突*/

int isplace(int pos[], int k) {

int i;

for(i=1; i < k; i++) {

if( （1） || fabs(i-k) ══ fabs(pos[i] - pos[k])) {

return 0;

}

}

return 1;

}

int main() {

int i,j,count=1;

int pos[N+1];

//初始化位置

for(i=1; i < =N; i++) {

pos[i]=0;

}

（2） ；

while(j > =1) {

pos[j]= pos[j]+1；

/*尝试摆放第j个皇后*/

while(pos[j] < =N&& （3）_) {

pos[j]= pos[j]+1;

}

/*得到一个摆放方案*/

if(pos[j] < =N&&j══ N) {

printf("方案%d: ",count++);

for(i=1; i < =N; i++){

printf("%d ",pos[i]);

}

printf("\n");

}

/*考虑下一个皇后*/

if(pos[j] < =N&& （4） ) {

j=j+1;

} else{ //返回考虑上一个皇后

pos[j]=0;

（5）;

}

}

return 1;

}

【问题1】（10分）根据说明和代码填写（1）～（5）。

【问题2】（2分）算法采用的设计策略是（6）。

【问题3】（3分）上述代码的输出为（7）。

答案与解析

平台参考答案（原文保留）

【问题1】

（1）pos[i] ==pos[k]

（2）j=1

（3）isplace(pos,j)==0

（4）j < N

（5）j=j-1

【问题2】

（6）回溯法

【问题3】

（7）
方案1：2 4 1 3

方案2：3 1 4 2

解析与纠错

每行只放一个皇后，因此还需排除同列和同对角线：第（1）空为pos[i]==pos[k]，对角线由行差绝对值等于列差绝对值检查。第（2）空j=1，从第一行开始；第（3）空isplace(pos,j)==0表示当前位置冲突，需要继续增加列号；第（4）空j<N表示仍有下一行；第（5）空j=j-1回退上一行。

这是一种回溯搜索。位置合法就深入下一层，无可用列就撤销当前行并退回；列号按升序尝试，因此四皇后两组输出依次为2 4 1 3和3 1 4 2。

找到最后一行的一个解后立即回退，并不会漏掉同一前缀下的第二个解：前N−1行已有互不相同的N−1个列号，最后一行至多只剩一列可选。这一论证依赖每行、每列都只放一个皇后。

补充说明

原代码问题与修正条件：原题确实写作“#define N4”，N和4之间没有空格；两处“══”是相连双长横线，并非标准C的==。全角分号与拆开的“< =”“> =”也按原样保留，直接填入答案仍不能编译。上面的方案须按N=4及标准C标点、比较运算符解释，这些是明确的语法修正，不是原题原文。

第（3）空后的“_”表示填空横线向右延伸，不是变量名中的下划线，也不是需要补入的C符号。题面保留这一文本表示；把答案写入程序执行时应去除该填空标记。main在return 1及闭括号后即结束，没有遗漏后续代码；return 1使程序即使已打印正确方案，仍返回非零进程状态。

下面给出修正上述语法、填入答案并移除填空标记后的完整演示程序；它不是原题逐字原文。N=1～10已与独立求解程序比较，结果数依次为1、0、0、2、10、4、40、92、352、724。

#include <stdio.h>

#include <math.h>

#ifndef N
#define N 4
#endif

/*判断第k个皇后目前放置位置是否与前面的皇后冲突*/

int isplace(int pos[], int k) {

int i;

for(i=1; i < k; i++) {

if( pos[i] ==pos[k] || fabs(i-k) == fabs(pos[i] - pos[k])) {

return 0;

}

}

return 1;

}

int main() {

int i,j,count=1;

int pos[N+1];

//初始化位置

for(i=1; i <=N; i++) {

pos[i]=0;

}

j=1 ;

while(j >=1) {

pos[j]= pos[j]+1;

/*尝试摆放第j个皇后*/

while(pos[j] <=N&& isplace(pos,j)==0) {

pos[j]= pos[j]+1;

}

/*得到一个摆放方案*/

if(pos[j] <=N&&j== N) {

printf("方案%d: ",count++);

for(i=1; i <=N; i++){

printf("%d ",pos[i]);

}

printf("\n");

}

/*考虑下一个皇后*/

if(pos[j] <=N&& j < N ) {

j=j+1;

} else{ //返回考虑上一个皇后

pos[j]=0;

j=j-1;

}

}

return 1;

}

四皇后的示意图如下：

来源

• 回顾时间复杂度和空间复杂度（161720）
• 代码填空技巧（161721）
• 实战演练（161722）

图片来源、尺寸和 SHA256 见图片来源清单。概念、排序对照表和选择题见算法基础。

评论