Dotcpp  /  试卷列表  /  CSP考试题库 - 第20页

CSP考试

第381题

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

#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;
}

④处应填（ ）

第382题

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

#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;
}

⑤处应填（ ）

第383题

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

#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;
}

①处应填（ ）

第384题

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

#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;
}

②处应填（ ）

第385题

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

#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;
}

③处应填（ ）

第386题

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

#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;
}

④处应填（ ）

第387题

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

#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;
}

⑤处应填（ ）

第388题

在linux 系统终端中，以下哪个命令用于创建一个新的目录?（）

第389题

0,1,2,3,4 中选取4个数字，能组成（）个不同四位数。(注: 最小的四位数是 1000最大的四位数是9999)

第390题

假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 m=O(n)的稀疏图而言，下面的四个选项，哪一项的渐进时间复杂度最小？（）

第391题

假设有n 根柱子，需要按照以下规则依次放置编号为 1,2,3..的圆柱：每根柱子的底部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4个根子时，最多可以放置（）个圆环。

第392题

以下对数据结构表述不恰当的一项是？（）

第393题

以下连通无向图中，（）一定可以用不超过两种颜色进行染色。

第394题

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列X={x1,x2,x3,…,xm}和Y={y1,y2,y3,…,yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z={z1,z2,z3,…,zk},使得序列Z既是序列X的子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最大的。(注：序列A是序列B的子序列，当且仅当在保持序列B元素顺序的情况下，从序列B中删除若干个元素，可以使得剩余的元素构成序列A。)则序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为（）

第395题

一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出x点，得到2x元；第二次掷出y点，当y=x时玩家会失去之前得到的2x元，而当y≠x时玩家能保住第一次获得的2x元。上述x,y∈{1,2,3,4,5,6}。例如：玩家第一次掷出3点得到6元后，但第二次再次掷出3点，会失去之前得到的6元，玩家最终收益为0元；如果玩家第一次掷出3点、第二次掷出4点，则最终收益是6元。假设骰子掷出任意一点的概率均为1/6,玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少?（）

第396题

假设我们有以下的C++代码：

int  a=5,b=3,c=4;
bool res = a & b ||c ^ b && a | c;

请问，res的值是什么?（）

提示：在C++中，逻辑运算的优先级从高到低依次为：逻辑非(!)、逻辑与(&&)、逻辑或(I)。位运算的优先级从高到低依次为：位非(~)、位与(&)、位异或(^)、位或(I)。同时，双目位运算的优先级高于双目逻辑运算；逻辑非和位非优先级相同，且高于所有双目运算符。

第397题

假设快速排序算法的输入是一个长度为 n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?（）

第398题

以下哪个命令，能将一个名为”main.cpp“的 C++源文件，编译并生成一个名为”main“的可执行文件?（）

第399题

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数量最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?（）

第400题

如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

有向图

知识点标签

全部 高校题库 Python试卷 NOIP真题 计算机网络 Mysql数据库 Linux 考研真题 Java试卷 计算机二级 数据结构与算法 CSP考试 C++试卷 C语言试卷