2. 计算机
  3. 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 计算两个字符串x和y的最长公共子串(Longest Common Substring)。 假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 计算两个字符串x和y的最长公共子串(Longest Common Substring)。 假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j

admin2016-11-11  89
问题 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
    计算两个字符串x和y的最长公共子串(Longest Common Substring)。
    假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。
    c[j]满足最优子结构，其递归定义为：

    计算所有c[j](O≤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
    #include
    int c[50][50]；
    int maxi；
    int maxj；
    int 1cs(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；
    }
    void printLCS(int max，char *x){
        int i=0；
        if(max==0)    return；
        for(___________(4)；i＜maxi；i++)
           printf("％c"，x)；
    }
    void main(){
    char*x="ABCADAB"；
  cnar*y="BDCABA"；
    int max=0；
    int m=strlen(x)；
    int n=strlen(y)；
    max=lcs(x，m，y，n)；
    printLCS(max，x)；
   }
【问题1】
根据以上说明和C代码，填充C代码中的空(1)～(4)。
选项
答案(1)x[i－1]==y[j－1] (2)max=c[i][j] (3)c[i][j]=0 (4)i=maxi－max
解析 本题考查算法设计与分析和C语言实现算法的相关技术。
此类题目要求考生认真阅读题目，首先理解问题以及求解问题的算法思路。
根据题干说明，给出的问题具有最优子结构，考生应该能想到该题用动态规划或者贪心求解。一般在给出递归定义最优解时，已经比较清楚地给出要用动态规划方法，并且根据给出的C程序，可知以自底向上的方式进行计算，即先求小规模问题的，再求规模更大的问题的解。进入到C程序内部，函数lcs是计算c数组，并确定其最大的元素。在两重循环内，应该是递归公式的迭代求解过程，因此空(1)处填入“x[i－1]=y[j－1]”；若当前的最大长度小于c[j]，则应该更新当前最大长度，即空(2)处填入“max=c[j]”；空(3)前面是else与if对应，即是x[i－1]≠y[j－1]的情况，根据递归式此处填入“c[j]=0”；函数printLCS是根据函数lcs计算的结果输出最长公共子串，长度为max，在串x中的最后位置是maxi，而在串y中的最后位置是maxj，因此，空(4)填入“i=maxi—max”。
转载请注明原文地址:https://kaotiyun.com/show/7dDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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