阅读程序(第三题):最长公共子序列长度

wm283821 组合题 共 个子题

阅读下面程序,完成后面的判断题和单选题。判断题正确填 A,错误填 B。

#include <cstdio>
#include <cstring>
#include <algorithm>

char a[1005], b[1005];
int dp[1005][1005];

int main() {
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    int n = strlen(a + 1);
    int m = strlen(b + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i] == b[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}

子题 判断题

判断题:该程序求的是两个字符串的最长公共子序列的长度(子序列不要求连续)。( )

A

正确

B

错误

子题 判断题

判断题:当第一行输入为 "abcfbc"、第二行输入为 "abfcab" 时,输出为 4。( )

A

正确

B

错误

子题 判断题

判断题:将第 16 行的 `dp[i][j] = dp[i - 1][j - 1] + 1;` 改为 `dp[i][j] = dp[i - 1][j - 1];` 后,对任何合法输入,程序的输出都为 0。( )

A

正确

B

错误

子题 判断题

判断题:该程序的空间复杂度为 O(n + m)(其中 n、m 分别为两个字符串的长度)。( )

A

正确

B

错误

子题 单选题

当第一行输入为 "abcde"、第二行输入为 "ace" 时,输出为( )。

A

1

B

2

C

3

D

5

子题 单选题

将第 18 行的表达式整体改为 `dp[i][j] = dp[i - 1][j];`(即只继承上一行的值),当第一行输入为 "abcfbc"、第二行输入为 "abfcab" 时,输出为( )。

A

0

B

1

C

2

D

4

子题 单选题

该程序的时间复杂度(关于 n、m)为( )。

A

O(n + m)

B

O(n × m)

C

O(n²)

D

O(n² × m)

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