首页 › 题库 › GESP编程能力等级认证 › 2.3 LIS与LCS

GESP-C++七级 题库

共 3 道题 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 2.3 LIS与LCS

已知三个序列: 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 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 2.3 LIS与LCS

已知两个序列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 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 2.3 LIS与LCS

下面代码段可以求两个字符串 s1 和 s2 的最长公共子串(LCS),下列相关描述不正确的是(   )。

A

代码的时间复杂度为O(n2)

B

代码的空间复杂度为O(n2)

C

空间复杂度已经最优

D

采用了动态规划求解

答案与解析
正确答案:C
这道题暂未补解析。
题目详情