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

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)