Dotcpp  >  试卷列表  >  CSP-J1入门级初赛试卷[2023]

CSP-J1入门级初赛试卷[2023]

自由练习

模拟考试

我的成绩

第1题

在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（ ）。

共 2 分　

第2题

八进制数123456708 和076543218的和为（ ）。

共 2 分　

第3题

阅读下述代码，请问修改data的value成员以存储3.14，正确的方式是（ ）。

1
2
3
4
5
6
union Data{
int num;
float value;
char symbol;
};
union Data data;
共 2 分　

第4题

假设有一个链表的节点定义如下：

1
2
3
4
struct Node {
int data;
Node* next;
};

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）

共 2 分　

第5题

根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（ ）。

共 2 分　

第6题

小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有（ ）种选择时间段的方案。

共 2 分　

第7题

以下关于高精度运算的说法错误的是（ ）。

共 2 分　

第8题

后缀表达式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”对应的中缀表达式是（ ）

共 2 分　

第9题

数1010102和1668的和为（ ）。

共 2 分　

第10题

假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）

共 2 分　

第11题

给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）

共 1 分　

第12题

考虑一个有向无环图，该图包括4条有向边：(1,2)，(1,3)，(2,4)，和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）

有向无环图

共 2 分　

第13题

在计算机中，以下哪个选项描述的数据存储容量最小？（ ）

共 2 分　

第14题

一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）

共 2 分　

第15题

以下哪个不是操作系统？（ ）

共 2 分　

第16题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cmath>
using namespace std;
double f(double a,double b,double c){
 double s=(a+b+c)/2;
 return sqrt(s*(s-a)*(s-b)*(s-c));
}
int main(){
 cout.flags(ios::fixed);
 cout.precision(4);
  
int a,b,c;
 cin>>a>>b>>c;
 cout<<f(a,b,c)<<endl;
 return 0;
}

假设输入的所有数都为不超过1000的正整数，完成下面的判断题和单选题：

当输入为“2 2 2”时，输出为“1.7321”（ ）

共 2 分　

第17题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cmath>
using namespace std;
double f(double a,double b,double c){
 double s=(a+b+c)/2;
 return sqrt(s*(s-a)*(s-b)*(s-c));
}
int main(){
 cout.flags(ios::fixed);
 cout.precision(4);
  
int a,b,c;
 cin>>a>>b>>c;
 cout<<f(a,b,c)<<endl;
 return 0;
}

假设输入的所有数都为不超过1000的正整数，完成下面的判断题和单选题：

将第7行中的"（s-b）*（s-c）"改为"（s-c）*（s-b）"不会影响程序运行的结果（）

共 2 分　

第18题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cmath>
using namespace std;
double f(double a,double b,double c){
 double s=(a+b+c)/2;
 return sqrt(s*(s-a)*(s-b)*(s-c));
}
int main(){
 cout.flags(ios::fixed);
 cout.precision(4);
  
int a,b,c;
 cin>>a>>b>>c;
 cout<<f(a,b,c)<<endl;
 return 0;
}

假设输入的所有数都为不超过1000的正整数，完成下面的判断题和单选题：

程序总是输出四位小数（ ）

共 2 分　

第19题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cmath>
using namespace std;
double f(double a,double b,double c){
 double s=(a+b+c)/2;
 return sqrt(s*(s-a)*(s-b)*(s-c));
}
int main(){
 cout.flags(ios::fixed);
 cout.precision(4);
  
int a,b,c;
 cin>>a>>b>>c;
 cout<<f(a,b,c)<<endl;
 return 0;
}

假设输入的所有数都为不超过1000的正整数，完成下面的判断题和单选题：

当输入为“3 4 5”时，输出为（ ）

共 2 分　

第20题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cmath>
using namespace std;
double f(double a,double b,double c){
 double s=(a+b+c)/2;
 return sqrt(s*(s-a)*(s-b)*(s-c));
}
int main(){
 cout.flags(ios::fixed);
 cout.precision(4);
  
int a,b,c;
 cin>>a>>b>>c;
 cout<<f(a,b,c)<<endl;
 return 0;
}

假设输入的所有数都为不超过1000的正整数，完成下面的判断题和单选题：

当输入为“5 12 13”时，输出为（ ）

共 2 分　

第21题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}

