2. 从业资格
  3. 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明

admin2022-08-02  42
问题 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】   计算两个字符串x和y的最长公共子串（Longest Common Substring）。   假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。c[j]满足最优子结构，其递归定义为：计算所有c[j](0 ≤i ≤ m，0 ≤j ≤ n)的值，值最大的c[j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j，确定一个最长公共子串。【C代码】(1)常量和变量说明   x，y：长度分别为m和n的字符串   c[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[0] = 0;for (i =1;i ＜ = n; i++)            c[0]=0;for (i =1;i ＜ = m; i++)    {     for (j=1; j ＜ = n; j++)    {        if (   (1)    )    {c[j] = c[i-1][j -1] + 1;if(max ＜ c[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);}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） 。
选项
答案
解析 【问题1】（8分）答案：（1）x[i-1]= =y[j-1]  （2）max=c[j]（3）c[j]=0          （4）i=maxi-max【问题2】（4分）答案：动态规划、 O(m×n)或O(mn)【问题3】（3分）答案：AB根据题干和C代码，计算出下表的值。最大值为2。在计算过程中，我们记录第一个最大值，即表中阴影部分元素，因此得到最长公共子串为AB。
转载请注明原文地址:https://tihaiku.com/congyezige/2407929.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)