当前位置：首页 > news >正文

软考：软件设计师 — 15.数据结构及算法应用

news 来源：原创 2024/9/20 6:08:36

十五. 数据结构及算法应用

数据结构及算法应用类题目是下午场考试中的第四道题目，分值 15 分，主要以 C 语言填空、算法策略判断和时间复杂度判断为考察形式，建议拿到 6 分以上。

1. 解题技巧

算法策略与时间复杂度部分详细内容可以参考文章：软考：软件设计师 — 14.算法基础

（1）算法策略区分

分治法（主要是二分）

特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。

经典问题：斐波那契数列、归并排序、快速排序、二分搜索、矩阵乘法、大整数乘法等

贪心法（一般用于求满意解）

特征：局部最优，但整体不见得最优。每步有明确的、既定的策略。

经典问题：背包问题（如装箱）、多机调度、找零钱问题

动态规划法（用于求最优解）

特征：划分子问题，并把子问题结果适用数组存储，利用查询子问题结果构造最终问题结果。（一般自顶向下时间复杂度为 O( $2^{n}$ )，自底向上时间复杂度为 O( $n^{a}$ )，后者效率更高）

经典问题：斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列

回溯法

特征：系统搜索一个问题的所有解或任一解。

经典问题：N皇后问题、迷宫、背包问题

算法名称	关键点	特征	典型问题
分治法	递归技术	把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。	归并排序、快速排序、二分搜索
贪心法	一般用于求满意解，特殊情况可求最优解（部分背包）	局部最优，但整体不一定最优。每步有明确的、既定的策略。	背包问题（如装箱）、多机调度、找零钱问题
动态规划法	最优子结构和递归式	划分子问题（最优子结构），并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。	矩阵乘法、背包问题、LCS最长公共子序列
回溯法	探索和回退	系统搜索一个问题的所有解或任一解。有试探和回退的过程。	N皇后问题、迷宫、背包问题

算法策略判断：

回溯：有尝试探索和回退的过程。
分治：分治和动态规划比较难区分。分治不好解决问题，从而记录中间解解决问题。分治主要采用二分的思想，二分以外都用动态规划法解决了。二分的时间复杂度与 O(nlog2n) 相关，需注意有无外层嵌套循环，如果有，则需要再乘 n。（结合归并排序、快速排序的过程，也是二分的）
动态规划法：有递归式，自底向上实现时，中间解基本上查表可得，时间复杂度一般是 O( $n^{a}$ )，具体 a 的值取决于 for 循环的嵌套层数。如果循环变量从 0 或 1 开始，到 n 结束，这种情况就是从小规模到大规模，自底向上。如果自顶向下，时间复杂度为 O( $2^{n}$ )，和分治的实现就差不多了，查表的意义可以忽略不记，循环变量一般由 n 开始，向 1 缩小，是从大规模到小规模。
贪心法：有时也会出现最优子结构的描述，但没有递归式。考虑的是当前最优，求得的是满意解。

（2）时间复杂度与空间复杂度

常见的对算法执行所需时间的度量：

O(1)<O( $log_{2}n$ )<O(n)<O( $nlog_{2}n$ )<O( $n^{2}$ )<O( $n^{3}$ )<O( $2^{n}$ )

（3）代码填空技巧

仔细审题：

检查所有用到的变量是否有声明，是否赋初值；
检查是否有返回值，与题干要求返回变量名或上下文是否一致；
检查 for 循环是否有计数变量的赋值、初值和终止条件；
注意 while 循环的开始和结束；
有一些变量名具有特殊含义，比如一般用 max/min 保存最大值/最小值，temp 作为中间变量，一般用来存储中间值或用来做数值交换的中间过渡。x>max，则修正 max=x；x<min，则修正 min=x；
对特殊的算法策略：回溯法是否有回退 k=k-1；分治法递归的递归调用（调用自身函数名）；动态规划法的查表操作；
注意题干描述和代码说明、递归式（条件和等式）、代码中的注释、代码上下文。一般特殊数据结构调用方式会在代码说明或代码上下文中给出。

