青少年编程能力等级测评CPA C++（三级）-试卷2

一、单项选择题（共15题，每题3分，共45分）

CP3_2_1．在宽度为500米的河道上，修建一个拦河大坝。施工队每天筑坝50米，由于当时条件所限，晚上又被河流冲毁15米，求施工队需要几天完成500米的筑坝任务。下列代码实现该功能，则/**(1)**/处需要填写的语句是（  ）。

#include <iostream>

using namespace std ;

int main(void) {

    int amount = 0;

    int days = 0;

    while (true) {  

        amount += 50;

        days++;

        if (amount >= 500)

            break;  

        /**(1)**/

    }

    cout << days << endl;  

    return 0;

}

A．amount += 15;

B．amount += 50;

C．amount -= 15;

D．amount -= 50;

CP3_2_2．下列有关穷举算法的叙述中，不正确的是（  ）。

A．使用穷举法，必须满足的条件是解的个数有限且可以列举

B．使用穷举法，需确定答案要满足的条件

C．穷举法得到的结果一定是正确的

D．穷举法适用于任何问题

CP3_2_3．有数列1，1/1!，1/2!，1/3!，1/4!，1/5!...（其中n!表示n的阶乘），下列代码计算数列第10项的值，则迭代关系语句是（  ）。

#include <iostream>

using namespace std;

int main(){

    int i=1;

    double num=1.0;

    while(i <10){

        num *= 1.0 / i;

        i++;

    }

    cout<<num<<endl;

    return 0;

}

A．double num=1.0;;

B．int i=1;

C．整个while()循环语句

D．num *= 1.0 / i;

CP3_2_4．运行下列代码，输出结果是（  ）。

#include <iostream>

using namespace std;

int main( ){

    int a[ ] = {1,2,3,4,5},b[5];

    for(int i = 0;i < 5; i++)

        b[i]=a[i]+a[4-i];

    for(int i=0; i<5; i++)

        cout<<b[i]<< '\t';

    return 0;

}

A．3 3 3 3 3

B．6 6 6 6 6

C．3 5 7 9 6

D．2 4 6 8 10

CP3_2_5．使用选择排序算法（每趟最多交换一次）对一组数“19，28，12，7，66，31，24”进行升序排序，则第三趟结束后，这组数的顺序是（  ）。

A．19，28，12，7，66，31，24

B．7，19，12，28，66，31，24

C．7，12，19，24，66，31，28

D．7，12，19，28，66，31，24

CP3_2_6．用直接插入排序算法对一组数“100，80，12，66，31，19，28”进行升序排序，则第四趟结束后，这组数的顺序是（  ）。

A．80，100，12，66，31，19，281

B．12，80，100，66，31，19，282

C．12，31，66，80，100，19，284

D．12，66，80，100，31，19，283

CP3_2_7．用冒泡排序算法对一组数“48，98，23，45，62，51”进行升序排序，下列叙述正确的是（  ）。

A．对于这组数排好序需要1趟

B．对于这组数排好序需要2趟

C．对于这组数排好序需要3趟

D．对于这组数排好序需要4趟

CP3_2_8．下列有关排序算法稳定性的叙述中，正确的是（  ）。

A．如待排序的一组数有相同的数值，排序后这些数的相对次序一定保持不变，则排序算法是稳定的

B．同一组数的初始顺序不同，排序总的比较次数相同，则排序算法是稳定的

C．同一组数的初始顺序不同，排序总的交换次数相同，则排序算法是稳定的

D．同一组数的初始顺序不同，排序总的比较次数和总的交换次数都相同，则排序算法是稳定的

CP3_2_9．已经按升序排列好的一组数“20,40,47,58,62,82,94”，使用二分查找算法在这组数中查找200，判断出200不在这组数中，需要比较的次数是（  ）。

A．3次

B．4次

C．1次

D．2次

