答案及解析：[问答题]阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】计算两个字符串x和y的最长公共子串（Longest Common Substring）。假设字符串x和字符串y

问题：

[问答题] 阅读下列说明和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;}voidprintLCS(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）。

Tags：软件水平考试中级软件设计师试题及答案软件水平考试中级软件评测师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题