真题解析/GESP9月认证C++五级真题回顾

一、单选题（每题2分，共30分）

1、近年来，线上授课变得普遍，很多有助于改善教学效果的设备也逐渐流行，其中包括⽐较常用的手写板，那么它属于哪类设备？（ ）。

A.输⼊

B.输出

C.控制

D.记录

【答案】A

【考纲知识点】 计算机基础知识

【解析】本题属于考察计算机基础知识知识。手写板是输入信息的设备，选A。

2、如果a和b均为int类型的变量，且b的值不为0，那么下列能正确判断“a是b的3倍”的表达式是（ ）。

A. (a >> 3 == b)

B. (a - b) % 3 == 0

C. (a  / b  == 3)

D. (a ==  3  * b)

【答案】D

【考纲知识点】 运算表达式和位运算

【解析】本题属于考察运算表达式和位运算知识。b不等于0，a是b的3倍。A选项中，a右移3位，相当于除以8；B是取余运算；如果a=7,b=2,a/b的结果也等于3，因为是整型，C选项也不正确；选D。

3、如果变量 a 和 b 分别为 double 类型和 int 类型，则表达式(a = 6，b = 3 * (7 + 8) / 2，b += a) 的计算结果为（ ）。

A.6

B.21

C.28

D.不确定

【答案】C

【考纲知识点】 数据类型和运算表达式

【解析】本题属于考察数据类型、逗号表达式、运算表达式知识。逗号表达式从左到右依次计算每一个表达式，整个逗号表达式的结果是最后一个表达式的计算结果，a=6，b=3*15/2=22,b=6+22=28，选C。

4、有关下⾯C++代码说法错误的是（ ）。

A.sumA() ⽤循环⽅式求从1到N之和，sumB()⽤递归⽅式求从1到N之和。

B.默认情况下，如果输⼊正整数1000，能实现求从1到1000之和。

C.默认情况下，如果输⼊正整数100000，能实现求从1到100000之和。

D.一般说来，sumA()的效率⾼于sumB()。

【答案】C

【考纲知识点】 函数和递归算法

【解析】本题属于考察递归和函数知识。sumA用循环求的是1到n的总和；sumB用递归的方式求1到n的总和。1加到100000的和大于int类型最大值，2147483647，会溢出，选C。

5、下⾯C++代码以递归⽅式实现字符串反序，横线处应填上代码是（ ）。

A. sIn[sIn.length()  -  1]  +  sReverse(sIn.substr(0,  sIn.length()  - 1));

B. sIn[0] + sReverse(sIn.substr(1, sIn.length() - 1));

C. sReverse(sIn.substr(0, sIn.length() - 1)) + sIn[sIn.length() - 1];

D. sReverse(sIn.substr(1, sIn.length() - 1)) + sIn[sIn.length() - 1];

【答案】A

【考纲知识点】 函数和递归算法

【解析】本题属于考察递归和函数知识。要倒序输出字符串，先输出字符串中的最后一个字符，最后一个字符下标是长度-1，然后翻转除了最后一个字符的字符串，这个字符串是从0开始，选sln.length()-1个字符，选A。

6、印度古⽼的汉诺塔传说：创世时有三根⾦刚柱，其中⼀柱从下往上按照⼤⼩顺序摞着64⽚黄⾦圆盘，当圆盘逐⼀从⼀柱借助另外⼀柱全部移动到另外⼀柱时，宇宙毁灭。移动规则：在⼩圆盘上不能放⼤圆盘，在三根柱⼦之间⼀次只能移动⼀个圆盘。下⾯的C++代码以递归⽅式实现汉诺塔，横线处应填⼊代码是（ ）。

A. Hanoi(B,  C,  A,  N  -  2)

B. Hanoi(B,  A,  C,  N  -  1)

C. Hanoi(A,  B,  C,  N  -  2)

D. Hanoi(C,  B,  A,  N  -  1)

【答案】B

【考纲知识点】 函数和递归算法

【解析】本题属于考察递归和函数知识。汉诺塔比较经典的递归问题，第11行代码意味这剩下的N-1快圆盘，现在B柱子上，借助A柱，挪到C柱上，选B。

7、根据下⾯C++代码的注释，两个横线处应分别填⼊（ ）。

