軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：www.tent-cn.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：www.tent-cn.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2025/8/7）在線測(cè)試：www.tent-cn.com/exam/ExamDayAL.aspx?t1=4&day=2025/8/7

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2025/8/7）

試題四（共15分）
   閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
   計(jì)算兩個(gè)字符串x和y的最長(zhǎng)公共子串（Longest Common Substring）。
   假設(shè)字符串x和字符串y的長(zhǎng)度分別為m和n，用數(shù)組c的元素c[i][j]記錄x中前i
個(gè)字符和y中前j個(gè)字符的最長(zhǎng)公共子串的長(zhǎng)度。
   c[i][j]滿足最優(yōu)子結(jié)構(gòu)，其遞歸定義為：
 


   計(jì)算所有c[i][j](0 ≤i ≤ m，0 ≤j ≤ n)的值，值最大的c[i][j]即為字符串x和y的最長(zhǎng)公共子串的長(zhǎng)度。根據(jù)該長(zhǎng)度即i和j,+確定一個(gè)最長(zhǎng)公共子串。
【C代碼】
(1)常量和變量說明
   x，y：長(zhǎng)度分別為m和n的字符串
   c[i][j]：記錄x中前i個(gè)字符和y中前j個(gè)字符的最長(zhǎng)公共子串的長(zhǎng)度
   max：x和y的最長(zhǎng)公共子串的長(zhǎng)度
   maxi, maXj：分別表示x和y的某個(gè)最長(zhǎng)公共子串的最后一個(gè)字符在x和y中的位置（序號(hào)）
 (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［i］［0］=0;
for (i =1; i<= m; i++)    {
     for (j=1; j<= n; j++)    {
        If (    (1)    )    {
c[il[j] = c[i - l][j - i] + 1;
if(max<c[il[j] {
        (2)   :
    maxi = i;
    maxj =j;
 }
}
else     (3)    ;
       }
   }
    retum  max;
}    
void printLCS(int max, char *x) {
         int i= 0;
      if (max = 0)        retum;
     For （  (4)    ； i < maxi; i++)
}
void main（）{
 Char* x= "ABCADAB";
 Char*y= "BDCABA";
  int max= o;
 int m = strlen(x);
 int n = strlen(y);
 Max=lcs(x,m,y,n)
 printLCS（max，x）
}
【問題1】（8分）    
 根據(jù)以上說明和C代碼，填充C代碼中的空(1)～(4).
【問題2】（4分）    
根據(jù)題干說明和以上C代碼，算法采用了（5）設(shè)計(jì)策略。
分析時(shí)間復(fù)雜度為（6）  （用0符號(hào)表示）。
【問題3】（3分）
 根據(jù)題干說明和以上C代碼，輸入字符串x= "ABCADAB’，'y="BDCABA",則輸出為   （7）。
 

信管網(wǎng)1232***********：
＜br /＞＜img src=＂http://pic.cnitpm.com/upload/2022/09/tbimg/09-11/1662907531.jpg＂ /＞