CP3_2_10．一个装有16枚硬币的袋子，其中有一个硬币是伪造的，并且伪造的硬币比真的硬币要轻（真币重量10，假币重量9）。现有一台可用来比较两组硬币重量的仪器（下面程序中的sum函数模拟对一组硬币称重），下列程序使用分治法找出那枚伪造的硬币（输出伪币的下标）。在/**(1)**/处应填写的表达式为（  ）。

#include <iostream>

using namespace std;

int sum(int a[], int m, int n)    //求重量和 （a[m]+a[m+1]+…+a[n]）

{

    int sum = 0;     

    for (int i = m; i <= n; i++)     

    {         

        sum += a[i];

    }

    return sum;

}

int find(int a[], int left, int right) {

    if (right - left == 1)  //只剩2个硬币

        return a[right] > a[left] ? left : right;

    int mid = (right + left) / 2;

    if ((right - left) % 2 == 0)//硬币数量为奇数

    {

        if(a[mid]<10)   //mid 就是伪币，返回下标mid 

            return mid;    

        int sumLeft = sum(a, left, mid - 1);   //前面一组硬币重量之和

        int sumRight = sum(a, mid + 1, right); //后面一组硬币重量之和

        if(sumLeft > sumRight)    //假币在后面一组

            return find(a, mid + 1, right);

        else      //假币在前面一组

            return find(a, left, mid - 1);

    }

    else //硬币数量为偶数

    {         

        int sumLeft = /**(1)**/ ;

        int sumRight = sum(a, mid + 1, right);

        if(sumLeft > sumRight)  

            return find(a, mid + 1, right);

        else

            return find(a, left, mid - 1);  

    }

 }

int main()

{

    int a[16]= {10,10,10,10,10,10,9,10,10,10,10,10,10,10,10,10};

    int index = find(a,0,15);

    cout << index << endl;

    return 0;

}

A．sum(a, left, mid - 1)

B．sum(a, mid , right)

C．sum(a, left, mid)

D．sum(a, mid, right)

CP3_2_11．使用贪心法求解0-1背包问题。已知一背包能装入25kg的物品，现有重量、价值各不相同的8件物品，如何选择装入背包的物品，使装入物品的总价值最大。贪心策略是优先将性价比高的物品装入背包。下列代码实现该功能，则/**(1)**/处需要填写的语句是（  ）。

说明：程序中定义了cmp()函数，是为了使用sort(items,items+n,cmp) 对items按性价比降序排序。

#include<iostream>

#include<algorithm>

using namespace std;

struct item{  //物品

    float weight;  //重量

    float value;   //价值

    float ratio;   //性价比（单位重量的价值）

};

bool cmp(struct item a, struct item b) //排序用的函数，考生不必研究 

{

    return a.ratio > b.ratio;

}

int main()

{

    int n=8;

    float c = 25;  //背包剩余的容量（还可以装入物品的重量）

struct item items[] = { {5,10},{8,11},{6,9},{2,8},

                             {7,19},{8,15},{1,1},{2,1} };

    for(int i=0; i<n; i++)  //计算性价比

       items[i].ratio = items[i].value/items[i].weight;

    sort(items,items+n,cmp);   //对items按性价比降序排序究 

    float sum= 0;    //已装入物品的总价值

    for (int i = 0; i < n; i++)

    {

        if ( items[i].weight <= c)  //将物品i装入背包

        {

            sum += items[i].value;

            /**(1)**/

        }

     }

     cout << "装入的总价值：" << sum << endl;

}

A．c -= items[i].weight;

B．c += items[i].weight;

C．c -= items[i].value;

D．c += items[i].value;

CP3_2_12．执行下列程序，输出结果是（  ）。

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

    char a[10] = "Program";

    char b[10] = "Programer";

    char c[10] = "Problem";

    int i,j,k;

    i = strcmp(a,b);

    j = strcmp(a,c);

    k = strcmp(a,"Program");

    cout << i <<"  " << j << "  " << k <<  endl;

    return 0;

}

A．1  -1  0

B．-1  1  0

C．-1  0  1

D．1  0  -1

CP3_2_13．执行下列程序，输出结果是（  ）。

#include <iostream>