A. compare 和isOdd(lstA[i])

B. compare(x1,y1) 和isOdd

C. compare 和isOdd

D. compare(x1,y1) 和isOdd(lstA[i])

【答案】A

【考纲知识点】 函数的调用、值传递

【解析】本题考察的是vector和sort函数的使用。本题中首先创建了一个vector lstA存储整数1~99，然后调用sort函数对lstA进行排序，sort函数排序需要传递三个参数，前两个参数决定了排序范围的起始位置和结束位置，第三个参数是排序规则函数，排序规则函数需要两个参数和一个bool类型的返回值，所以代码1处传递排序规则函数compare，只需要写函数名即可，不需要写成调用的形式，排除选项B和D。接下来的代码是将lstA中的奇数存储到另一个vector lstB中，判断奇数可以使用自定义函数isOdd，代码2处是调用isOdd函数判断当前的lstA[i]是否为奇数，因此需要使用调用函数语法isOdd(IstA[i])，正确答案为A选项。

8、有关下面代码正确的是（ ）。

A.checkNum() 函数定义错误。

B.将isEven作为checkNum()参数将导致错误。

C.执⾏后将输出1。

D.运⾏时触发异常。

【答案】C

【考纲知识点】 函数的定义、调用、值传递

【解析】本题考察函数指针的知识。isEven是一个自定义函数，用于判断为偶数。checkNum也是一个自定义函数，该函数的第一个参数是一个函数指针类型，需要传递一个函数，所传递的这个函数要求返回值为bool，并且有一个int类型参数，isEven函数复合该类型的要求，所以调用checkNum函数时，第一个参数传递函数isEven，第二个参数传递整数10没有错误，执行checkNum函数内部代码Fx(N)，也就是调用函数isEven(10)，整数10是偶数，因此最后调用的结果是1，因此正确答案选C。

9、有关下⾯C++代码正确的是（ ）。

A.checkNum() 函数定义错误。

B.输出⾏A的语句将导致编译错误。

C.输出⾏B的语句将导致编译错误。

D.该代码没有编译错误。

【答案】C

【考纲知识点】函数指针

【解析】本题考察函数指针的知识。checkNum函数的第一个参数需要传递一个返回值为bool、参数为int类型的函数，isEven函数复合该类型的要求，所以调用checkNum函数时，第一个参数传递函数isEven，不会导致编译错误，Square函数的返回值是int类型，不符合cehckNum函数的第一个参数的类型要求，因此调用时传递Square函数会导致编译错误，所以答案为C选项。

10、下⾯代码执⾏后的输出是（ ）。

A.4#3#2#2#4

B.4#3#2#2#1#5

C.4#3#2#1#2#4

D.4#3#2#1#2#5

【答案】D

【考纲知识点】 递归和函数

【解析】本题属于考察递归和函数知识。第13行代码调用jumFloor(4)，首先输出4#，然后返回jumFloor(3)+ jumFloor(2)，jumFloor(3)输出3#再继续递归调用jumFloor(2)+ jumFloor(1)依次输出2#1#并返回3。jumFloor(2)输出2#返回2，所以第13行代码调用之后的返回结果是3+2=5，最后的输出结果就是4#3#2#1#2#5，所以正确答案选D。

11、下⾯代码中的isPrimeA()和isPrimeB()都⽤于判断参数N是否素数，有关其时间复杂度的正确说法是（ ）。

A. isPrimeA() 的最坏时间复杂度是0(N)，isPrimeB()的最坏时间复杂度是0(log N) ，isPrimeB()优于isPrimeA()。

B. isPrimeA() 的最坏时间复杂度是0(N)，isPrimeB()的最坏时间复杂度是0（N^1/2），isPrimeB()优于isPrimeA()。

C. isPrimeA() 的最坏时间复杂度是0（N^1/2），isPrimeB()的最坏时间复杂度是0(N)， isPrimeA()优于isPrimeB()。

D. isPrimeA() 的最坏时间复杂度是0(log N) ，isPrimeB()的最坏时间复杂度是0(N)，isPrimeA()优于isPrimeB()。

【答案】B

【考纲知识点】 时间复杂度

