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

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、