2023年12月GESP认证C++七级真题试卷答案解析

2023年GESP12月认证C++七级试卷解析 一、 单选题（每题 2 分，共 30 分） 题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 B D B C D D B C B C D C B D B 1 、定义变量 double x ，如果下 ⾯ 代码输 ⼊ 为 100 ，输出最接近 ( ) 。 A. 0 B. -5 C. -8 D. 8 【答案】 B 【解析】 log10(x) 表示 10 的多少次方是 x ， log2(x) 表示 2 的多少次方是 x ，这里的 x 是输入的 100 ，所以， log10(100)=2 ，又因为 2 6 =64 ，所以 log2(100) 是 6. 多，两者作差，约为 -4. 多，选 B 。 对于下 ⾯ 动态规划 ⽅ 法实现的函数， 以下选项中最适合表达其状态转移函数的为 ( ) 。 A. B. C. D. 【答案】 D 【解析】首先看代码， s 数组是前缀和数组， f 数组是 dp 数组，初始化 f 数组为正无穷，只有 f[i][i]=0 （ 1<=i<=n ）的值为 0 ，接着进行了区间 dp ， i 和 j 分别是区间 dp 的两个端点， k 是枚举的分界点， k 的取值范围是 [i,j) ，所以选项 C 错误，根据第 15 行转移方程，发现后面的 s[j]-s[i-1] 是 a[i]+a[i+1]+…+a[j] 的和，且与 k 无关，可以单独拎出来，所以转移方程为 ，选项 D 正确。选项 A,B 的错误点在于 f(i,j) 的初始值为正无穷，所以 f(i,j) 是不参与转移方程的。 3、下 ⾯ 代码可以 ⽤ 来求最长上升 ⼦ 序列（ LIS ）的长度，如果输 ⼊ 是： 5 1 7 3 5 9 ，则输出是 ( ) 。 A. 9 7 5 1 1 9 B. 1 2 2 3 4 4 C. 1 3 5 7 9 9 D. 1 1 1 1 1 1 【答案】 B 【解析】题目已经提示我们这是在求最长上升子序列， f 数组的含义是以 i 结尾的最长上升子序列长度， ans 是整个序列的最长上升子序列长度，代码中先依次输出了 f[1],f[2],…,f[n], 最后再输出 ans ，接着我们可以进行手算， 1 7 3 5 9 序列的 f 值分别为 1,2,2,3,4,ans=4 ，所以正确答案为 B 。 4 、 C++ 语 ⾔ 中，下列关于关键字 static 的描述不正确的是 ( ) 。   A. 可以修饰类的成员函数。   B. 常量静态成员可以在类外进 ⾏ 初始化。   C. 若 a 是类 A 常量静态成员 ，则  a 的地址都可以访问且唯 ⼀ 。   D. 静态全局对象 ⼀ 定在 main 函数调 ⽤ 前完成初始化 ，执 ⾏ 完  main 函数后被析构。 【答案】 C 【解析】 static 是静态意思，可以修饰成员变量和成员方法， static 修饰成员变量表示该成员变量在内存中只存储一份，可以被共享访问，修改。选项 C 中 a 的地址都可以访问是不对的，所以本题选 C 。 5 、 G 是 ⼀ 个 ⾮ 连通 ⽆ 向图，共有 28 条边，则该图 ⾄ 少有 ( ) 个顶点。 A. 6 B. 7 C. 8 D. 9 【答案】 D 【解析】注意到题目里说的是非连通无向图，那么在同样的点数 n 下，为了有尽量多的边，可以分为两张连通图，一张 n-1 个点的完全图，另一张只有单独一个点，手算后可以发现， 8 个点的完全图有 8*7/2=28 个点，正好满足题目要求，所以总点数为 9 个，选 D 。 6 、哈希表长 31 ，按照下 ⾯ 的程序依次输 ⼊ 4 17 28 30 4 ，则最后的 4 存 ⼊ 哪个位置？  (   ) A. 3 B. 4 C. 5 D. 6 【答案】 D 【解析】题目提示我们这是哈希表，根据代码，发现是按照 %13 进行哈希并且在发生冲突的情况下， 对应放到下一个位置，我们依次计算 17 28 30 4 会放置在什么位置， 17 放置在 4,28 放置在 2,30 本来放置在 4 ，但是发生冲突，最终放置在 5,4 本来放置在 4 ，但是 4 和 5 都被占用了，所以最终放置在 6 ，选 D 。 7 、某 ⼆ 叉树 T 的先序遍历序列为： {A B D F C E G H}  ，中序遍历序列为： {B F D A G E H C}  ，则下列说法中正确的是 ( ) 。 T 的度为 1 B. T 的 ⾼ 为 4 C. T 有 4 个叶节点 D. 以上说法都不对 【答案】 B 【解析】先序遍历是根左右，中序遍历是左根右，首先可以根据先序遍历和中序遍历画出完整的树，如下图： 所以正确答案为 B 。 8、下 ⾯ 代码段可以求两个字符串  s1  和  s2  的最长公共 ⼦ 串（ LCS ） ，下列相关描述不正确的是（  ）。 A. 代码的时间复杂度为 O （ n 2 ） B. 代码的空间复杂度为 O （ n 2 ） C. 空间复杂度已经最优 D. 采用了动态规划求解 【答案】 C 【解析】题目告诉我们代码是在求解最长公共子串，代码中使用了双重 for 循环，且循环范围为 [1~n1] 以及 [1~n2] ，所以选项 A 正确，使用了二维数组 dp ，两维的长度也均为字符串长度，所以选项 B 正确，空间复杂度还可以使用滚动数组进一步优化为 O(n) ，所以选项 C 错误，本题选 C ，选项 D 正确，代码中使用的正是动态规划算法。 9 、图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？ (  ) A. 双向栈 B. 队列 C. 哈希表 D. 堆 【答案】 B 【解析】图的广度优先搜索是从若干点出发，依次向外进行逐层扩展的算法，使用队列存放待遍历节点，本题选 B 。 10 、对关键字序列 {44 ， 36 ， 23 ， 35 ， 52 ， 73 ， 90 ， 58} 建 ⽴ 哈希表 ，哈希函数为  h(k)=k%7 ，执 ⾏ 下 ⾯ 的 Insert 函数 ，则等概率情况下的平均成功查找长度（即查找成功时的关键字 ⽐ 较次数的均值）为 (