试卷 2024年3月GESP认证C++编程六级真题试卷
2024年3月GESP认证C++编程六级真题试卷
选择题
第 1 题    单选题

在构建哈夫曼树时 ,每次应该选择(  ) 合并。

A.

最⼩权值的节点

B.

最⼤权值的节点

C.

随机节点

D.

深度最深的节点

第 2 题    单选题

⾯向对象的编程思想主要包括以下哪些原则  (  )  ?


A.

贪⼼ 、动态规划、 回溯

B.

并发、并⾏ 、异步

C.

递归、循环、分治

D.

封装、继承、多态

第 3 题    单选题

在队列中 ,元素的添加和删除是按照( )原则进⾏的。

A.

先进先出

B.

先进后出

C.

最⼩值先出

D.

随机进出

第 4 题    单选题

给定⼀个简单的类定义如下,( )语句在类的外部正确地创建了⼀个  Circle 对象并调⽤了  getArea 函数?

1 class Circle {
2 private:
3  double radius;
4 public:
5  Circle(double r) : radius(r) {}
6  double getArea() {
7   return 3.14 * radius * radius;
8  }
9 };
A.

Circle c = Circle(5.0); c.getArea(c);

B.

Circle c(5.0); getArea(c);

C.

Circle c = new Circle(5.0); c.getArea();

D.

Circle c(5.0); c.getArea();

第 5 题    单选题

以下代码希望能在⼀棵⼆叉排序树中搜索特定的值 ,请在横线处填⼊(  ) ,使其能正确实现相应功能。

1 TreeNode* search(TreeNode* root, int target) {
2  if (root == NULL || root->val == target) {
3   return root;
4  }
5  if (_______________) {
6   return search(root->left, target);
7  } else {
8   return search(root->right, target);
9  }
10 }
A.
target < root->left
B.
target < root->val
C.
target > root->val
D.
target > root->left
第 6 题    单选题

3 位格雷编码的正确顺序是(  ) 。

A.

000, 001, 010, 011, 100, 101, 110, 111

B.

000, 001, 011, 010, 110, 111, 101, 100

C.

000, 010, 001, 011, 100, 110, 101, 111

D.

000, 010, 110, 100, 111, 101, 011, 001

第 7 题    单选题

以下动态规划算法的含义与⽬的是(  ) 。

1 int function(vector<int>& nums) {
2  int n = nums.size();
3  if (n == 0)
4   return 0;
5  if (n == 1)
6   return nums[0];
7  vector<int> dp(n, 0);
8  dp[0] = nums[0];
9  dp[1] = max(nums[0], nums[1]);
10  for (int i = 2; i < n; ++i) {
11   dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
12  }
13  return dp[n - 1];
14 }
A.

 计算数组 nums 中的所有元素的和

B.

计算数组 nums 中相邻元素的最大和

C.

计算数组 nums 中不相邻元素的最大和

D.

计算数组 nums 中的最小元素

第 8 题    单选题

阅读以下广度优先搜索的代码:

1 void bfs(TreeNode* root) {
2  if (root == NULL) {
3   return;
4  }
5  queue<TreeNode*> q;
6  q.push(root);
7  while (!q.empty()) {
8   TreeNode* current = q.front();
9   q.pop();
10   cout << current->val << " ";
11   if (current->left) {
12    q.push(current->left);
13   }
14   if (current->right) {
15    q.push(current->right);
16   }
17  }
18 }

使用以上算法遍历以下这棵树,可能的输出是( )。

A.

1 2 8 9 4 5 3 6 7 10 11

B.

1 2 3 4 5 6 7 8 9 10 11

C.

1 2 3 8 9 6 4 5 7 10 11

D.

1 2 3 8 9 4 5 6 7 10 11

第 9 题    单选题

给定一个空栈,执行以下操作序列:

操作序列:push(1), push(2), push(3), pop( ), pop( ), push(4), push(5), pop( )

最终栈中的元素是( )。

A.

1, 2

B.

 1, 4, 5

C.

1, 2, 5

D.

1, 4

第 10 题    单选题

⼀个有 124 个叶⼦节点的完全⼆叉树 ,最多有( )个结点。

A.

247

B.

 248

C.

 249

D.

 250

第 11 题    单选题

在求解最优化问题时 ,动态规划常常涉及到两个重要性质, 即最优⼦结构和( ) 。

A.

重叠⼦问题

B.

分治法

C.

贪⼼策略

D.

回溯算法

第 12 题    单选题

若⼀棵⼆叉树的先序遍历为:A, B, D, E, C, F 、 中序遍历为:D, B, E, A, F, C ,它的后序遍历为( ) 。

A.

D, E, B, F, C, A

B.

 E, D, B, F, C, A

C.

D, E, B, C, F, A

D.

E, D, B, C, F, A

第 13 题    单选题

线性筛法与埃⽒筛法相⽐的优势是(  ) 。

A.

更容易实现

B.

更节省内存

C.

更快速

D.

更准确

第 14 题    单选题

