代码填空技巧

2026/9/22大约 4 分钟

代码填空技巧

1. 考点：解题技巧

常见技巧：1、仔细看 2、编程经验 3、给变量代入数据，尝试在脑海中运行程序

1.1 解题技巧：仔细检查所有用到的变量。

1.1.1 题目

......
int main() {
    int i,j,count=1;
    int pos[N+1];
    for(i=1; i<=N; i++) { //初始化位置
        pos[i]=0;
    }
    (1) ;  //此处缺少j的初始赋值
    while(j>=1) {
        pos[j]=pos[j]+1;
            while(pos[j]<=N&& __) {/*尝试摆放第i个皇后*/
            pos[j]=pos[j]+1;
        }
    }
}

答案：（1）：j = 1。

1.2 解题技巧：仔细观察，对比代码说明和代码，找到得分点。

1.2.1 题目

......
for(p=1;p<n;p++){
    for(i=0; i<n-p;i++){
		......
        for(k=i; (1) ;k++){
            temp= (2) ;
            if(tempCost==-1 || tempCost>temp){
                tempCost = temp;    tempTrace=k;
            }
        }
        cost[i][j] = tempCost;
        (3) ; //此处缺少trace[][]记录
    }
}
......

代码说明
- cost[i][j]：二维数组，长度为 $n*n$ ，其中元素 cost[i][j] 表示 $A_{i+1}*A_{i+2}**A_{j+1}$ 的最优的计算代价。
- trace[][]：二维数组，长度为 $n*n$ ，其中元素 trace[i][j] 表示 $A_{i+1}*A_{i+2}**A_{j+1}$ 的最优计算顺序对应的划分位置，即 $k$ 。

注意：数组要么一来就有值，要么在代码中赋值。

答案：（3）：trace[i][j] = tempTrace;

1.3 解题技巧：有一些变量名具有特殊含义，比如一般用 `max/min` 保存最大值/最小值。`temp` 作为中间变量，一般用来存储中间值或用来作数值交换的中间过渡。

1.3.1 题目

......
if(max<c[i][j]){
    (1) ;//此处max比某值小，不符合最大，需要修改max值
    maxi = i;
    maxj = j;
}
......

答案：（1）：max = c[i][j]。

1.4 解题技巧：仔细对比伪代码和代码，找到得分点。

1.4.1 题目

【模式匹配基本概念】

定义：模式匹配是指给定主串 $t$ 和子串 $s$ ，在主串 $t$ 中寻找子串 $s$ 的过程，其中 $s$ 称为模式。
返回值：如果匹配成功，返回 $s$ 在 $t$ 中的位置；否则返回-1。

【KMP算法优化说明】

优化机制：KMP算法用 next 数组对匹配过程进行了优化。
伪代码执行步骤：
1. 在串 $t$ 和串 $s$ 中，分别设比较的起始下标 $i=j=0$ 。
2. 如果串 $t$ 和串 $s$ 都还有字符，则循环执行下列操作：
  - 条件 (1) ：如果 $j=-1$ 或者 $t[i]=s[j]$ ，则将 $i$ 和 $j$ 分别加1，继续比较 $t$ 和 $s$ 的下一个字符。
  - 条件 (2) ：否则，将 $j$ 向右滑动到 next[j] 的位置，即 $j=next[j]$ 。

......
int kmp( int *next, char *t,char *s, int lt, int ls )
{
    Int i=0,j =0;
    while (i < lt &&  (1) ){  //此处缺少循环条件
        if(j==-1||  (2) ){    //此处缺少if判断条件
            i++;    j++;
        }else
            (3); //此处缺少不满足if条件的处理过程
    }
    if (j >= ls) return  ( ) ;
    else  return -1;
}
......

答案：（1）：j < ls（2）：t[i] == s[j]（3）：j = next[j]。

1.5 解题技巧：仔细对比题干公式和代码，找到得分点。

1.5.1 题目

公式：

c[i][j] = \begin{cases} c[i-1][j-1]+1 & \text{若 } i > 0 \text{ 且 } j > 0 \text{ 且 } x[i-1] = y[j-1] \\ 0 & \text{其它} \end{cases}

......
for (i =1; i<= m; i++) {
    for (j=1; j<=n; j++) {
        if( (1) ){   //缺少递归式条件
            c[i][j]=c[i-1][j-1] + 1;
            if(max<c[i][j]){
                ( );
                maxi = i;   maxj =j;
            }
        }
        else  (2);  //缺少递归式结果
    }
}
......

答案：（1）：x[i-1] == y[j-1]（2）：c[i][j] = 0。

1.6 解题技巧：特殊算法有特定操作。对分治和动态规划有递归调用；动态规划的查数组操作；回溯法是否有回退 `k=k-1`。

1.6.1 题目

......
if (x[k]<n&&&k<n-1) {/*设置当前顶点的访问标志，继续下一个顶点*/
    ( )
    k=k+1;
} else {/*没有未被访问过的邻接顶点，回退到上一个顶点*/
    x[k]=0;
    visited [x[k]]=0;
    (1);    //此处缺少回退操作
}
......

答案：（1）：k = k - 1。

1.7 解题技巧：仔细看注释。有时候逻辑比较复杂的程序，注释会给出代码的功能说明。

1.7.1 题目

公式：

(1) 当 $i=1$ 时， $\text{size}(1, j) = \begin{cases} 0 & j < \pi(1) \\ 1 & \text{其他情况} \end{cases}$

(2) 当 $i>1$ 时， $\text{size}(i, j) = \begin{cases} \text{size}(i-1, j) & j < \pi(i) \\ \max\{\text{size}(i-1, j), \text{size}(i-1, \pi(i)-1) + 1\} & \text{其他情况} \end{cases}$

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<π[i]时*/
        for(j=pi[i]; j<=n; j++) {/*当j>=π[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;
        }
    }
......

重点：三目运算符。

答案：（1）：size[1],[j] = 1（2）：size[i],[j] = size[i-1], [j]。