PAAT全国青少年编程能力等级考试C++编程高级样题1

全国青少年编程能力等级考试C++（高级）-样卷 一、单项选择题（共20题，每题3分，共60分） CP3_1_1．下列有关算法特点的叙述中，符合模拟算法的是（）。 A．不遗漏任何一个正确解，结果最可靠 B．可以将大规模的问题有效进行拆解，各个击破 C．运行效率最高 D．最接近于真实的事物或过程 CP3_1_2．下列有关提高穷举算法效率的方法中，不能 ．． 提高穷举算法效率的方法是（）。 A．通过推导，减少穷举的范围和数量 B．通过预处理，避免重复的计算发生 C．用更小规模的函数分解现有函数 D.以空间换时间，避免重复的判断发生 CP3_1_3．在下列求解斐波那契(Fibonacci)数列的函数中，体现迭代关系的是（）。 intFib(intn){ if(n<1) return0; if(n==1||n==2) return1; intf1=1,f2=1,fn; inti; for(i=3;i<=n;++i){ fn=f1+f2; f1=f2; f2=fn; } returnfn; } A．整个for语句 B．fn=f1+f2; C．f1=f2; D．f2=fn; CP3_1_4．运行下列代码，输出结果是（）。 #include<iostream> usingnamespacestd; intmain(){ inta[5]={1,2,3,4}; for(int*p=a;p!=a+4;p++){ cout<<*p+*(p+1)<<'\t'; } return0; } A．1234 B．3574 C．1357 D．5751 CP3_1_5．下列有关选择排序算法的叙述中，正确的是（）。 A．选择排序算法是不稳定的排序算法 B．对于同一数列，选择排序的速度快于冒泡排序 C．直接选择排序算法的时间复杂度为O(n) D．选择排序算法数据总的比较次数与关键字序列的初始状态相关 CP3_1_6．下列代码，若能实现整型数组的直接插入排序，则while(Cond)中，Cond 对应的表达式是（）。 #include<iostream> usingnamespacestd; inta[100]; intmain() { intn,i,f,j; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; for(i=2;i<=n;i++) { f=a[i],j=i-1; while(Cond) a[j+1]=a[j--]; a[j+1]=f; } for(i=1;i<=n;i++) cout<<a[i]<<""; return0; } A．j>=0&&a[j]>f B．j>0&&a[j]>f C．j>=0||a[j]>f D．j>0||a[j]>f CP3_1_7．下列各组数据，用冒泡排序算法进行从小到大排序，则需要交换次数最多的是 （）。 A．12-9157 B．12571-9 C．1-91257 D．-957112 CP3_1_8．下列排序算法中，本质上属于插入排序的是（）。 A．希尔排序 B．堆排序 C．快速排序 D．归并排序 CP3_1_9．二分算法所采用的核心策略是（）。 A．回溯策略 B．动态规划策略 C．分治策略 D．贪心策略 CP3_1_10．若key在有序数组中一定存在，通过二分查找算法，查找key在数组中的位 置，则下列代码//(1)处需要填写的语句是（）。