>>>>>>>>>> 点击进入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版）