2023-2023年noip初赛提高组c++语言试题及参考答案.doc

2023-2023年NOIP初赛提高组C++语言试题及参考答案
2
2023-2023年NOIP初赛提高组C++语言试题
2023第十九届全国青少年信息学奥林匹克联赛初赛
提高组C++语言试题 竞分；每题有一个或多个正确选项，多项选择或少选均不得分〕
，正确计算1,2,…,100这100个自然数之和sum〔初始值为0〕的是〔〕。
A.
for(i=1;i<=100;i++)
sum+=i;
B.
i=1;
while(i>100){
sum+=i;
i++;
}
C.
i=1;
D.
i=1;
4
do{
sum+=i;
i++;
}while(i<=100);
do{
sum+=i;
i++;
}while(i>100);
2.〔〕的平均时间复杂度为O(n log n)，其中n是待排序的元素个数。

，对下面的无向图进行深度优先遍历时〔遍历的顺序与顶点字母的下标无关〕，最后一个遍历到的顶点可能是〔 〕。

4.〔〕属于NP类问题。



〔输入规模的〕指数时间内能够解决的问题
NOIP复赛考试结束后，因〔〕提出的申诉将不会被受理。

，未提交源程序
三、问题求解〔共2题，每题5分，共计10分；每题全部答对得5分，没有不得分〕
。密码是n个数s1,s2,…,sn，均为0或1。该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户答复(s1a1+s2a2+…+snan)除以2的余数。如果屡次的答复总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。
然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答：
就破解出了密码s1=_________，s2=_________，s3=_________，s4=_________。
，初始时在n号荷叶上。当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1,2,…,k号荷叶之一上，直至跳到1号荷叶为止。当n=2时，平均一共跳2次；当n=3时，。那么当n=5时，平均一共跳_________次。
5
四、阅读程序写结果〔共4题，每题8分，共计32分〕
1.#include<iostream>
#include<string >
using namespace std;
int main( )
{ string
Str;
cin>>str;
int n = ( );
bool isPlalindrome = true;
for (int i =0; i<n/2;i++){
if (str[i] !=str[n-i-1]) isPlalindrome = false;
}
if(isPlalindrome)
cout << 〞Yes〞 << endl;
else cout << 〞No〞 << endl;
}
输入：abceecba
输出：_________
2. #include<iostream>
using namespace std;
int main( )
{
int a,b,u,v,i, num;
cin >>a>>b>>u>>v;
num =0;
for ( i= a; I <=b; i++)
6
if (((i%u) ==0)||((i%v)==0))
num ++;
count <<num<<endl;
return 0;
}
输入：1 1000 10 15
输出：_________
3. #include<iostream>
using namespace std;
int main( )
{
const int SIZE = 100;
int height[