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
函数 ,则等概率情况下的平均成功查找长度(即查找成功时的关键字
⽐
较次数的均值)为
(
2023年GESP12月认证C++七级试卷解析,2023年12月GESP认证C++七级真题试卷答案解析