f函数的返回值小于等于min（n,m）。（ ）

共 2 分　

第22题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}

f函数的返回值等于两个输入字符串的最长公共子串的长度。（）

共 2 分　

第23题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}

当输入两个完全相同的字符串时，g函数的返回值总是true。（）

共 2 分　

第24题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}

将第19行中的“v[m][n]”替换为“v[n][m]”，那么该程序（ ）

共 2 分　

第25题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}

当输入为 "csp-j p-jcs" 时,输出为( )

共 2 分　

第26题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}

当输入为“csppsc spsccp”时，输出为：（ ）

共 2 分　

第27题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cmath>
using namespace std;
int solve1(int n){
return n*n;
}
int solve2(int n){
 int sum=0;
 for(int i=1;i<=sqrt(n);i++){
 if(n%i==0){
 if(n/i==i){
 sum+=i*i;
 }else{
 sum+=i*i+(n/i)*(n/i);
 }
 }
}
 return sum;
}
int main(){
 int n;
 cin>>n;
 cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
 return 0;
}

假设输入的n是绝对值不超过1000的整数，完成下面的判断题和单选题:

如果输入的n为正整数，solve2函数的作用是计算n所有的因子的平方和（ ）

共 3 分　

第28题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cmath>
using namespace std;
int solve1(int n){
return n*n;
}
int solve2(int n){
 int sum=0;
 for(int i=1;i<=sqrt(n);i++){
 if(n%i==0){
 if(n/i==i){
 sum+=i*i;
 }else{
 sum+=i*i+(n/i)*(n/i);
 }
 }
}
 return sum;
}
int main(){
 int n;
 cin>>n;
 cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
 return 0;
}

假设输入的n是绝对值不超过1000的整数，完成下面的判断题和单选题:

第13~14行的作用是避免n的平方根因子i（或n/i）进入第16行而被计算两次（）

共 3 分　

第29题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cmath>
using namespace std;
int solve1(int n){
return n*n;
}
int solve2(int n){
int sum=0;
for(int i=1;i<=sqrt(n);i++){
if(n%i==0){
if(n/i==i){
sum+=i*i;
}else{
sum+=i*i+(n/i)*(n/i);
}
}
}
return sum;
}
int main(){
int n;
cin>>n;
cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
return 0;
}

假设输入的n是绝对值不超过1000的整数，完成下面的判断题和单选题:

如果输入的n为质数，solve2（n）的返回值为n²+1（）

共 3 分　

第30题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cmath>
using namespace std;
int solve1(int n){
return n*n;
}
int solve2(int n){
int sum=0;
for(int i=1;i<=sqrt(n);i++){
if(n%i==0){
if(n/i==i){
sum+=i*i;
}else{
sum+=i*i+(n/i)*(n/i);
}
}
}
return sum;
}
int main(){
int n;
cin>>n;
cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
return 0;
}

假设输入的n是绝对值不超过1000的整数，完成下面的判断题和单选题:

如果输入的n为质数p的平方，那么solve2（n）的返回值为（ ）

共 3 分　

第31题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cmath>
using namespace std;
int solve1(int n){
return n*n;
}
int solve2(int n){
int sum=0;
for(int i=1;i<=sqrt(n);i++){
if(n%i==0){
if(n/i==i){
sum+=i*i;
}else{
sum+=i*i+(n/i)*(n/i);
}
}
}
return sum;
}
int main(){
int n;
cin>>n;
cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
return 0;
}

假设输入的n是绝对值不超过1000的整数，完成下面的判断题和单选题:

当输入为正整数时，第一项减去第二项的差值一定（ ）

共 3 分　

第32题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cmath>
using namespace std;
int solve1(int n){
return n*n;
}
int solve2(int n){
int sum=0;
for(int i=1;i<=sqrt(n);i++){
if(n%i==0){
if(n/i==i){
sum+=i*i;
}else{
sum+=i*i+(n/i)*(n/i);
}
}
}
return sum;
}
int main(){
int n;
cin>>n;
cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
return 0;
}

假设输入的n是绝对值不超过1000的整数，完成下面的判断题和单选题:

当输入为“5”时，输出为（ ）

共 3 分　

第33题

