GESP 2024年6月_C++六级试卷

从PDF导入：GESP 2024年6月_C++六级试卷

C++ 180分钟 总分 100.0 27 题
试卷题目预览
第1题 中级 2.0分 单选
面向对象的编程思想主要包括（ ）原则。
A. 贪心、动态规划、回溯
B. 并发、并行、异步
C. 递归、循环、分治
D. 封装、继承、多态
第2题 中级 2.0分 单选
运行下列代码，屏幕上输出（ ）。

A. 1 1 1
B. 1 2 3
C. 1 1 2
D. 1 2 2
第3题 中级 2.0分 单选
运行下列代码，屏幕上输出（ ）。

A. rectangle area: triangle area:
B. parent class area: parent class area:
C. 运行时报错
D. 编译时报错
第4题 中级 2.0分 单选
向一个栈顶为hs的链式栈中插入一个指针为s的结点时，应执行（ ）。
A. hs->next = s;
B. s->next = hs; hs = s;
C. s->next = hs->next; hs->next = s;
D. s->next = hs; hs = hs->next;
第5题 中级 2.0分 单选
在栈数据结构中，元素的添加和删除是按照什么原则进行的？
A. 先进先出
B. 先进后出
C. 最小值先出
D. 随机顺序
第6题 中级 2.0分 单选
要实现将一个输入的十进制正整数转化为二进制表示，下面横线上应填入的代码为（ ）。

A. cout << bin.top(); bin.pop();
B. bin.pop(); cout << bin.top();
C. cout << bin.back(); bin.pop();
D. cout << bin.front(); bin.pop();
第7题 中级 2.0分 单选
下面定义了一个循环队列的类，请补全判断队列是否满的函数，横线上应填写（ ）。

A. return (rear + 1) % capacity == front;
B. return rear % capacity == front;
C. return rear == front;
D. return (rear + 1) == front;
第8题 中级 2.0分 单选
对"classmycls"使用哈夫曼（Huffman）编码，最少需要（ ）比特。
A. 10
B. 20
C. 25
D. 30
第9题 中级 2.0分 单选
二叉树的（ ）第一个访问的节点是根节点。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 以上都是
第10题 中级 2.0分 单选
一棵5层的满二叉树中节点数为（ ）。
A. 31
B. 32
C. 33
D. 16
第11题 中级 2.0分 单选
在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。
A. 重叠子问题
B. 分治法
C. 贪心策略
D. 回溯算法
第12题 中级 2.0分 单选
青蛙每次能跳1或2步，下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法，错误的是（ ）。

A. 函数jump_recur()采用递归方式。
B. 函数jump_dp()采用动态规划方法。
C. 当n较大时，函数jump_recur()存在大量重复计算，执行效率低。
D. 函数jump_recur()代码量小，执行效率高。
第13题 中级 2.0分 单选
阅读以下二叉树的广度优先搜索代码，使用以上算法，在以下这棵树搜索数值17时，可能的输出是（ ）。

A. 5 2 -4 3 17 9
B. -4 2 3 5 9 17
C. 5 2 17 -4 3 9
D. 以上都不对
第14题 中级 2.0分 单选
同上题中的二叉树，阅读以下二叉树的深度优先搜索代码，使用以上算法，在二叉树搜索数值9时，可能的输出是（ ）。

A. 5 2 -4 3 17 9
B. -4 2 3 5 9 17
C. 5 2 17 -4 3 9
D. 以上都不对
第15题 中级 2.0分 单选
在上题的树中搜索数值9时，采用深度优先搜索一共比较的节点数为（ ）。
A. 2
B. 3
C. 4
D. 5
第16题 中级 2.0分 判断
哈夫曼编码本质上是一种贪心策略。
T. 正确
F. 错误
第17题 中级 2.0分 判断
创建一个对象时，会自动调用该对象所属类的构造函数。如果没有定义构造函数，编译器会自动生成一个默认的构造函数。
T. 正确
F. 错误
第18题 中级 2.0分 判断
定义一个类时，必须手动定义一个析构函数，用于释放对象所占用的资源。
T. 正确
F. 错误
第19题 中级 2.0分 判断
C++中类内部可以嵌套定义类。
T. 正确
F. 错误
第20题 中级 2.0分 判断
000, 001, 011, 010, 110, 111, 101, 100是一组格雷码。
T. 正确
F. 错误
第21题 中级 2.0分 判断
n个节点的双向循环链表，在其中查找某个节点的平均时间复杂度是O(n)。
T. 正确
F. 错误
第22题 中级 2.0分 判断
完全二叉树可以用数组存储数据。
T. 正确
F. 错误
第23题 中级 2.0分 判断
在C++中，静态成员函数只能访问静态成员变量。
T. 正确
F. 错误
第24题 中级 2.0分 判断
在深度优先搜索中，通常使用队列来辅助实现。
T. 正确
F. 错误
第25题 中级 2.0分 判断
对0-1背包问题，贪心算法一定能获得最优解。
T. 正确
F. 错误
第26题 中级 25.0分 编程
计算得分

小杨想要计算由m个小写字母组成的字符串的得分。 小杨设置了一个包含n个正整数的计分序列a，如果字符串的一个子串由j(j>=1)个abc首尾相接组成，那么能够得到分数a[j]，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。 例如，假设n=3，字符串dabcabcabcabzabc的所有可能计分方式如下： • d+abc+abcabc+abz+abc，总得分为a[1]+a[2]+a[1] • d+abcabc+abc+abz+abc，总得分为a[2]+a[1]+a[1] • d+abc+abc+abc+abz+abc，总得分为a[1]+a[1]+a[1]+a[1] • d+abcabcabc+abz+abc，总得分为a[3]+a[1] 小杨想知道对于给定的字符串，最大总得分是多少。

【输入格式】
第一行包含一个正整数n，代表计分序列a的长度。
第二行包含n个正整数，代表计分序列a。
第三行包含一个正整数m，代表字符串的长度。
第四行包含一个由m个小写字母组成的字符串。
【输出格式】
输出一个整数，代表给定字符串的最大总得分。
【样例输入】

3
3 1 2
13
dabcabcabcabz
【样例输出】

9
【样例解释】

最优的计分方式为d+abc+abc+abc+abz，总得分为3+3+3=9分。
对于全部数据，保证有1≤n≤20，1≤m≤10^5，1≤a[i]≤10^3。
第27题 中级 25.0分 编程
二叉树

小杨有一棵包含n个节点的二叉树，且根节点的编号为1。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行q次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。小杨想知道q次操作全部完成之后每个节点的颜色。

【输入格式】
第一行一个正整数n，表示二叉树的节点数量。
第二行n-1个正整数，第i(2≤i≤n)个数表示编号为i的节点的父亲节点编号，数据保证是一棵二叉树。
第三行一个长度为n的01串，从左到右第i(1≤i≤n)位如果为0，表示编号为i的节点颜色为白色，否则为黑色。
第四行一个正整数q，表示操作次数。
接下来q行每行一个正整数x(1≤x≤n)，表示第i次操作选择的节点编号。
【输出格式】
输出一行一个长度为n的01串，表示q次操作全部完成之后每个节点的颜色。从左到右第i(1≤i≤n)位如果为0，表示编号为i的节点颜色为白色，否则为黑色。
【样例输入】

6
3 1 1 3 4
100101
3
1
3
2
【样例输出】

010000
【样例解释】

第一次操作后，节点颜色为：011010
第二次操作后，节点颜色为：000000
第三次操作后，节点颜色为：010000
对于全部数据，保证有1≤n≤10^5，1≤q≤10^5。
💬