2023CCF认证第一轮（CSP-J）真题
三、完善程序题
第一题 寻找被移除的元素
问题：原有长度为 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 missing_number = find_missing(nums);
if (missing_number == ⑤) {
cout << "Sequence is consecutive" << endl;
}else{
cout << "Missing number is " << missing_number << endl;
}
return 0;
}
程序分析：此程序的主要思路是使用二分查找来找到缺失的数
- 首先，定义左右两个指针，表示查找范围的左右边界
- 然后，进入一个循环，在循环内部进行二分查找
- 在每次循环中，计算中间位置mid，并比较nums[mid]与mid + nums[0]的大小
- 如果相等，说明缺失的数在右侧，更新左指针为mid + 1
- 如果不相等，说明缺失的数在左侧或者当前位置就是缺失的数，更新右指针为mid
- 循环终止条件是左指针小于右指针
- 最后，返回左指针加上序列的起始数nums[0]，即为缺失的数
- 在main函数中，首先读取序列的长度n。然后，使用循环将序列的元素读入到数组nums中
- 接下来，调用find_missing函数找到缺失的数，并将结果保存在missing_number变量中
- 最后，通过比较missing_number和序列的最后一个数nums[n-1]来判断是否连续
- 如果相等，则说明序列是连续的；否则，输出缺失的数
- 整个代码的时间复杂度为O(log n)，其中n为序列的长度
单选题
①处应该填
A. 1
B. nums[0]
C. right
D. left
答案：B
答案分析：从程序分析中可以得知此处应该是B
②处应该填
A. left=mid+1
B. right=mid−1
C. right=mid
D. left=mid
答案：A
答案分析：从程序分析中可以得知此处应该是A
③处应该填
A. left=mid+1
B. right=mid−1
C. right=mid
D. left=mid
答案：C
答案分析：从程序分析中可以得知此处应该是C
④处应该填
A. left+nums[0]
B. right+nums[0]
C. mid+nums[0]
D. right+1
答案：A
答案分析：从程序分析中可以得知此处应该是A
⑤处应该填
A. nums[0]+n
B. nums[0]+n−1
C. nums[0]+n+1
D. nums[n−1]
答案：D
答案分析：从程序分析中可以得知此处应该是D
第二题 编辑距离
给定两个字符串，每次操作可以选择删除(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] = ①;
else if (j == 0)
dp[i][j] = ②;
else if (③)
dp[i][j] = ④;
else
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
}
}
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;
}
程序分析：此程序实现了使用动态规划算法求解两个字符串之间的编辑距离
- 代码中的函数min()用于返回三个整数中的最小值。
- 函数edit_dist_dp()使用了一个二维矩阵dp来保存中间计算结果
- 矩阵的行数和列数分别是两个字符串的长度加1，这是因为字符串的下标从1开始计数，而矩阵的下标从0开始计数
- 在双重循环中，矩阵的第一行和第一列分别表示空字符和另一个字符串的前缀的编辑距离
- 所以首先需要初始化矩阵的第一行和第一列
- 接着，通过比较当前字符是否相等来判断是否需要进行替换操作
- 如果当前字符相等，则当前位置的编辑距离与前一个位置的编辑距离相同；否则，需要进行一次替换操作
- 最后，返回矩阵的右下角元素，即两个字符串的编辑距离
- 在main()函数中，先从标准输入读取两个字符串，然后调用edit_dist_dp()函数计算编辑距离，并将结果输出到标准输出
单选题
①处应该填
A. j
B. i
C. m
D. n
答案：A
答案分析：从程序分析中可以得知此处应该是A
②处应该填
A. j
B. i
C. m
D. n
答案：B
答案分析：从程序分析中可以得知此处应该是B
③处应该填
A. str1[i−1]==str2[j−1]
B. str1[i]==str2[j]
C. str1[i−1]!=str2[j−1]
D. str1[i]!=str2[j]
答案：A
答案分析：从程序分析中可以得知此处应该是A
④处应该填
A. dp[i−1][j−1]+1
B. dp[i−1][j−1]
C. dp[i−1][j]
D. dp[i][j−1]
答案：B
答案分析：从程序分析中可以得知此处应该是B
⑤处应该填
A. dp[i][j]+1
B. dp[i−1][j−1]+1
C. dp[i-1][j-1]
D. dp[i][j]
答案：C
答案分析：从程序分析中可以得知此处应该是C