（寻找被移除的元素）问题，原有长度为n+1,公差为1的等差升序数列，将序列输入到程序的数组时移除了一个元素，导致长度为n的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums){
 int left=0,right=nums.size()-1;
 while(left<right){
 int mid=left+(right-left)/2;
 if(nums[mid]==mid+①){
 ②;
 }else{
 ③;
  }
 }
 return ④;
}
int main(){
 int n;
 cin>>n;
 vector<int> nums(n);
 for(int i=0;i<n;i++) cin>>nums[i];
 int misssing_number=find_missing(nums);
 if(missing_number==⑤){
 cout<<"Sequence is consecutive"<<endl;
 }else{
 cout<<"Missing numbers is"<<missing_number<<endl;
 }
return 0;
}

①处应填（ ）

共 3 分　

第34题

（寻找被移除的元素）问题，原有长度为n+1,公差为1的等差升序数列，将序列输入到程序的数组时移除了一个元素，导致长度为n的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums){
 int left=0,right=nums.size()-1;
 while(left<right){
 int mid=left+(right-left)/2;
 if(nums[mid]==mid+①){
 ②;
 }else{
 ③;
  }
 }
 return ④;
}
int main(){
 int n;
 cin>>n;
 vector<int> nums(n);
 for(int i=0;i<n;i++) cin>>nums[i];
 int misssing_number=find_missing(nums);
 if(missing_number==⑤){
 cout<<"Sequence is consecutive"<<endl;
 }else{
 cout<<"Missing numbers is"<<missing_number<<endl;
 }
return 0;
}

②处应填（ ）

共 3 分　

第35题

（寻找被移除的元素）问题，原有长度为n+1,公差为1的等差升序数列，将序列输入到程序的数组时移除了一个元素，导致长度为n的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums){
 int left=0,right=nums.size()-1;
 while(left<right){
 int mid=left+(right-left)/2;
 if(nums[mid]==mid+①){
 ②;
 }else{
 ③;
  }
 }
 return ④;
}
int main(){
 int n;
 cin>>n;
 vector<int> nums(n);
 for(int i=0;i<n;i++) cin>>nums[i];
 int misssing_number=find_missing(nums);
 if(missing_number==⑤){
 cout<<"Sequence is consecutive"<<endl;
 }else{
 cout<<"Missing numbers is"<<missing_number<<endl;
 }
return 0;
}

③处应填（ ）

共 3 分　

第36题

（寻找被移除的元素）问题，原有长度为n+1,公差为1的等差升序数列，将序列输入到程序的数组时移除了一个元素，导致长度为n的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums){
 int left=0,right=nums.size()-1;
 while(left<right){
 int mid=left+(right-left)/2;
 if(nums[mid]==mid+①){
 ②;
 }else{
 ③;
  }
 }
 return ④;
}
int main(){
 int n;
 cin>>n;
 vector<int> nums(n);
 for(int i=0;i<n;i++) cin>>nums[i];
 int misssing_number=find_missing(nums);
 if(missing_number==⑤){
 cout<<"Sequence is consecutive"<<endl;
 }else{
 cout<<"Missing numbers is"<<missing_number<<endl;
 }
return 0;
}

④处应填（ ）

共 3 分　

第37题

（寻找被移除的元素）问题，原有长度为n+1,公差为1的等差升序数列，将序列输入到程序的数组时移除了一个元素，导致长度为n的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums){
 int left=0,right=nums.size()-1;
 while(left<right){
 int mid=left+(right-left)/2;
 if(nums[mid]==mid+①){
 ②;
 }else{
 ③;
  }
 }
 return ④;
}
int main(){
 int n;
 cin>>n;
 vector<int> nums(n);
 for(int i=0;i<n;i++) cin>>nums[i];
 int misssing_number=find_missing(nums);
 if(missing_number==⑤){
 cout<<"Sequence is consecutive"<<endl;
 }else{
 cout<<"Missing numbers is"<<missing_number<<endl;
 }
return 0;
}

⑤处应填（ ）

共 3 分　

