>>>>>>>>>> 點(diǎn)擊進(jìn)入2016年軟件設(shè)計(jì)師網(wǎng)絡(luò)課堂課
  >>>>>>>>>>點(diǎn)擊進(jìn)入軟件設(shè)計(jì)師歷年真題題庫(kù)
  >>>>>>>>>>點(diǎn)擊進(jìn)入2016年軟件設(shè)計(jì)師考試指南

2015年下半年軟件設(shè)計(jì)師考試真題下午卷

  試題四（共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）。
      從下列的2道試題（試題五至試題六）中任選1道解答。 請(qǐng)?jiān)诖痤}紙上的指定位置處將所選擇試題的題號(hào)框涂黑。若多涂或者未涂題號(hào)框，則對(duì)題號(hào)最小的一道試題進(jìn)行評(píng)分。

   >>>>>>>>>>點(diǎn)擊獲取答案

  >>>>>>>>>>點(diǎn)擊返回目錄

  相關(guān)鏈接：

  軟件設(shè)計(jì)師考前ppt串講

  軟件設(shè)計(jì)師考試下午知識(shí)點(diǎn)精講與考前必練

  軟件設(shè)計(jì)師考試試題分類精解（第3版）