题干公式很重要，一般公式体现在代码中，会有循环边界、判断条件等；
代码说明很重要，一般代码说明会指出一些变量的定义、初始值和边界值；
代码上下文很重要，可以根据上下文判断有没有缺失变量声明、变量赋值；
题干说明很重要，题干有时候会给出循环边界、判断条件等内容。还可以根据题干描述，判断使用的算法策略，不同的算法策略，一般会有一些典型的代码缺失，比如：动态规划法可能会考察题干给出的递归式以及最优解的判断；分治法一般会考察递归式以及问题的划分；贪心法一般会考察满意解的当前最优判断条件；回溯法一般会考察回退的过程。

2. 例题

（1）背包问题介绍

有 n 物品，第 i 个物品价值为 $v_{i}$ ，重量为 $w_{i}$ ，其中 $v_{i}$ 和 $w_{i}$ 均为非负数，背包的容量为 W，W 为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。

部分背包问题（物品可分割）

这类问题通常可以通过依次选择单位价值（ $v_{i}$ / $w_{i}$ ）最大的物品进行放入，剩余体积不够时，进行切割，从而得到最优结果。

0-1 背包问题（物品不可分割）

形式化描述如下：

目标函数为 $max\sum_{i=1}^{n}v_{i}x_{i}$

约束条件为 $\sum_{i=1}^{n}w_{i}x_{i}\leq W,x_{i}\in {0,1}$

满足约束条件的任一集合 $(x_{1},x_{2},\cdots ,x_{n})$ 是问题的一个可行解。

放置策略

可以将背包问题的求解过程看作是进行一系列决策的过程，即决定哪些物品应该放入背包，哪些物品不放入背包。

优先放体积最大，超过背包体积则放弃其它物品（5，4；30）；
优先放价值最大，超过背包体积则放弃其它物品（5，4；30）；
优先放单位价值最大，超过背包体积则放弃其它物品（5，3；29）；
按顺序放置，不合适就退出来重新放置，直到尝试完背包能够放置的所有方案；
刻画 0-1 背包问题的最优解的结构：

如果一个问题的最优解包含了物品 n，即 $x_{n}=1$ ，那么其余 $x_{1},x_{2},\cdots ,x_{n-1}$ 一定构成子问题 1，2，…，n-1 在容量 $W-w_{n}$ 的最优解。如果这个最优解不包含物品 n，即 $x_{n}=0$ ，那么其余 $x_{1},x_{2},\cdots ,x_{n-1}$ 一定构成子问题 1，2，…，n-1 在容量 W 的最优解。

如果题目中有对最优子结构的描述，用贪心法可以求得最优解（参考贪心法求解部分背包问题）。

（2）背包问题 - 贪心法

说明：

设有 n 个货物要装入若干个容量为 C 的集装箱以便运输，这 n 个货物的体积分别为 { $S_{1},S_{2},\cdots ,S_{n}$ }，且有 $S_{i}$ ≤ C（1≤i≤n）。为节省运输成本，用尽可能少的集装箱来装运这 n 个货物。

下面分别采用最先适宜策略和最优适宜策略来求解该问题。

最先适宜策略首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。

最优适宜策略与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。

C代码：

变量说明

n：货物数

C：集装箱容量

s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0 开始

b：数组，长度为 m，b[i] 表示第 i+1 个集装箱当前已经装入货物的体积，下标从 0 开始

i，j：循环变量

k：当前所用的集装箱数量

min：集装箱装入了第 i 个货物后的最小剩余容量

m：当前所需要的集装箱数量

temp：临时变量

具体代码

（1）最先适宜策略

/* 最先适宜策略首先将所有的集装箱初始化为空，对于所有货物，
按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中 */int firstfit(){int i,j;k=0;for(i=0; i<n; i++){b[i]=0;}for(i=0; i<n; i++){(1);while(C-b[i]<s[i]){j++;}(2);k=k>(j+1)?k:(j+1);}return k;
}

