GESP考察语言为图形化（Scratch）编程、Python编程及C 编程，主要考察学生掌握相关编程知识和操作能力，熟悉编程各项基础知识和理论框架，通过设定不同等级的考试目标，让学生具备编程从简单的程序到复杂程序设计的编程能力，为后期专业化编程学习打下良好基础。
本次为大家带来的是2024年6月认证C 六级真题解析。
GESP2024年6月认证C 六级
一、单选题（每题2分，共30分）
题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
答案 | D | B | A | B | B | A | A | C | A | A | A | D | C | A | C |
1、面向对象的编程思想主要包括（ ）原则。
A.贪心、动态规划、回溯
B.并发、并行、异步
C.递归、循环、分治
D.封装、继承、多态
【答案】D
【考纲知识点】面向对象的思想
【解析】面向对象的编程思想(OOP)主要包括多态、继承和封装原则。
多态：多态允许程序在运行时根据对象的实际类型来选择执行的方法，增加了代码的灵活性和可扩展性。
继承：通过继承，子类可以扩展父类的功能，而不需要重新编写已有的代码，提高了代码的复用性和维护性。
封装：封装隐藏了对象的内部状态，只提供必要的操作接口，保护对象数据不被外部直接访问，同时确保了数据的安全性和完整性。
这些原则共同构成了面向对象编程的核心，使得代码更加模块化、可重用、可维护和可扩展
2、运行下列代码，屏幕上输出（ ）。
A.1 1 1
B.1 2 3
C.1 1 2
D.1 2 2
【答案】B
【考纲知识点】静态变量、类的创建(析构函数)
【解析】构造函数my_class()在对象obj实例化时自动调用，静态局部变量count在程序执行到该对象的声明处时被首次初始化为0，在以后的函数调用不再进行初始化；因此后续调用print_count()方法时，输出count依次自增的结果，程序输出结果为1 2 3，另外析构函数~my_class()会在对象结束调用时做“清理善后” 的工作，即程序结束时，会自动调用三次~my_class()方法，因此最终程序结束时，count的值为0。
3、运行下列代码 ，屏幕上输出（ ）。
A. rectangle area: triangle area:
B. parent class area: parent class area:
C.运⾏时报错
D.编译时报错
【答案】A
【考纲知识点】类的方法调用
【解析】主函数实例化两个对象rectangle rec 和triangle tri，pshape调用rec的area()方法,输出了rectangle area:，之后pshape调用tri的area()方法,输出了triangle area:
4、向一个栈顶为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;
【答案】B
【考纲知识点】栈
【解析】指针之间的赋值:A=B可以理解为A指向B，栈的结构为先进后出，因此S需要作为栈顶存在，hs需要指向S，即hs=s;但是在此之前，需要将S链接到hs，即S的下一个指针指向S，有S->next=hs;
5、在栈数据结构中，元素的添加和删除是按照什么原则进行的？
A.先进先出
B.先进后出
C.最小值先出
D.随机顺序
【答案】B
【考纲知识点】栈
【解析】栈的元素添加原则为先进后出(后进先出)。
6、要实现将一个输入的十进制正整数转化为二进制表示，下面横线上应填入的代码为（ ）。
A. cout << bin.top(); bin.pop();
B. bin.pop(); cout << bin.top();
C. cout << bin.back(); bin.pop();
D. cout << bin.front(); bin.pop();
【答案】B
【考纲知识点】栈
【解析】如果对十进制X进行拆位：每次用取得最低位，同时/10去除最低位，用栈即可得到从个位到高位的各个位，不停弹出即可正常输出十进制的每一位，这个过程可以理解为将十进制转化为二进制，如果将 /10 改为%2 /2，那么这就相当于将十进制转化为二进制。
代码中ten2bin()就是拆分各个位并返回栈st,bin接收值后，按照栈的弹出规则依次输出即可，因此答案选B.
7、下面定义了一个循环队列的类，请补全判断队列是否满的函数，横向上应填写（ ）
A. return (rear 1) % capacity == front;
B. return rear % capacity == front;
C. return rear == front;
D. return (rear 1) == front;
【答案】A
【考纲知识点】循环队列
【解析】判断循环队列是否为满可以让队列的rear指针加1之后对capacity取模结果等于front指针，这时表明队列已满，反之则未满。
8、对“classmycls”使用哈夫曼（Huffman）编码，最少需要（ ）比特。
A
.10
B.20
C.25
D.30
【答案】C
【考纲知识点】哈夫曼编码
【解析】按照哈夫曼编码规则进行建树，如图，按照左0右1的二进制格式编码，可以得到每个字符的编码:
length(C)=length(S)=length(L)=2,length(A)=3,length(Y)=length(M)=4
经过计算可以得到classmycls的总长=2 2 3 2 2 4 4 2 2 2=25。
9、二叉树的（ ）第一个访问的节点是根节点。
A.先序遍历
B.中序遍历
C.后序遍历
D.以上都是
【答案】A
【考纲知识点】二叉树搜索算法
【解析】先序遍历先根再左子树再右子树，中序遍历先左子树再根再右子树，后序遍历先左子树再右子树再根。
10、一棵5层的满二叉树中节点数为（ ）。
A. 31
B. 32
C. 33
D. 16
【答案】A
【考纲知识点】完全二叉树
【解析】一个K层的满二叉树的节点个数为1 2 4 …… 2k-1=2k-1 (等比数列/二进制)。
11、在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和( )。
A.重叠子问题
B.分治法
C.贪心策略
D.回溯算法
【答案】A
【考纲知识点】动态规划
【解析】动态规划的性质主要包括最优子结构、无后效性和有重叠子问题
最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。这意味着问题的最优解可以通过其子问题的最优解来构建。
无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。这一性质确保了动态规划方法的有效性，因为当前阶段的选择不会影响到之前阶段的状态。
有重叠子问题：子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。这一性质是动态规划算法能够通过存储和重用子问题的解来提高效率的关键。
12、青蛙每次能跳1或2步，下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法，错误的是( )。
A.函数jump_recur()采用递归方式。
B.函数jump_dp()采用动态规划方法。
C.当n较大时，函数jump_recur()存在大量重复计算，执行效率低。
D.函数jump_recur()代码量小，执行效率高
【答案】D
【考纲知识点】一维动态规划
【解析】
状态表示:dp[i]表示青蛙到达第i个台阶的跳法。
状态转移方程：第i个台阶由两个状态转移过来①i-2级跳两步②i-1级跳一部，因此状态转移方程为：dp[i]=dp[i-1] dp[i-2]
目标状态:dp[n]
int jump_recur(int n)使用递归方式(斐波那契)，无记忆化，因此复杂度为指数。
int jump_dp(int n)使用动规(递推)方式，复杂度O(n).
13、阅读以下二叉树的广度优先搜索代码:
使用以上算法，在以下这棵树搜索数值20时，可能的输出是( )
A. 5 2 -4 3 17 9
B. -4 2 3 5 9 17
C. 5 2 17 -4 3 9
D.以上都不对
【答案】C
【考纲知识点】二叉树搜索算法(层序遍历)
【解析】该程序使用广搜方式，因此为二叉树层序遍历，答案选C
14、同上题中的二叉树，阅读以下二叉树的深度优先搜索代码
使用以上算法，在二叉树搜索数值20时，可能的输出是( )。
A. 5 2 -4 3 17 9
B. -4 2 3 5 9 17
C. 5 2 17 -4 3 9
D.以上都不对
【答案】A
【考纲知识点】二叉树搜索算法(先序遍历)
【解析】该题目使用栈代替了DFS的递归形式，由输出和push的顺序,可以知道该题目为先序遍历，因此答案为A。
15、在上题的树中搜索数值3时，采用深度优先搜索一共比较的节点数为（ ）
A. 2
B. 3
C. 4
D. 5
【答案】C
【考纲知识点】二叉树搜索算法(先序遍历)
【解析】该二叉树中序遍历有序，同时从构造形态上，为一棵二叉排序树，但是程序并不是按照二叉排序树的规则，题目是先序遍历比较，因此比较的节点依次为:5、2、-4、3,共4次。
如图，比较分支为5-2-3
二、判断题 (每题 2 分,共 20 分)
题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
答案 | √ | √ | × | √ | √ | × | √ | √ | × | × |
1、哈夫曼编码本质上是一种贪心策略。
【答案】正确
【考纲知识点】哈夫曼编码
【解析】哈夫曼编码原理为贪心。
2、创建一个对象时，会自动调用该对象所属类的构造函数。如果没有定义构造函数，编译器会自动生成一个默认的构造函数。
【答案】正确
【考纲知识点】类的创建
【解析】如果一个类中声明成员都没有，我们简称为空类。但是空类中并不是真的什么都没有，即使我们什么都不写，类中也会自动生成6个默认成员函数。
默认成员函数其实就相当于缺省成员函数。如果不写就会编译器默认生成的，写了编译器就不会生成。
3、定义一个类时，必须手动定义一个析构函数，用于释放对象所占用的资源。
【答案】错误
【考纲知识点】类的创建
【解析】由上一题，析构函数编译器会默认生成。
4、C 中类内部可以嵌套定义类。
【答案】正确
【考纲知识点】类的创建
【解析】在C 中，类可以在另一个类的内部定义，这种类被称为嵌套类或内部类。内部类可以访问外部类的所有成员，包括私有成员。
5、000, 001, 011, 010, 110, 111, 101, 100是一组格雷码。
【答案】正确
【考纲知识点】格雷码
【解析】格雷码的特点为：相邻的两个格雷码，只有一位二进制是不同的。且首尾元素也遵循。
6、n个节点的双向循环链表，在其中查找某个节点的平均时间复杂度是O(logn)。
【答案】错误
【考纲知识点】双向循环链表
【解析】考察数据结构中链表的知识。查找数据 平均时间复杂度是O(n).
7、完全二叉树可以用数组存储数据。
【答案】正确
【考纲知识点】完全二叉树
【解析】完全二叉树比较平衡，因此可以从1开始编号作为根，后续每个节点i，其左右两个孩子的下标为2*i,和2*i 1。
8、在C 中，静态成员函数只能访问静态成员变量。
【答案】正确
【考纲知识点】
【解析】在C 中，静态成员函数只能访问静态成员变量。这是因为非静态成员变量属于类的对象，而静态成员变量属于类本身。当一个类的实例没有被创建时，非静态成员变量不存在，所以静态成员函数不能访问它们。
9、在深度优先搜索中，通常使用队列来辅助实现。
【答案】错误
【考纲知识点】深度优先搜索算法(DFS)
【解析】深度优先搜索通常递归方式实现，可以用栈代替递归方式。
10、对0-1背包问题，贪心算法一定能获得最优解。
【答案】错误
【考纲知识点】动态规划(简单背包问题)
【解析】贪心无法得到0-1背包最优解，这是因为部分闲置的空间降低了总体的价值。
三、编程题(每题25分,共50分)
题号 | 1 | 2 |
答案 |
1、计算得分
题面描述
小杨想要计算由m个小写字母组成的字符串的得分。
小杨设置了一个包含n个正整数的计分序列A=[a1,a2,a3……an]，如果字符串的一个子串由k (1 ≤k ≤n) 个abc首尾相接组成，那么能够得到分数ak，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。
例如，假设n=3，字符串dabcabcabcabzabc的所有可能计分方式如下：
• d abc abcabc abz abc或者d abcabc abc abz abc，其中d和abz不计算得分，总得分为a1 a2 a1
• d abc abc abc abz abc，总得分为 a1 a1 a1 a1
• d abcabcabc abz abc，总得分为a3 a1
小杨想知道对于给定的字符串，最大总得分是多少。
输入格式
第一行包含一个正整数n，代表计分序列A的长度。
第二行包含n个正整数，代表计分序列A。
第三行包含一个正整数m，代表字符串的长度。
第四行包含一个由m个小写字母组成的字符串。
输出格式
输出一个整数，代表给定字符串的最大总得分。
样例1
样例解释
最优的计分方式为d abc abc abc abz，总得分为a1 a1 a1，共9分。
数据范围
对于全部数据，保证有1≤n ≤20，1≤m ≤105，1≤a1 ≤1000。
【题目大意】
给定字符串m,将其匹配abc字符串，连续的abc衔接的个数会有不同的得分，求解字符串m的最大的得分。
【考纲知识点】
一维动态规划
【解题思路】
20分思路，考虑到ai>=ai 1,此时将abc单独算是最多的，答案为A[1]*abc的个数。
满分思路
状态表示:DP[i]表示前i个字符组成的最大得分。
状态转移方程:
对第i个字符，有两种情况：①不作为答案的一部分。②作为abc的一部分对答案产生贡献；
对于①:DP[i]=DP[i-1] (也可以理解为将i-1的答案顺延到i)，这保证了答案为DP[m]
对于②:前i个字符中，最后一个位置作为“abc”，可以考虑用连续的j个abc连接更新答案；
此时i-3*j 1 ~i的范围都为连续的j个abc，产生的代价为A[j]
转态转移方程为:
DP[i]=DP[i-3*j] A[j]
①和②构成了答案的所有解
有:DP[i]=max(DP[i-1],max(DP[i-3*j] A[j]); i-3*j 1>=1
参考程序
2、二叉树
题面描述
小杨有一棵包含n个节点的二叉树，且根节点的编号为1。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行q次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。
小杨想知道q次操作全部完成之后每个节点的颜色。
输入格式
第一行一个正整数n，表示二叉树的节点数量。
第二行n-1个正整数,第i(1<-i≤n-1)个数表示编号为i 1的节点的父亲节点编号，数据保证是一棵二叉树。
第三行一个长度为n的01串，从左到右第i（1≤i ≤n）位如果为0，表示编号为i的节点颜色为白色，否则为黑色。第四行一个正整数q，表示操作次数
接下来q行每行一个正整数a_i（1≤ai ≤n ），表示第i次操作选择的节点编号。
输出格式
输出一行一个长度为n的01串，表示 次操作全部完成之后每个节点的颜色。从左到右第i（1≤i ≤n）位如果为0，表示编号为i的节点颜色为白色，否则为黑色。
样例1
样例解释
第一次操作后，节点颜色为：011010
第二次操作后，节点颜色为：000000
第三次操作后，节点颜色为：010000
数据范围
对于全部数据，保证有1≤ n,q ≤ 105。
【题目大意】
给定一棵有向树，同时给定q次操作，每次操作将x所在的子树每个节点颜色取反，问q次操作后的每个节点的颜色，数据范围为105.
【考纲知识点】
树上DFS，树形DP
【解题思路】
①比较朴素的思路为建树，每次操作时执行DFS，将操作的结果处理，最终输出每个节点颜色，极端情况下每次操作遍历整棵树的话，复杂度O(nq)，只能解决40%的数据。
②考虑到程序只要最终结果，因此中间结果没必要完全求得，取反操作的周期为2，具有奇偶性，因此每次操作X时，将X的位置打个标记，表示其将影响X下方的每个节点翻转一次，当所有操作标记完，执行DFS,从root=1出发，统计到达每个节点X时的标记的数量cnt，如果cnt为奇数，则改点颜色取反，否则保持原来颜色。这样只需要O(n q)的复杂度。
参考程序
