PDF文檔公眾號回復關鍵字:20240601

1 2023 CSP-J 閱讀程序2

閱讀程序（程序輸入不超過數組成字符串定義的范圍：判斷題正確填√，錯誤填×；除特殊說明外，判斷題1.5分，選擇題3分，共計40分）

源程序

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int f(string x,string y){int m=x.size();int n=y.size();vector<vector<int>>v(m+1,vector<int>(n+1,0));for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(x[i-1]==y[j-1]){v[i][j]=v[i-1][j-1]+1;}else{v[i][j]=max(v[i-1][j],v[i][j-1]);}}}return v[m][n];
}bool g(string x,string y){if(x.size() != y.size()){return false;}return f(x+x,y)==y.size();
}int main(){string x,y;cin>>x>>y;cout<<g(x,y)<<endl;return 0;
}

判斷題

21（1.5分）f函數的返回值小于等于min（n,m）（ ）

22 （1.5分） f函數的返回值等于兩個輸入字符串的最長公共子串的長度（ ）

23 （1.5分）當輸入兩個完全相同的字符串時，g函數的返回值總是true（ ）

單選題

24 （3分）將第19行中的“v[m] [n]”替換為“v[n] [m]”，那么該程序（ ）

A 行為不變 B 只會改變輸出 C 一定非正常退出 D 可能非正常退出

25 （3分）當輸入為“csp-j p-jcs”時，輸出為：（ ）

A “0” B “1” C “T” D “F”

26 當輸入為“csppsc spsccp”時，輸出為()

A “T” B “F” C “0” D “1”

2 相關知識點

1) 子序列

一個給定的序列的子序列，就是將給定序列中零個或多個元素去掉之后得到的結果

例如

2) 子串

給定串中任意個連續的字符組成的子序列稱為該串的子串

3)最長公共子序列

一個序列即是X序列的子序列，也是Y序列的子序列，則該序列稱為為X和Y的公共子序列。對于兩個序列的公共子序列是不唯一的，因此，最長公共子序列顧名思義就是長度最長的公共子序列

4) 動態規劃最長公共子序列長度

最長公共子序列(Longest Common Subsequence, LCS) 問題可以使用動態規劃求解。

假設x[1…m]和y[1…n]是兩個序列，令c[i,j]表示x[1…i]和y[1…j]的LCS長度

狀態轉移方程

當i=0或j=0時，c[i,j]=0；
當x[i]=y[j]時，c[i,j]=c[i-1,j-1]+1；
當x[i]!=y[j]時，c[i,j]=max(c[i,j-1],c[i-1,j])。

例如

有2個字符串，字符串1：0123456和字符串2：0346

5) 字符串連接

在C++中，可以使用加號+運算符或append()方法來連接字符串

#include<bits/stdc++.h>
using namespace std;
/*字符串連接string a="我愛你,",String b="中國!";string c=a+b;//a和b拼接在一起賦值給c,所以c是我愛你,中國!a.append(b);//把b拼接到a上,所以a是我愛你,中國!
*/
int main(){string a="我愛你,";string b="中國!";string c=a+b;cout<<c<<endl; //輸出我愛你,中國!a.append(b);cout<<a<<endl;//輸出我愛你,中國!string p="";string q="";string pp=p+p;//空字符粗拼接后還是空字符串cout<<pp.size();//空字符串的長度為0，所以輸出0return 0;
}
/*
輸出 
我愛你,中國!
我愛你,中國!
0
*/ 

6) 數組

數組越界

一般數組越界結果不可預測

#include<bits/stdc++.h>
using namespace std;
/*在C++中，訪問數組時出現越界（即訪問了不屬于該數組的內存區域）不會自動導致程序崩潰。這是因為C++標準并未規定訪問數組越界時應當如何反應未定義行為意味著程序的后續行為是不可預測的，可能會導致各種不確定的結果，包括程序崩潰、異常拋出、運行錯誤結果，  或者看似正常的行為
*/
int a[10][20]; C++
int main(){cout<<a[300][160];//可以輸出 未退出 cout<<" test";//可以輸出  return 0;
}

