>>>>>>>>>> 點擊進入2016年軟件設計師網絡課堂課
  >>>>>>>>>>點擊進入軟件設計師歷年真題題庫
  >>>>>>>>>>點擊進入2016年軟件設計師考試指南

2015年下半年軟件設計師考試真題下午卷

  試題四（共15分）
閱讀下列說明和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［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分）
      根據以上說明和C代碼，填充C代碼中的空(1)～(4).

【問題2】（4分）
      根據題干說明和以上C代碼，算法采用了（5）設計策略。 分析時間復雜度為（6）  （用0符號表示）。

【問題3】（3分）
      根據題干說明和以上C代碼，輸入字符串x= "ABCADAB’，'y="BDCABA",則輸出為 （7）。
      從下列的2道試題（試題五至試題六）中任選1道解答。 請在答題紙上的指定位置處將所選擇試題的題號框涂黑。若多涂或者未涂題號框，則對題號最小的一道試題進行評分。

   >>>>>>>>>>點擊獲取答案

  >>>>>>>>>>點擊返回目錄

  相關鏈接：

  軟件設計師考前ppt串講

  軟件設計師考試下午知識點精講與考前必練

  軟件設計師考試試題分類精解（第3版）