青少年编程能力等级测评CPA C++(三级)-试卷1
一、单项选择题(共15题,每题3分,共45分)
CP3_1_1.以下有关模拟算法的叙述中,不正确的是( )。
A.模拟算法适于解决那些难于通过经典算法和建立数学模型求解的问题
B.模拟算法实现较为简单,只要按照问题原本的思路求解即可a
C.模拟算法较之其他算法具有时间复杂度的优势
D.模拟算法实现中,代码本身蕴含的算法思维较少
CP3_1_2.有鸡和兔在一个笼子中,数头共50个头,数脚共120只脚,问:鸡和兔分别有多少只?用穷举法求解该问题,下列方案中,能够有效降低算法时间复杂度的是( )。
A.根据脚数,限制代表兔子数量的变量的循环上限
B.根据总数量,用表示鸡的变量推导兔子的数量,将双重循环降为单重循环
C.用宏预处理鸡、兔的数量关系
D. 用函数代替表达式,求解两种动物的数量
CP3_1_3.在下列代码中,迭代关系语句是( )。
#include <iostream>
using namespace std;
int main(){
int day=10,num=1;
while(day){
num=(num+1)*2;
day--;
}
cout<<num<<endl;
return 0;
}
A.num=(num+1)*2;
B.d--;
C.整个while()循环语句
D.int day=10,num=1;
CP3_1_4.运行下列代码,输出结果是( )。
#include <iostream>
using namespace std;
int main( ){
int a[ ] = {1,3,5,7};
for(int i = 0;i < 4; i++){
a[i]=a[i]+i;
cout<<a[i]<< '\t';
}
return 0;
}
A.2 4 6 8
B.1 4 8 12
C.1 4 7 10
D.3 6 9 12
CP3_1_5.在直接选择排序算法中,与记录的初始排列状态相关的是( )。
A.算法的时间复杂度
B.算法的空间复杂度
C.关键码的比较次数
D.排序过程中数据移动的总次数
CP3_1_6.折半插入排序算法是对插入排序算法的一种改进。下列有关算法改进核心点的叙述中,正确的是( )。
A.减少了数据移动的次数
B.减少了数据比较的次数
C.降低了算法的时间复杂度
D.降低了算法的空间复杂度
CP3_1_7.下列各组数据,用冒泡排序法进行从小到大排序,则需要交换次数最多的是( )。
A.12 5 8 9 7
B.12 5 9 8 7
C.5 8 9 7 12
D.5 9 7 12 8
CP3_1_8.下列排序算法分类中,快速排序算法所属的分类是( )。
A.交换排序
B.插入排序
C.选择排序
D.基数排序
CP3_1_9.数组a定义为:int a[]={205,408,471,498,621,829,833,940}; 进行二分查找,设定查找键为key。若第一个被访问到的数据是498,小于key值,则第二个被访问到的数据是( )。
A.408
B.829
C.833
D.940
CP3_1_10.下列代码为分治策略实现的二分查找算法,参数key为要查找的键。/**(1)**/处应填写的函数调用表达式为( )。
int bsearch(int array[], int low, int high, int key)
{
if (low > high)
return -1; //边界设置不合理,返回-1
int mid = (low + high)/2;
if (array[mid]> key)
return /**(1)**/ ;
if (array[mid]< key)
return bsearch(array, mid+1, high, key);
if (midValue == key)
return mid;
}
A.bsearch(array, low+1, mid, key)
B.bsearch(array, low, high, key)
C.bsearch(array, low, mid -1, key)
D.bsearch(array, low-1, high, key)
CP3_1_11.已知货币面值为100元、50元、20元、10元、5元、1元,购买价格为n元的商品,恰好完成支付,至少需要支付几张货币。下列代码实现该功能,则/**(1)**/处需要填写的语句是( )。
#include <iostream>
using namespace std;
const int money[] = {100,50,20,10,5,1}; //货币面值
int main(){
int n,count = 0;
cin >> n;
for (int i = 0; i <= 5; i++){
/**(1)**/
n = n % money[i];
}
cout << count << endl;
return 0;
}
A. count += money[i];
B. count += n - money[i];
C. count += n – n / money[i];
D. count += n / money[i];
CP3_1_12.执行下列程序,输出结果是( )。
#include<iostream>
#include<cstring>
using namespace std;
int main(){
char s1[20]="cplus";
char s2[20]="language";
cout<<strcat(s1+1,s2+strlen(s2)/2)<<endl;
return 0;
}
A.cuage
B.cpluuage
C.plusuage
D.pluslang
CP3_1_13.下列通过string定义字符串的语句,错误的是( )。
A.string s; s = "hello C++";
B.string s = "hello C++";
C.string s("hello C++");
D.string s["hello C++"];
CP3_1_14.对如图所示的二叉树进行深度优先遍历,用栈存储访问到的节点,则第5个入栈的节点值是( )。
A.8
B.9
C.5
D.6
CP3_1_15.在面向对象方法中,信息隐蔽实现的机制是( )。
A. 对象的多态性
B. 对象的继承性
C. 对象的封装性
D. 对象的共享性
二、多项选择题(共5题,每题3分,共15分)
CP3_1_16.下列排序算法,其平均时间复杂度高于O(nlog2n)的有( )。
A.堆排序
B.直接插排序入
C.冒泡排序
D.快速排序
CP3_1_17.下列有关局部最优解和全局最优解的叙述中,正确的有( )。
A.局部最优解不一定是全局最优解,全局最优解一定是局部最优解
B.贪心算法是以局部最优解为目标的,但根据局部最优解一定能够得出全局最优解
C.所有全局最优解问题都可以通过贪心算法得以解决
D.局部最优解经过优化均可形成全局最优解
CP3_1_18.下列方法中,可用做优化广度优先算法的有( )。
A.双向搜索法
B.启发式搜索
C.等效冗余排除
D.用堆栈替代队列
CP3_1_19.在C++中,类的成员具有的访问控制权限有( )。
A. public
B. private
C. protected
D. personal
CP3_1_20. 设Demo为已定义的一个类,则下列有关该类的对象定义语句,正确的有( )。
A. Demo int a;
B. Demo arr[5];
C. Demo *p = new Demo( );
D. class Demo b;
三、编程题(共2题,每题20分,总分40分)
CP3_1_21.
猴子第一天摘下若干桃子,当即吃下了一半,还不过瘾,又多吃了一个;第二天又将剩余的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩余桃子的一半多一个。到第n天再想吃时,发现桃子就剩一个了。编写程序,输入一个正整数代表只剩一个桃子的第n天,输出第一天摘的桃子数。
样例1
输入: 5
输出: 46
样例2:
输入:2
输出:4
CP3_1_22.
某校有8位同学参加数学竞赛,得分均为60至100之间的正整数(包括60和100在内)。编程输入8个满足要求的分数,并对这些分数从高到低进行排序并输出。
注意:
(1)输入的不符合要求的分数将被忽略。
(2)编程过程中对于程序给定的部分不允许修改,考生仅允许在/****code****/提示行区间内作答。
#include <iostream>
using namespace std;
int main(){
int i,j,k,temp,score[8];
for(i=0;i<8;i++){
/************code**********/
/************code**********/
}
for (i=0;i<8;i++)
cout<<score[i]<<" "; //循环输出排列好的分数
cout << endl;
return 0;
}
样例1
输入:67 78 98 75 77 89 90 65
输出:98 90 89 78 77 75 67 65
样例2:
输入:12 65 60 75 80 63 90 56 86 70
输出:90 86 80 75 70 65 63 60