（2）最优适宜策略

/* 最优适宜策略与最先适宜策略类型，不同的是，
总是把货物装到能容纳它且目前剩余容量最小的集装箱中，使得该箱子装入货物后闲置空间最小。*/int bestfit(){int i,j,min,m,temp;k=0;for(i=0; i<n; i++){b[i]=0;}for(i=0; i<n; i++){min=C;m=k+1;for(j=0; j<k+1; j++){temp=C-b[i]-s[i];if(temp>0&&temp<min){(3);m=j;}}(4);k=k>(m+1)?k:(m+1);}return k;
}

问题1：

根据说明和 C 代码，填充 C 代码中的空（1）~（4）；

问题2：

根据说明和 C 代码，该问题在最先适宜和最优适宜策略下分别采用了（5）和（6）算法设计策略，时间复杂度分别为（7）和（8）。

问题3：

考虑实例 n=10，C=10，各个货物的体积为 {4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为（9）和（10）。考虑一般的情况，这两种求解策略能否确保得到最优解？（11）（能或否）

解析1：

在最先适宜策略代码中，第一个 for 循环中首先初始化了每个集装箱中装入货物的体积，第二个 for 循环中，有 while 循环去判断剩余集装箱的体积与每个货物的体积情况，货物体积大于集装箱剩余体积，则 j++，进入下一个集装箱。每个变量使用前都需要初始化，变量 j 没有初始化，因此第（1）空处填写初始化 j 变量的操作，即 j=0。如果货物体积不大于集装箱剩余体积，那么就说明可以放入集装箱中，因此第（2）处缺失的是装箱的操作，即 b[i] = b[i] + s[i]。

在最优适宜策略代码中，第一个 for 循环中首先初始化了每个集装箱中装入货物的体积，第二个 for 循环中，首先将集装箱容量初始化为最小，因为一开始集装箱中没装任何货物，也是最小剩余容量，m 代表当前所需要的集装箱数量或者集装箱的编号，因为初始编号从 0 开始，嵌套的 for 循环去遍历目前用到的集装箱，因为货物要放入能容纳它并且目前集装箱容量最小的那个，使用 temp 存储目前各集装箱的剩余容量，如果 temp 大于 0 （合法）并且比当前最小值要小的话，说明此时的最小值应该是 temp，找到当前剩余容量最小的集装箱，同时把遍历的第几个集装箱赋值给 m，那么此时的最小值是temp，即 min = temp；下一步缺少的也是装箱操作，注意此时不再是 b[j]，而是 b[m]，b[m] 才是目前剩余容量最小的集装箱，即 b[m] = b[m] + s[i]。

（1）j=0 （2）b[j] = b[j] + s[i]（3）min = temp （4）b[m] = b[m] + s[i]

解析2：

最先适宜策略是将货物装到第一个能容纳它的集装箱中，考虑的是局部最优，即贪心策略；最优适宜策略虽然有最优的概念，但是将货物装入能容纳它且目前剩余容量最小的箱子中，考虑的也是局部最优，即贪心策略。根据它们的 C 代码，最先适宜策略中涉及到两个平行的 for 循环以及一个嵌套进第二个 for 循环的 while 循环，有两层遍历，一层是遍历货物 n，一层是判断货物的体积与集装箱剩余的体积，因此时间复杂度为 O( $n^{2}$ )；最优适宜策略中涉及到了两层嵌套的 for 循环，一层是遍历货物，一层是遍历集装箱，因此时间复杂度为 O( $n^{2}$ )。

（5）贪心（6）贪心（7）O( $n^{2}$ ) （8）O( $n^{2}$ )

解析3：

具体实例的判断可通过画图或者推理得出，最先适宜策略是放入第一个能容纳当前货物的集装箱中，最优适宜策略是放入能容纳当前货物且目前剩余容量最小的集装箱中：

由图示可得，最先适宜策略需要 5 个集装箱，最优适宜策略需要 4 个集装箱；因此这两种策略不能确保得到最优解。

（3）背包问题 - 动态规划法

说明：

0-1 背包问题定义：给定 i 个物品的价值 v[1…i]、重量 w[1…i] 和背包容量 T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。

0-1 背包问题具有最优子结构性质。定义 c[i][T] 为最优装包方案所获得的最大价值，则可得到如下所示的递归式。

C代码：

常量和变量声明

T：背包容量

v[]：价值数组

w[]：重量数组

c[][]：c[i][j] 表示前 i 个物品在背包容量为 j 的情况下最优装包方案所能获得的最大价值

具体代码

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){(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：

根据说明和 C 代码，补充代码填空（1）~（4）。

问题2：

根据说明和 C 代码，算法采用了（5）设计策略。在求解过程中，采用了（6）（自底向上或自顶向下）的方式。

问题3：

若 5 项物品的价值数组和重量数组分别为 v[]={0,1,6,18,22,28} 和 w[]={0,1,2,5,6,7}，背包容量为 T=11，则获得的最大价值为（7）。

解析1：

第一部分为主函数，首先初始化 c[i][j] = -1，代表此时背包中没有物品，也没有价值。第二部分为计算最大价值的 Calculate_Max_Value 函数，首先给 temp 赋值 0，代表临时存储空间，然后如果 c[i][j] != -1，那么就代表此时背包中有物品，因此返回 c[i][j] 即可，即 return c[i][j]；接着下面给出了当 i=0 或 j==0 时，c[i][j] 也等于 0，即对应递归式中的第一种情况；否则 c[i][j] = Calculate_Max_Value（v,w,i-1,j），进行了递归调用，通过给出的参数可以发现，满足递归式的第二种情况；那么接着就是对递归式第三种情况的判断，如果 i>0且T≥w[i] 时，满足的表达式是什么，注意，Calculate_Max_Value 函数给出的参数为（ v，w，i，j），所以判断条件应该为 i>0&&j≥w[i]，此时满足表达式最大值为 Calculate_Max_Value（v,w,i-1,j-w[i]）+v[i]，也是一次递归调用，可参考第二种情况下，然后将计算结果赋给 temp；最后，如果 temp 比此时的 c[i][j] 要大，那么就更新最大值，即把 temp 赋给 c[i][j]，即 c[i][j] = temp。

（1）return 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：

通常题干中提到了最优子结构并且给出了递归式，那么就是动态规划法；在代码中，计算最大值时用到了参数 i-1，也就是递减的形式，那么算法采用的就是自顶向下的方式。

（5）动态规划法（6）自顶向下

解析3：

v-w	1-1	6-2	18-5	22-6	28-7	总价值
方案1	√	√			√	35
方案2			√	√		40
方案3	√	√	√			25
方案4	√	√		√		29

由于只有 5 种物品，直接穷举法列出全部结果，根据上表可发现最大价值为 40。

（4）N皇后问题 - 回溯法

说明：

在一个 n*n 的棋盘上摆放 n 个皇后，要求任意两个皇后不能冲突，即任意两个皇后不在同一行、同一列或同一斜线上。

算法的基本思想是：将第 i 个皇后摆放在第 i 行，i 从 1 开始，每个皇后都从第 1 列开始尝试。尝试判断在该列摆放皇后是否与前面的皇后有冲突，如果没有冲突，则在该列摆放皇后，并考虑摆放下一个皇后；如果有冲突，则考虑下一列。如果该行没有合适的位置，回溯到上一个皇后考虑在原来的位置的下一个位置上继续尝试摆放皇后，直到找到所有合理摆放方案。

C代码：

常量和变量说明

n：皇后数，棋盘规模为 n*n

queen[]：皇后的摆放位置数组，queen[i] 表示第 i 个皇后的位置，1≤queen[i]≤n

具体代码

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：

根据题干和 C 代码，补充代码填空（1）~（4）。

问题2：

根据题干和 C 代码，算法采用的设计策略为（5）。

问题3：

当 n=4 时，有（6）种摆放方式，分别为（7）。

解析1：

Place 函数中首先判断与已经放置的皇后是否在同一列或同一斜线上，其中 i 代表第 i 行，因此 queen[i] 代表第 i 列，如果元素在同一斜线上，那么行坐标之差与列坐标之差是相等的，因此 abs(queen[i]-queen[j] == (j-i))，abs() 函数的作用是返回数的绝对值，所以第（1）空缺失的是对皇后在同一列上的判断，即 queen[i] == queen[j]；在同一列或同一斜线上，则不能放置，返回 0，否则可以放置，返回 1，因此第（2）空是返回 1，即 return 1；在 Nqueen 函数中，首先遍历所有的皇后，j 代表皇后数，从 i=1 开始遍历。下方给出了两种情况，分别是 j==n，即遍历完所有的皇后，就展示方案，否则继续遍历下一个皇后，因此第（3）空判断条件中缺失的是该位置可以摆放皇后并且皇后数量小于等于 n，即 Place(j)&&j<=n；如果没有遍历完，继续遍历，即 Nqueen(j+1)，此处有一个递归调用。

（1）queen[i] == queen[j]（2）1 （3）Place(j)&&j<=n（4）Nqueen(j+1)

解析2：

N皇后问题，典型的回溯法设计策略。

解析3：

n=4 时，即在一个 4*4 的棋盘上放置 4 个皇后，且不冲突，可以画图得到结果：

即只有两种方案，分别是 2413 和 3142。

（5）假币问题 - 分治法

说明：

有 n 枚硬币，其中有一枚是假币，已知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。

将 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：当前考虑的硬币数组中第一个和最后一个下标

具体代码

int getCounterfeitCoin(int coins[], int first, int last){int firstSum = 0;int 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：

根据题干和 C 代码，补充代码填空（1）~（3）。

问题2：

根据题干和 C 代码，算法采用了（4）设计策略。函数 getCounterfeitCoin 的时间复杂度为（5）。

问题3：

若输入的硬币数为 30，则最少的比较次数为（6），最多的比较次数为（7）。

解析1：

偶数枚硬币的判断与奇数枚硬币的判断类似，只是划分的方式有略微不同。偶数枚硬币方法中，后半段重量相加时是从 i = first+(last-first)/2+1 枚硬币开始的，那么前半段就应该是从 1 到 first+(last-first)/2，因为偶数枚硬币可以直接划分为相等的两部分，因此第（1）空为 i<first+(last-first)/2+1；然后看返回值判断部分，可以参考奇数枚硬币的部分，当前半段小于后半段时，返回前半段，说明前半段有假硬币，重量轻，因此第（2）空为 firstSum<lastSum；奇数枚硬币时多了一种情况，就是两侧硬币重量相等，即中间的那枚硬币是假币，所以第（3）空，即第三种情况返回的是中间那枚硬币的下标号，即 return first+(last-first)/2。

（1）i<first+(last-first)/2+1（2）firstSum<lastSum（3）first+(last-first)/2

解析2：

利用了二分的思想，将硬币分为两部分，比较结果，然后继续划分成两部分比较，因此采用了分治法；时间复杂度为 O( $nlog_{2}n$ )，二分思想的时间复杂度为 $log_{2}n$ ，代码中还增加了一层 for 循环，因此多了一层 n，即 $nlog_{2}n$ 。

（4）分治法（5）O( $nlog_{2}n$ )

解析3：

硬币数为 30，偶数。最少的划分次数为，首先划分成两边各 15 枚硬币，进行一次比较，然后将较轻的一边继续划分，由于 15 是奇数，因此划分成 7 1 7 三部分，由于是最少的划分次数，所以直接得出中间的那枚硬币是假币，即两侧重量相等，即最少的划分次数为 2 次；最多的划分次数就是继续划分，7 划分成 3 1 3，然后 3 划分成 1 1 1，从而得到结果，因此最多划分 4 次。

（6）2 （7）4

数据结构及算法应用部分的内容至此结束，后续如果有补充或修改会直接添加。