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

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

#### 第1题

01#include<cstdio>02usingnamespacestd;03intn;04inta[100];0506intmain(){07scanf("%d",&n);08for(inti=1;i<=n;++i)09scanf("%d",&a[i]);10intans=1;11for(inti=1;i<=n;++i){12if(i>1&&a[i]<a[i-1])13ans=i;14while(ans<n&&a[i]>=a[ans+1])15++ans;16printf("%d\n",ans);17}18return0;19}

• 判断题

1. （1 分）第 16 行输出 ans时，ans的值一定大于 i。（）

   A. 正确 B. 错误

2. （1 分）程序输出的 ans 小于等于 n。（）

   A. 正确 B. 错误

3. 若将第 12 行的<改为!=，程序输出的结果不会改变。（）

   A. 正确 B. 错误

4. 当程序执行到第 16 行时，若 ans−i>2，则 a[i+1]≤a[i]。 （）

   A. 正确 B. 错误

• 选择题

5.（3 分）若输入的 a数组是一个严格单调递增的数列, 此程序的时间复杂度（）

A. O(log⁡n)

B. O(n 2 n^2n2)

C. O(nlog⁡n)

D. O(n)

6.最坏情况下，此程序的时间复杂度是（）。

A. O(n 2 n^2n2)

B. O(log⁡n)

C. O(n)

D. O(nlog⁡n)

答案及解析

判断题

1. B。第16行输出ans时，ans的值不一定大于i。例如当i=1时，ans可能等于1，因此ans可能等于i，不一定大于。
2. A。while循环的条件保证ans < n时才增加，因此ans最大为n，所以输出值一定小于等于n。
3. A。将第12行的<改为!=后，虽然重置条件变化，但通过分析可知，无论上升还是下降，最终输出的ans与原来相同，因此结果不变。
4. A。若ans−i>2，则ans ≥ i+3，因此i+1在范围内。由while循环条件可知，a[i] ≥ a[i+1]成立，即a[i+1] ≤ a[i]。

选择题

5. D。当输入严格单调递增时，每个i的while循环只将ans从i-1增至i，总操作次数为O(n)。
6. A。最坏情况如严格单调递减序列，每个i的while循环都会从i遍历到n，总次数为1+2+…+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;}