2020年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第2题）

2020年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第2题）

第2题

1#include<iostream>2#include<cstdlib>3usingnamespacestd;45intn;6intd[10000];78intfind(intL,intR,intk){9intx=rand()%(R-L+1)+L;10swap(d[L],d[x]);11inta=L+1,b=R;12while(a<b){13while(a<b&&d[a]<d[L])14++a;15while(a<b&&d[b]>=d[L])16--b;17swap(d[a],d[b]);18}19if(d[a]<d[L])20++a;21if(a-L==k)22returnd[L];23if(a-L<k)24returnfind(a,R,k-(a-L));25returnfind(L+1,a-1,k);26}2728intmain(){29intk;30cin>>n;31cin>>k;32for(inti=0;i<n;++i)33cin>>d[i];34cout<<find(0,n-1,k);35return0;36}

假设输入的 n,k 和 d[i]都是不超过 10000的正整数，且 k不超过 n，并假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：

• 判断题

  1. 第 9行的 x 的数值范围是 L+1 到 R，即 [L+1,R]。（ ）

     A. 正确 B. 错误

  2. 将第 19 行的d[a]改为d[b]，程序不会发生运行错误。（ ）

     A. 正确 B. 错误

• 单选题

  1. （2.5 分）当输入的 d[i]是严格单调递增序列时，第 17 行的swap平均执行次数是( )。

     A. O(nlog⁡n)

     B. O(n)

     C. O(log⁡n)

     D. O(n 2 n^2n2)

  2. （2.5 分）当输入的 d[i] 是严格单调递减序列时，第 17 行的swap平均执行次数是( )。

     A. O(n 2 n^2n2)

     B. O(n)

     C. O(nlog⁡n)

     D. O(log⁡n)

  3. （2.5 分）若输入的 d[i] 为i，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。

     A. O(n) , O(n 2 n^2n2)

     B. O(n) , O(nlog⁡n)

     C. O(nlog⁡n) , O(n 2 n^2n2)

     D. O(nlog⁡n) , O(nlog⁡n)

  4. （2.5 分）若输入的 d[i] 都为同一个数，此程序平均的时间复杂度是( )。

     A. O(n)

     B. O(log⁡n)

     C. O(nlog⁡n)

     D. O(n 2 n^2n2)

判断题答案及解析

1. 错误。第9行的x = rand() % (R - L + 1) + L，随机数范围是[L, R]，包括L，而不是[L+1, R]。
2. 正确。原程序在区间长度为1时，a = L+1会越界访问；改为d[b]后，b = R = L在合法范围内，避免了运行错误。

单选题答案及解析

1. A/B。错题，不随便算一个答案。
2. B。对于严格单调递减序列，同理，平均交换次数也为O(n)。
3. A。输入为i（递增序列）时，平均时间复杂度为O(n)，最坏情况（每次选到最小或最大）为O(n²)。
4. D。输入全相同时，每次划分只能排除一个元素，递归深度为n，总比较次数为O(n²)。

专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}