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  66
问题 阅读下列说明和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)；
   }
【问题2】
根据题干说明和以上C代码，算法采用了__________(5)设计策略。
分析时间复杂度为__________(6)(用O符号表示)。
选项
答案(5)动态规划 (6)O(m×n)或O(mn)
解析 根据【问题1】中的分析，已知算法采用动态规划技术，算法的时间复杂度分析过程为：
(1)函数lcs中，有两个一重循环和一个两重循环，时间复杂度为m+n+mn；
(2)函数printiLCS中，有一个一重循环，时间复杂度为m(或n)。
故算法的时间复杂度为O(mn)。
转载请注明原文地址:https://kaotiyun.com/show/KdDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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