2023年CSP-J认证 CCF信息学奥赛C++ 中小学初级组 第一轮真题-完善程序题解析

本文主要是介绍2023年CSP-J认证 CCF信息学奥赛C++ 中小学初级组 第一轮真题-完善程序题解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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] = ④;elsedp[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

这篇关于2023年CSP-J认证 CCF信息学奥赛C++ 中小学初级组 第一轮真题-完善程序题解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/791340

相关文章

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三