#include <string>

using namespace std;

int main()

{

    string s1= "Program";

    string s2;

    s2.assign(s1,2,4);

    cout << s2 <<  endl;

    return 0;

}

A．Program

B．ogram

C．ogra

D．ra

CP3_2_14．若对如图所示的有向图进行遍历，则属于深度优先遍历序列的是（  ）。

A．A→B→E→C→D→F→G

B．A→B→C→E→D→F→G

C．A→B→F→G→E→C→D

D．A→B→C→E→F→G→D

CP3_2_15．下列有关面向对象程序设计的叙述中，错误的是（  ）。

A．在面向对象程序设计中，程序的模块是由类构成的

B．在面向对象程序设计中，将数据与操作数据的函数封装在一起构成类

C．在面向对象程序设计中，继承可以减少程序中的重复代码

D．在面向对象程序设计中，多态是指一个类中不同的函数完成不同的功能

二、多项选择题（共5题，每题3分，共15分）

CP3_2_16．下列有关排序算法的叙述中，正确的有（  ）。

A．选择排序，总的比较次数和数据的初始顺序无关

B．插入排序，所需时间与数据的初始顺序有关

C．冒泡排序是不稳定的排序

D．插入排序，第k次外层循环后，前k个元素已经是排好序的

CP3_2_17．下列有关局部最优解和全局最优解的叙述中，不正确的有（  ）。

A．若一项决策和解决该问题的所有决策相比较是最优的，被称为全局最优解

B．若一项决策和解决该问题的部分决策相比较是最优的，被称为局部最优解

C．全局最优解不一定是局部最优解

D．任何问题都可以使用贪心算法得到全局最优解

CP3_2_18．若对如图所示的无向图进行遍历，则属于广度优先遍历序列的有（  ）。

A．A→B→C→D→E→F→G→H

B．A→B→D→C→F→E→G→H

C．A→C→B→F→E→D→G→H

D．A→C→F→E→G→H→B→D

CP3_2_19．下列关于面向对象程序设计的叙述中，正确的有（  ）。

A．在面向对象的程序设计中，类的数据成员称为属性

B．在面向对象的程序设计中，类的函数成员称为方法

C．类的方法只能在类的内部定义

D．类的方法可以在类的内部定义，也可以在类的外部定义

CP3_2_20. 有如下Test类的定义，则下列有关该类对象定义的语句，不正确的有（  ）。

class Test

{

public:

    Test (int i){}

    Test (int i, int j, int k){}

};

A．Test a;

B．Test a1(1);

C．Test a2(1,2);

D．Test a3(1,2,3);

三、编程题（共2题，每题20分，总分40分）

CP3_2_21.

一渔夫打鱼三天，然后晒网两天，一直这样循环作业，打鱼一天可以赚300元，晒网一天需要花费30元，编写程序，输入一个正整数代表渔夫需要赚的钱数，输出渔夫为赚够这些钱需要作业的天数。

样例1

输入：1000

输出：6

样例2：

输入：6000

输出：36

CP3_2_22.

小明学习二分查找算法后，想编写一个C++关键字查询程序。首先将学过的15个C++的关键字按升序的顺序存放到二维字符数组中，然后输入要查找的关键字，如果查到则输出该关键字的位置索引；若没有查到则输出-1。

注意：

编程过程中对于程序给定的部分不允许修改，考生仅允许在/****code****/提示行区间内作答。

#include <iostream>

#include <cstring>

using namespace std;

int search(char words[][30], int length, char *key);

int main()

{

    char words[15][30]={"bool","break","case","char","continue",

                           "do", "double", "else", "float", "for","if",

                           "int","long","switch","while"};  

    char key[30];  //要查找的关键字

    cin >> key;    

    int index = search(words, 15, key);//返回待查找关键字的索引，找不到返回-1

    cout << index << endl;

}

int search(char words[][30], int length, char *key)

{

    /************code**********/

     

     

    /************code**********/

}

样例1

输入：float

输出：8

样例2：

输入：floor

输出：-1