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

问答题【问题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[i][j]，则应该更新当前最大长度，即空(2)处填入“max=c[i][j]”；空(3)前面是else与if对应，即是x[i－1]≠y[j－1]的情况，根据递归式此处填入“c[i][j]=0”；函数printLCS是根据函数lcs计算的结果输出最长公共子串，长度为max，在串x中的最后位置是maxi，而在串y中的最后位置是maxj，因此，空(4)填入“i=maxi—max”。

问答题【问题2】根据题干说明和以上C代码，算法采用了__________(5)设计策略。分析时间复杂度为__________(6)(用O符号表示)。

【正确答案】正确答案：(5)动态规划 (6)O(m×n)或O(mn)

【答案解析】解析：根据【问题1】中的分析，已知算法采用动态规划技术，算法的时间复杂度分析过程为： (1)函数lcs中，有两个一重循环和一个两重循环，时间复杂度为m+n+mn； (2)函数printiLCS中，有一个一重循环，时间复杂度为m(或n)。故算法的时间复杂度为O(mn)。

问答题【问题3】根据题干说明和以上C代码，输入字符串x="ABCADAB"，y="BDCABA"，则输出为__________(7)。

【正确答案】正确答案：(7)AB

【答案解析】解析：根据题干和C代码，计算出下表的值。