以下代码使⽤了辗转相除法求解最⼤公因数 ,请在横线处填⼊(  )  ,使其能正确实现相应功能。

1 int gcd(int a, int b) {
2  while (b != 0) {
3   _________________________                                        
4  }
5  return a;
6 }
A.

int temp = b; b = a / b; a = temp;

B.

int temp = a; a = b / a; b = temp;

C.

int temp = b; b = a % b; a = temp;

D.

b = a % b; a = b;

第 15 题    单选题

下⾯的代码⽚段⽤于反转单链表 ,请进⾏(  ) 修改 ,使其能正确实现相应功能。

1 ListNode* reverseLinked List(ListNode* head) {
2  ListNode* prev = nullptr;
3  ListNode* current = head;
4  while (current != nullptr) {
5   ListNode* next = current->next;
6   current->next = next;
7   prev = current;
8   current = next;
9  }
10  return prev;
11 }
A.

 current->next = next; 应该改为  current->next = prev;

B.

 ListNode* next = current->next; 应该改为  ListNode* next = prev->next;

C.

current != nullptr 应该改为  current->next != nullptr

D.

ListNode* prev = nullptr; 应该改为  ListNode* prev = head;

判断题
第 16 题    判断题

哈夫曼树是一种二叉树。( )

A.
正确
B.
错误
第 17 题    判断题
在动态规划中,状态转移方程的作用是定义状态之间的关系。
A.
正确
B.
错误
第 18 题    判断题

继承是将已有类的属性和方法引入新类的过程。( )

A.
正确
B.
错误
第 19 题    判断题

完全二叉树的任意一层都可以不满。( )

A.
正确
B.
错误
第 20 题    判断题
删除单向链表中的节点,只需知道待删除节点的地址即可,无需访问前一个节点。
A.
正确
B.
错误
第 21 题    判断题
在宽度优先搜索中,通常使用队列来辅助实现。
A.
正确
B.
错误
第 22 题    判断题

哈夫曼编码的主要应用领域是有损数据压缩。( )

A.
正确
B.
错误
第 23 题    判断题
二叉搜索树的查找操作的时间复杂度是O(N) 。
A.
正确
B.
错误
第 24 题    判断题
栈的基本操作包括入栈(push)和出栈(pop)。
A.
正确
B.
错误
第 25 题    判断题
使用哈夫曼编码对一些字符进行编码,如果两个字符的频率差异最大,则它们的编码可能出现相同的前缀。
A.
正确
B.
错误
编程题
第 26 题    问答题

试题名称:游戏

3.1.1 题面描述

你有四个正整数n,a,b,c ,并准备用它们玩一个简单的小游戏。

在一轮游戏操作中,你可以选择将n减去a,或是将n减去b。游戏将会进行多轮操作,直到当n≤c时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同,当且仅当游戏操作轮数不同,或是某一轮游戏操作中,一种操作序列选择将n减去a,而另一种操作序列选择将n减去b。如果a=b,也认为将n减去a与将n减去b是不同的操作。

由于答案可能很⼤,你只需要求出答案对1000000007 取模的结果。

3.1.2 输入格式

一行四个正整数n,a,b,c 。保证1≤a,b,c≤n 。

3.1.3 输出格式

一行一个整数,表示不同的游戏操作序列数量对1000000007取模的结果。

3.1.4 样例1

3.1.5 样例2

3.1.6 样例3

3.1.7 数据范围

对于20的测试点,保证a=b=c=1,n≤30 。

对于40的测试点,保证c=1,n≤103

对于所有测试点,保证1≤n≤2×10

第 27 题    问答题

试题名称:好斗的牛

3.2.1 问题描述

你有 个牛棚,从左到右一字排开。你希望把N头牛安置到牛棚里。麻烦的是,你的牛很好斗,如果他们附近有其他的牛,他们就会不安分地去挑事。其中,第 i头牛的攻击范围是(ai,bi),这意味着,如果他的左边ai个牛棚或右边bi个牛棚里有其他牛,他就会去挑事。

你想留下连续的一段牛棚,并把其他牛棚都卖掉。请问你最少需要留下多少牛棚,才能保证至少存在一种方案能够把所有的N头牛都安置进剩余的牛棚里,且没有牛会挑事?

3.2.2 输入描述

第一行 1 个正整数N 。

接下来一行N个用空格隔开的正整数a1,……,an 。

接下来一行N个用空格隔开的正整数b1,…,bn 

3.2.3 输出描述

输出一行一个整数,表示你最少需要留下多少牛棚。

3.2.4 特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。

3.2.5 样例输入 1

3.2.6 样例输出 1

3.2.7 样例解释 1

你可以留下4个牛棚,并如此安排你的牛:

3.2.8 样例输入 2

3.2.9 样例输出 2

3.2.10 数据规模

对于20的测试点,保证N=2 ;

对于另外20的测试点,保证N=3 ;

对于80的测试点,保证N≤8 ;

对于所有测试点,保证N≤9,ai,bi≤1000 。

答题卡
选择题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
判断题
编程题
26 27
题目总数:27
总分数:100
时间:120分钟