题目

yangzhuoqun2014 · 2024-08-16 09:24:48 · 个人记录

阅读程序

01 #include <bits/stdc++.h>
02 using namespace std;
03 string a,b;
04 int dp[1001][1001],n,m;
05 void lcs(){
06     for(int i=1;i<=n;i++){
07       for(int j=1;j<=m;j++){
08           if(a[i-1]==b[j-1]){
09              dp[i][j] = dp[i-1][j-1]+1;
10           }else if(dp[i-1][j]>dp[i][j-1]){
11               dp[i][j]=dp[i-1][j];
12           }else{
13               dp[i][j]=dp[i][j-1];
14           }
15       }
16   }
17 }
18
19 int main(){
20     cin>>a>>b;
21     n=a.length();
22     m=b.length();
23     lcs();
24     cout<<dp[n][m];
25     return 0;
26 }

判断题

(1) 将第10行的else去除，运行结果不变 （ ）

(2) 这个程序求的是最长公共递增子序列 （ ）

(3) 将第4行代码移动到19~20行之间，运行结果发生变化（ ）

(4) 将第10行的>改成>=程序运行结果没有变化 （ ）

选择题

(1) 程序的时间复杂度为 （ ） A.O(n) B.O(m) C.O(n\times m) D.O(max(n,m))

(2) 输入ABDEGF\nABEGH,输出为（ ） A.1 B.3 C.5 D.4

答案