vector 數組

#include<bits/stdc++.h>
using namespace std;vector<int> a(11,1);//聲明數組a并賦值1 
vector<int> b(11);//聲明數組a,默認賦值0 
int main(){a.push_back(2);//在a最后一個元素后面追加2 a.push_back(4);//在a最后一個元素后面追加4 for(int i=0;i<a.size();i++){//輸出a數組中每個元素 cout <<a[i]<< ' ';}cout<<endl;for(int i=0;i<b.size();i++){//輸出b數組中每個元素cout <<b[i]<< ' ';C++}return 0;
}
/*
輸出
1 1 1 1 1 1 1 1 1 1 1 2 4
0 0 0 0 0 0 0 0 0 0 0 
*/

vector數組越界

#include<bits/stdc++.h>
using namespace std;
int m=10,n=20;
//聲明二維vector數組 默認值初始化為0 
vector<vector<int> > v(m+1,vector<int>(n+1,1));
int main(){cout<<v[n][m];//訪問越界位置  程序非正常退出 cout<<"test";//上一行已非正常退出，無法輸出test return 0;
}
/*
無任何輸出內容 
*/

3 思路分析

判斷題

21（1.5分）f函數的返回值小于等于min（n,m）（ ）

答案 T

分析

f函數的功能是求2個入參字符串的最長公共子序列的長度，是CSP-J必須掌握的動態規劃的算法

最長公共子序列,最大值是2個字符串長度的最小值，所以答案是正確的

22 （1.5分） f函數的返回值等于兩個輸入字符串的最長公共子串的長度（ ）

答案 F

分析

f函數的功能是求2個入參字符串的最長公共子序列的長度，不是最長公共子串的長度

f函數的功能是返回最長公共子序列的長度，不是最長公共子串的長度，子序列是不連續的，字串是連續的

例如

// CSP-J-ABCD  ,   CSNJBENCH
// 上面字符串的最長公共子序列是 CJBC 長度是4
// 上面字符串的最長公共子串是 CS 長度是2

23 （1.5分）當輸入兩個完全相同的字符串時，g函數的返回值總是true（ ）

答案 T

分析

當輸入2個完全相同的字符串時，最長公共子序列的長度時字符串的長度

所以g函數返回true

例如

//CSP-J和CSP-J，傳入f函數時對第1個參數連接增加了1倍長度，變成CSP-JCSP-J
//所以參數為CSP-JCSP-J和CSP-J，這2個字符串的最長公共子序列是CSP-J，長度是5

單選題

24 （3分）將第19行中的“v[m] [n]”替換為“v[n] [m]”，那么該程序（ ）

A 行為不變 B 只會改變輸出 C 一定非正常退出 D 可能非正常退出

答案 D

分析

m是n的2倍，改變行列vector會越界，程序會非正常退出

如果輸入x和y都是空字符串時，m和n都是0，vector不會越界

例如

/*
CSP-J和CSP-J，傳入f函數時對第1個參數連接增加了1倍長度，變成CSP-JCSP-J
所以參數為CSP-JCSP-J和CSP-J
m是10,n是5 ，所以數組是5行10列
填每行列對應數字時是按5行8列填的，取時如果交換，可能去8行去取，會出現vector越界，
vector越界會非正常退出
*/

25 （3分）當輸入為“csp-j p-jcs”時，輸出為：（ ）

A “0” B “1” C “T” D “F”

答案 B

分析

輸入csp-j p-jcs時，會第1給參數csp-j自連接后變成csp-jcsp-j

可以看出p-jcs在csp-jcsp-j中

返回的最長公共子序列的長度是p-jcs的長度和第2個參數長度相等，所以輸出為true或者1

所以選B

26 當輸入為“csppsc spsccp”時，輸出為()

A “T” B “F” C “0” D “1”

答案 D

分析

輸入csppsc spsccp時，會把第1給參數csppsc自連接后變成csppsccsppsc

可以看出spsccp按順序出現在csppsccsppsc 中

返回的最長公共子序列的長度是spsccp的長度和第2個參數長度相等，所以輸出為true或者1