第38题

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x,int y,int z){
 return min(min(x,y),z);
}
int edit_dist_dp(string str1,string str2){
 int m=str1.length();
 int n=str2.length();
 vector<vector<int>> dp(m+1,vector<int>(n+1));
 for(int i=0;i<=m;i++){
 for(int j=0;j<=n;j++){
 if(i==0)
 dp[i][j]=(1);
 else if(j==0)
 dp[i][j]=(2);
 else if((3))
 dp[i][j]=(4);
 else
 dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],(5));
 }
 }
 return dp[m][n];
}
int main(){
 string str1,str2;
 cin>>str1>>str2;
 cout<<"Mininum number of operation:"
 <<edit_dist_dp(str1,str2)<<endl;
 return 0;
}

①处应填（ ）

共 3 分　

第39题

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x,int y,int z){
 return min(min(x,y),z);
}
int edit_dist_dp(string str1,string str2){
 int m=str1.length();
 int n=str2.length();
 vector<vector<int>> dp(m+1,vector<int>(n+1));
 for(int i=0;i<=m;i++){
 for(int j=0;j<=n;j++){
 if(i==0)
 dp[i][j]=(1);
 else if(j==0)
 dp[i][j]=(2);
 else if((3))
 dp[i][j]=(4);
 else
 dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],(5));
 }
 }
 return dp[m][n];
}
int main(){
 string str1,str2;
 cin>>str1>>str2;
 cout<<"Mininum number of operation:"
 <<edit_dist_dp(str1,str2)<<endl;
 return 0;
}

②处应填（ ）

共 3 分　

第40题

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x,int y,int z){
 return min(min(x,y),z);
}
int edit_dist_dp(string str1,string str2){
 int m=str1.length();
 int n=str2.length();
 vector<vector<int>> dp(m+1,vector<int>(n+1));
 for(int i=0;i<=m;i++){
 for(int j=0;j<=n;j++){
 if(i==0)
 dp[i][j]=(1);
 else if(j==0)
 dp[i][j]=(2);
 else if((3))
 dp[i][j]=(4);
 else
 dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],(5));
 }
 }
 return dp[m][n];
}
int main(){
 string str1,str2;
 cin>>str1>>str2;
 cout<<"Mininum number of operation:"
 <<edit_dist_dp(str1,str2)<<endl;
 return 0;
}

③处应填（ ）

共 3 分　

第41题

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x,int y,int z){
 return min(min(x,y),z);
}
int edit_dist_dp(string str1,string str2){
 int m=str1.length();
 int n=str2.length();
 vector<vector<int>> dp(m+1,vector<int>(n+1));
 for(int i=0;i<=m;i++){
 for(int j=0;j<=n;j++){
 if(i==0)
 dp[i][j]=(1);
 else if(j==0)
 dp[i][j]=(2);
 else if((3))
 dp[i][j]=(4);
 else
 dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],(5));
 }
 }
 return dp[m][n];
}
int main(){
 string str1,str2;
 cin>>str1>>str2;
 cout<<"Mininum number of operation:"
 <<edit_dist_dp(str1,str2)<<endl;
 return 0;
}

④处应填（ ）

共 3 分　

第42题

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x,int y,int z){
 return min(min(x,y),z);
}
int edit_dist_dp(string str1,string str2){
 int m=str1.length();
 int n=str2.length();
 vector<vector<int>> dp(m+1,vector<int>(n+1));
 for(int i=0;i<=m;i++){
 for(int j=0;j<=n;j++){
 if(i==0)
 dp[i][j]=(1);
 else if(j==0)
 dp[i][j]=(2);
 else if((3))
 dp[i][j]=(4);
 else
 dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],(5));
 }
 }
 return dp[m][n];
}
int main(){
 string str1,str2;
 cin>>str1>>str2;
 cout<<"Mininum number of operation:"
 <<edit_dist_dp(str1,str2)<<endl;
 return 0;
}

⑤处应填（ ）

共 3 分　

试卷信息

题量: 42 道
总分: 99 分 
一、选择题（1-15 共 15 题）；
二、阅读程序（16-32 共 17 题）；
三、完善程序（33-42 共 10 题）。
第1题 第2题 第3题 第4题 第5题 第6题 第7题 第8题 第9题 第10题 第11题 第12题 第13题 第14题 第15题 第16题 第17题 第18题 第19题 第20题 第21题 第22题 第23题 第24题 第25题 第26题 第27题 第28题 第29题 第30题 第31题 第32题 第33题 第34题 第35题 第36题 第37题 第38题 第39题 第40题 第41题 第42题