软件设计师案例分析每日一练试题（2023/11/25）

当前位置：信管网 >> 软件设计师 >> 每日一练 >> 文章内容

来源：信管网 2023年11月26日【所有评论】

软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2023/11/25）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2023/11/25

软件设计师案例分析每日一练试题内容（2023/11/25）

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
计算两个字符串x和y的最长公共子串（Longest Common Substring）。
假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。
c[i][j]满足最优子结构，其递归定义为：

计算所有c[i][j](0 ≤i ≤ m，0 ≤j ≤ n)的值，值最大的c[i][j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j，确定一个最长公共子串。
【C代码】
(1)常量和变量说明
x，y：长度分别为m和n的字符串
c[i][j]：记录x中前i个字符和y中前j个字符的最长公共子串的长度
max：x和y的最长公共子串的长度
maxi, maXj：分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置（序号）
(2)C程序

#include
#include

int c[50][50];
int maxi;
int maxj;

int lcs(char *x, int m, char *y, int n) {
int i, j;
int max= 0;
maxi= 0;
maxj = 0;

for ( i=0; i<=m ; i++) c[i][0] = 0;
for (i =1; i<= n; i++) c[0][i]=0;
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 (2) ;
maxi = i;
maxj =j;
}
}
else (3) ;
}
}
return max;
}
void printLCS(int max, char *x) {
int i= 0;
if (max == 0) return;
for ( (4) ; i < maxi; i++)
printf("%c",x[i]);
}
void main(){
char* x= "ABCADAB";
char*y= "BDCABA";
int max= 0;
int m = strlen(x);
int n = strlen(y);

max=lcs(x,m,y,n);
printLCS(max , x);
}
【问题1】（8分）
根据以上说明和C代码，填充C代码中的空（1）～（4）。
【问题2】（4分）
根据题干说明和以上C代码，算法采用了（5）设计策略。
分析时间复杂度为（6）（用O符号表示）。
【问题3】（3分）
根据题干说明和以上C代码，输入字符串x= "ABCADAB’，'y="BDCABA",则输出为（7）。
信管网试题答案与解析：www.cnitpm.com/st/381603746.html
信管网考友试题答案分享：

信管网cnitpm537653968867：
问题一 1、x[i-] == y[j-1] 2、max == m 3、 4、i == 0 问题二回溯 n^2

信管网yebinghuai：
＜br /＞＜img src=＂http://pic.cnitpm.com/upload/tbimg/2021-09/1630812700.jpg＂ /＞

信管网试题答案与解析：www.cnitpm.com/st/381603746.html