【解析】本题属于考察时间复杂度的相关知识。isPrimeA的最坏时间复杂度是O(N)，isPrimeB的最坏时间复杂度是O()，O()优于O(N)，正确答案B选项。

12、下⾯代码⽤于归并排序，其中merge()函数被调用次数为（ ）。

A. 0

B. 1

C. 6

D. 7

【答案】C

【考纲知识点】 分治算法

【解析】本题考察归并排序的相关知识。listA的长度为7，根据递归返回的条件start ≥ end，merge函数会被调用6次，正确答案C选项。

13、在上题的归并排序算法中，mergeSort(listData, start, middle); 和mergeSort(listData, middle +  1,  end); 涉及到的算法为（ ）。

A.搜索算法

B.分治算法

C.贪⼼算法

D.递推算法

【答案】B

【考纲知识点】

【解析】本题属于考察归并排序的相关知识。归并排序采用的是分治算法思想，正确答案B选项。

14、归并排序算法的基本思想是（ ）。

A.将数组分成两个⼦数组，分别排序后再合并。

B.随机选择⼀个元素作为枢轴，将数组划分为两个部分。

C.从数组的最后⼀个元素开始，依次与前⼀个元素⽐较并交换位置。

D.⽐较相邻的两个元素，如果顺序错误就交换位置。

【答案】A

【考纲知识点】 归并排序算法

【解析】本题属于考察归并排序的相关知识。归并排序基本思想就是将数组分成两个⼦数组，分别排序后再合并，正确答案A选项。

15、有关下⾯代码的说法正确的是（ ）。

A.上述代码构成单向链表。

B.上述代码构成双向链表。

C.上述代码构成循环链表。

D.上述代码构成指针链表。

【答案】C

【考纲知识点】 循环链表

【解析】本题考察链表的相关知识。第15行代码~第17行代码创建了三个链表的节点，第一个节点的next指向第二个节点，第二个节点的next指向第三个节点，第三个节点的next又指向了第一个节点，形成了一个环，所以是循环链表，正确答案C选项。

二、判断题（每题2分，共20分）

1、TCP/IP的传输层的两个不同的协议分别是UDP和TCP。

【答案】正确

【考纲知识点】 计算机网络

【解析】本题是计算机网络的知识，传输层是这2个协议。

2、在特殊情况下流程图中可以出现三角框和圆形框。

【答案】错误

【考纲知识点】 流程图

【解析】本题考察流程图，流程图中没有三角框。

3、找出⾃然数N以内的所有质数，常⽤算法有埃⽒筛法和线性筛法，其中埃⽒筛法效率更⾼。

【答案】错误

【考纲知识点】 线性筛法和埃氏筛法

【解析】本题考察筛选素数的算法，线性筛法是在埃⽒筛法基础的改进，效率更高。

4、在C++中，可以使⽤⼆分法查找链表中的元素。

【答案】错误

【考纲知识点】 二分法和链表

【解析】本题考察二分法和链表的知识点，使用二分法查找元素，元素必须是顺序存储的，链表不是顺序存储数据，因此不能使用二分法。

5、在C++中，通过恰当的实现，可以将链表⾸尾相接，形成循环链表。

【答案】正确

【考纲知识点】 循环链表

【解析】本题考察循环链表的知识点，链表的最后一个节点的next指针指向头结点就能形成循环链表。

6、贪⼼算法的解可能不是最优解。

【答案】正确

【考纲知识点】 贪心算法

【解析】本题考察贪心算法的知识点，贪心算法找到的不一定是最优解。

7、⼀般说来，冒泡排序算法优于归并排序。

【答案】错误

【考纲知识点】 冒泡排序

【解析】本题考察排序算法性能，冒泡时间复杂度为O()，归并排序的时间复杂度为O(NlogN)，因此归并优于冒泡，说法错误。

8、C++语言中的qsort库函数是不稳定排序。

【答案】正确

【考纲知识点】gsort函数

【解析】本题考察qsort函数，qsort函数内部使用的是不稳定的排序算法。

9、质数的判定和筛法的目的并不相同，质数判定旨在判断特定的正整数是否为质数，而质数筛法意在筛选出范围内的所有质数。

【答案】正确

【考纲知识点】 质数的判定和筛选

【解析】本题考察质数的判定和筛选，说法正确。

