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

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

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

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2021/9/5）

阅读下列说明和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 <stdio.h>
#include <string.h>

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<c[i][j]) {
                 (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

信管网考友试题答案分享：

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