GESP-C++七级 题库
共 3 道题
· 按题型筛选,点「查看答案」核对解析
1
单选题
适中
已知三个序列: s1 = {3, 1, 8, 2, 5, 6, 7, 4} , s2 = {1, 5, 1, 8, 6, 4, 7, 5, 6}, s3 = {1, 8, 3, 5, 7, 6, 2, 4} 。以下哪个序列是它们的最长公共子序列( )。
A
{1, 8, 5, 6}
B
{1, 5, 6, 7}
C
{1, 8, 6}
D
{1, 5, 7, 4}
答案与解析
正确答案:A
确定三个序列的最长公共子序列需逐元素比对,找出在所有序列中按相同顺序出现的最长元素序列。使用动态规划方法,构建多维状态表记录各序列前缀间的公共子序列长度。通过递推更新状态值,依据匹配情况转移状态,最终回溯路径获取最长公共子序列。过程中需保持元素相对顺序不变,且每个元素必须在所有序列中存在并满足顺序约束。
2
单选题
适中
已知两个序列s1= {1,3,4,5,6,7,7,8,1} 、s2= {3,5,7,4,8,2,9,5,1} ,则它们的最长公共子序列是()。
A
{3,5,7,8,1}
B
{3,4,5,7,8}
C
{5,7,8}
D
{3,5,7,9,1}
答案与解析
正确答案:A
最长公共子序列指最长的序列满足即是s1的子序列又是s2的子序列,选项A满足要求且是最长的
3
单选题
适中
下面代码段可以求两个字符串 s1 和 s2 的最长公共子串(LCS),下列相关描述不正确的是( )。

A
代码的时间复杂度为O(n2)
B
代码的空间复杂度为O(n2)
C
空间复杂度已经最优
D
采用了动态规划求解
答案与解析
正确答案:C
这道题暂未补解析。