10、下⾯的C++代码执⾏后将输出0 5 1 6 2 3 4。

【答案】正确

【考纲知识点】sort函数

【解析】本题考察sort函数的排序规则，排序规则函数compareModule5确定的排序规则是根据除5的余数进行升序排序，所以main函数中对0~6范围的整数排序之后的结果就是0516234.

三、编程题（每题25分，共50分）

1、因数分解

问题描述

每个正整数都可以分解成素数的乘积,例如：6= 2×3、20=2²× 5 。

现在,给定⼀个正整数N,请按要求输出它的因数分解式。

输入描述

输⼊第⼀⾏，包含⼀个正整数N。约定2≤N≤10¹²

输出描述

输出⼀行，为N的因数分解式。要求按质因数由⼩到⼤排列，乘号⽤星号*表⽰，且左右各空⼀格。当且仅当⼀个素数出现多次时，将它们合并为指数形式，⽤上箭头^表⽰，且左右不空格。

样例输入1

样例输出1

样例输入2

样例输出2

样例输入3

样例输出3

【题目大意】

输入一个正整数N，按格式输出它的因数分解式。

【考纲知识点】

初等数论，多重循环，算术运算

【解题思路】

每个正整数N的质因数分解形式是唯一的。可以设计一个简单的算法，在2~N范围内按从小到大的顺序枚举每一个整数，如果该整数能整除N，则把该整数就是N的一个 质因数，将它从N中分解出去，循环执行直到N不能被分解为止。再分解过程中按题目要求输出因数分解式。

【参考程序】

2、巧夺大奖

问题描述

⼩明参加了⼀个巧夺⼤奖的游戏节⽬。主持⼈宣布了游戏规则：

游戏分为n个时间段，参加者每个时间段可以选择⼀个⼩游戏；

游戏中共有n个⼩游戏可供选择；

每个⼩游戏有规定的时限和奖励。对于第i个⼩游戏，参加者必须在第T_i 个时间段结束前完成才能得到奖励R_i 。

⼩明发现，这些⼩游戏都很简单，不管选择哪个⼩游戏，他都能在⼀个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个⼩游戏，才能使得总奖励最⾼？

输入描述

输入第一行，包含一个正整数n。n既是游戏时间段的个数，也是小游戏的个数。约定1≤n≤500。

输入第二行，包含n个正整数。第i个正整数为T_i ，即第i个小游戏的完成期限。约定1≤T_i≤n 。

输入第三行，包含n个正整数。第i个正整数为R_i，即第i个小游戏的完成奖励。约定1≤R_i≤1000。

输出描述

输出一行，包含一个正整数C，为最高可获得的奖励。

样例输入1

样例输出1

样例解释1

7个时间段可分别安排完成第4、2、3、1、6、7、5个小游戏，其中第4、2、3、1、7个小游戏在期限内完成。因此，可以获得总计40+60+50+70+10=230的奖励。

【题目大意】

在n个时间段内完成n个小游戏，每个小游戏完成的时间和获得奖励不同，如何选择小游戏使得最后获得奖励最高。

需要注意这句话的理解“对于第i个⼩游戏，参加者必须在第Ti个时间段结束前完成才能得到奖励”，也就是在第1~Ti个时间段范围之内，其中任意一个时间段都可以完成第i个游戏。

【考纲知识点】

贪心算法、数组、sort函数

【解题思路】

本题采用贪心策略，想要获得的最高奖励，优先完成获得奖励多的游戏，同时考虑在完成第i个游戏的时候，第1~Ti个时间段是否被占用，如果都被占用，那么该游戏就不能被完成。解题步骤如下：

1)首先创建结构体game用于保存每个游戏的信息，包括游戏时间期限T和对应的奖励R，并创建games[505]用于保存n个游戏的信息;

2)按题目要求输入数据，并保存在games数组中;

3)根据游戏的奖励，对数组games进行降序排序;

4)遍历排序后的数组games，依次判断第i个游戏是否能完成，如果能完成就累加当前游戏的奖励games[i].R;

5)判断游戏是否能完成可以使用一个数组进行标记，标记第1n个时间段是否被占用，如果第i个游戏的可完成时间段为第1Ti，如果该范围都被占用，则第i个游戏无法完成。

【参考程序】