首页 › 题库 › GESP编程能力等级认证 › GESP-C++八级

GESP-C++八级 题库

共 270 道题 ,第 8 / 14 页 · 按题型筛选,点「查看答案」核对解析
141 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

在一个有向带权图中,使用Dijkstra算法求单源最短路时,若使用优先队列(小根堆)优化,其时间复杂度为 ( )。

A
B
C
D
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
142 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

对于含n个顶点( n>=2)的连通加权有向图,若图中不存在负权环,则任意两点之间的最短路径(简单路径)最多包含( )条边。

A
n
B
n-1
C
n+1
D
无法确定,取决于图的具体边数
答案与解析
正确答案:B
在含 n 个顶点的连通加权有向图中,若不存在负权环,则任意两点间的最短路径必为简单路径。简单路径的定义是不重复经过任何顶点的路径。路径中每条边连接两个不同顶点,因此路径上最多可经过 n 个顶点。若起点为 u,终点为 v,且路径经过所有顶点,则路径中最多包含 n-1 条边,因为从第一个顶点到第 n 个顶点需要 n-1 次转移。若路径包含 n 或更多条边,则至少有一个顶点被重复访问,违背简单路径的定义。因此,最短路径所含边数不可能超过 n-1 条。
题目详情
143 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

在使用Floyd算法求任意两点间最短路径时,时间复杂度为。若在某次算法执行前,已经用 Dijkstra 算 法正确求出了所有点对的最短路并存入了 dist 数组。如果此时继续对该 dist 数组执行一次完整的 Floyd 算法过程 (无任何提前终止),执行完毕后 dist 数组内的值( )。

A
会发生改变,因为 Floyd 又做了一次松弛
B
不会发生改变
C
可能变大,因为未针对已有最短路优化
D
可能在某些负权图中陷入死循环
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
144 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

关于图论中的最短路径算法,下列说法中严格正确的是( )。

A
Dijkstra 算法能够高效处理包含负权边的有向图。
B
Floyd 算法可以求出任意两点间的最短路径,且允许图中存在负权边(但不能有负权环)。
C
单源最短路径算法无法用于无向图,无向图只能通过 BFS 求解。
D
Dijkstra 算法的每一步必定从当前未访问的节点中,选取距离起始点最远的节点进行松弛操作。
答案与解析
正确答案:B
Dijkstra算法基于贪心策略,每次选择当前距离源点最近的未访问节点进行扩展,仅适用于非负权边图。Floyd算法通过动态规划计算所有顶点对之间的最短路径,可处理负权边但要求图中无负权环。单源最短路径算法适用于有向与无向图,无向图中边可视为双向有向边,BFS仅适用于无权图或权值相等的图。Dijkstra算法每步选取距离起始点最近的未访问节点,而非最远节点,松弛操作更新邻接节点的最短距离估计值。
题目详情
145 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

有6个人排成一排照相,其中甲、乙两人必须相邻,且丙不能站在排头的不同排法有( )种。

A
120
B
144
C
192
D
240
答案与解析
正确答案:C
将甲、乙视为一个整体单元,该单元内部有2种排列方式。将此单元与其余4人(共5个元素)进行全排列,得到所有甲、乙相邻的排列数。在这些排列中,统计丙位于排头的情况:此时排头为丙,剩余4个元素(含甲乙单元)在后4位排列。从总的甲乙相邻排列数中,减去丙在排头且甲乙相邻的排列数,即得满足条件的排法总数。计算过程需分别考虑单元排列、整体排列与限制位置的排除。
题目详情
146 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

下列代码试图实现Floyd算法求所有点对之间的最短路径,横线处应填入( )。

void floyd(int n, int dist[][MAXN]) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (___________) // 在此处填入选项
                    dist[i][j] = dist[i][k] + dist[k][j];
}
A
dist[i][k] + dist[k][j] < dist[i][j]
B
dist[i][k] != INF && dist[k][j] != INF
C
dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]
D
dist[i][j] == INF
答案与解析
正确答案:C
Floyd算法通过动态规划更新任意两点间的最短路径。外层循环遍历中间点k,内层双循环遍历起点i和终点j。核心操作是比较经过中间点k的路径是否比当前记录的路径更短。更新条件依赖于从i到k和从k到j的路径存在且其距离之和小于当前i到j的距离。因此需判断dist[i][k]与dist[k][j]均不为无穷大,并计算二者之和作为候选值参与比较。算法本质是在三重循环中持续优化路径估计值。
题目详情
147 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

用数字 0、1、2、3、4 组成无重复数字的五位偶数,共有( )个。

A
48
B
60
C
72
D
96
答案与解析
正确答案:B
确定五位偶数的个位只能是0、2、4中的一个。分情况讨论:当个位为0时,其余四位从1、2、3、4中任取四个全排列;当个位为2或4时,需排除万位为0的情况。先确定个位选择,再安排万位(不能为0),最后安排中间三位。每种个位情况下,计算有效排列数并求和。所有数字不重复使用,每一位的选取依赖于前几位的选择限制,需按位置逐步分析可选数字个数。
题目详情
148 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

在一个无向带权图中,若使用 Prim 算法从顶点 0 开始构造最小生成树(边权均为正整数,且 graph[u][v] == 0 表示无边),下列代码中横线处应填入( )。

int prim(vector<vector<int>>& graph, int n) {
    vector<bool> inMST(n, false);
    vector<int> minEdge(n, INT_MAX);
    minEdge[0] = 0;
    int result = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++)
            if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))
                u = j;
        inMST[u] = true;
        result += minEdge[u];
        for (int v = 0; v < n; v++)
            if (___________) // 在此处填入选项
                minEdge[v] = graph[u][v];
    }
    return result;
}


A
graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v]
B
!inMST[v] && graph[u][v] < minEdge[v]
C
graph[u][v] > 0 && !inMST[v]
D
!inMST[v] && minEdge[v] > 0
答案与解析
正确答案:A
Prim算法从顶点0开始,维护一个集合inMST表示已在生成树中的顶点,minEdge数组记录各顶点到生成树的最小边权。每轮选择未加入生成树且minEdge值最小的顶点u,将其加入生成树,并更新所有与其邻接且未加入生成树的顶点v:若边(u,v)存在且其权值小于当前minEdge[v],则用该权值更新minEdge[v]。图中graph[u][v]为0表示无边,因此需判断graph[u][v] > 0。更新条件需确保v不在生成树中且新边权有效且更小。
题目详情
149 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

已知三个点在平面直角坐标系中的坐标。下列 C++ 表达式中,在精度误差范围1e-8内能正确计算判断这三个点是三点共线的表达式是( )。

A
(x2-x1)/(y2-y1) == (x3-x1)/(y3-y1)
B
(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) == 0
C
fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)) < 1e-8
D
fabs((x2-x1)/(y2-y1)-(x3-x1)/(y3-y1)) < 1e-8
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
150 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

在64位操作系统下(LP64 / LLP64 模型),下面代码的输出结果是()。

#include <iostream>
using namespace std;

int main() {
    int a[4] = {1, 2, 3, 4};
    int (*p)[4] = &a;
    int *q = a;

    cout << sizeof(a) << " ";
    cout << sizeof(p) << " ";
    cout << sizeof(p + 1) << " ";
    cout << sizeof(q + 1) << " ";
    cout << (p + 1) - p << " ";
    cout << (q + 1) - q << endl;
}


A
16 8 8 8 1 1
B
16 8 16 8 1 1
C
16 8 8 4 4 1
D
16 8 8 8 4 1
答案与解析
正确答案:A
首先确定各数据类型的大小:int类型在64位系统下占4字节;数组a有4个int元素,故整个数组占用16字节。p是指向长度为4的int数组的指针,其本身为指针,在64位系统下占8字节。q是int指针,同样占8字节。&a表示整个数组的地址,其类型为int(*)[4],与p一致。计算sizeof(a)时,返回整个数组占用的字节数。计算sizeof(p)、sizeof(q)时,返回指针本身的大小。对p和q进行解引用操作后,分别得到数组首地址对应的值或首个元素的值。通过逐项分析每个表达式的类型和内存布局,可推导出各输出项的具体数值。
题目详情
151 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

若一项任务可用两种互斥方案完成:方案A有m种做法,方案B有n种做法,则总做法数为m+n。

A
对
B
错
答案与解析
正确答案:对
分析任务完成方式的互斥性,确认方案A与方案B之间无重叠做法。统计方案A所含的m种做法数量,独立统计方案B所含的n种做法数量。根据加法原理,当两类方法不可同时采用且覆盖全部可能路径时,总方法数为两者之和。验证m与n是否分别对应各自方案下的独立选择项,确保无共同实现路径存在于两方案之间。
题目详情
152 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

在C++语言中,引用一旦被初始化,就不能再改为引用另一个变量。

A
对
B
错
答案与解析
正确答案:对
分析C++中引用的绑定机制,观察引用在初始化时与变量建立的关联方式,考察该关联是否允许后续重新绑定到其他变量。检查语言标准对引用生命周期内所绑定对象的唯一性约束,确认是否存在语法或语义层面的支持以改变引用的目标。
题目详情
153 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

快速排序和归并排序的平均时间复杂度都是O(n log n),但快速排序是不稳定的排序算法,归并排序是稳定的排序算法。

A
对
B
错
答案与解析
正确答案:对
比较快速排序与归并排序的时间复杂度机制,分析两者在元素交换过程中的相对位置保持特性。快速排序通过基准元素划分区间并递归排序,元素可能在不同递归层中跨区间交换,导致相同值的相对顺序改变。归并排序将数组分割至最小单位后逐层合并,在合并过程中相同值按原序列顺序依次选入结果,维持了相等元素的原有次序。两种算法的平均时间复杂度均由分治策略的递归深度与每层处理规模决定,表现为O(n log n)。
题目详情
154 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

使用 math.h 或 cmath 头文件中的函数,表达式 sqrt(4) 的结果类型为 double 。

A
对
B
错
答案与解析
正确答案:对
分析表达式 sqrt(4) 的类型需考察 sqrt 函数在 math.h 或 cmath 中的声明。该函数被重载为多个版本,参数和返回类型与浮点类型相关。当传入整型常量 4 时,会触发隐式类型转换,将 int 提升为 double 调用对应重载版本。C++ 标准库中 sqrt 接受 float、double 或 long double 并返回对应类型,无整型版本。因此调用 sqrt(4) 实际执行的是 sqrt(double),结果类型由函数签名决定。
题目详情
155 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 3.1 杨辉三角定义

在杨辉三角形中,第n行(从0开始计数,即第n+1 行有n+1个数)的所有数字之和等于2^n。

A
对
B
错
答案与解析
正确答案:对
分析杨辉三角形的构造规律,每一行的数值由上一行相邻两数相加得到。观察第n行数字之和的生成方式,结合二项式展开系数的性质,将该行所有元素求和转化为二项式系数之和的形式。利用组合恒等式,验证该和是否符合2^n的数学表达结构。通过数学归纳法或直接组合解释,推导行和与幂次之间的关系。
题目详情
156 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 8.1 算法优化方法

使用二叉堆优化的Dijkstra最短路算法,在某些特殊情况下时间复杂度不如朴素实现的O(V^2)。

A
对
B
错
答案与解析
正确答案:对
分析图的顶点数V与边数E的数量级关系;考察二叉堆优化Dijkstra中每次边松弛操作引起的堆操作次数与复杂度;计算二叉堆版本总时间复杂度O((V + E) log V);对比稠密图中E接近V^2时该表达式的增长趋势;比较朴素算法在所有情况下均保持O(V^2)的时间复杂度;考虑当E足够大时,(V + E) log V可能超过V^2;识别图结构中边密度对两种实现方式效率的影响机制。
题目详情
157 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

n个不同元素依次入栈的出栈序列数与将n个不同元素划分成若干非空子集的方案数相等。

A
对
B
错
答案与解析
正确答案:错
分析n个不同元素依次入栈的出栈序列总数,该数值由卡特兰数公式C_n = (2n)! / ((n+1)! * n!) 给出。计算将n个不同元素划分为若干非空子集的方案总数,该数值由贝尔数B_n给出。比较卡特兰数列与贝尔数列在相同n值下的数值关系。考察两个数列的生成机制:卡特兰数描述的是受栈操作约束的排列模式,贝尔数描述的是集合划分的组合方式。分别列出小规模n(如n=1,2,3)时两个数列的具体数值并进行对应比较。观察两者递推公式的结构差异,卡特兰数满足C_n = Σ_{i=0}^{n-1} C_i * C_{n-1-i},贝尔数满足B_n = Σ_{k=0}^{n-1} C(n-1,k) * B_k。
题目详情
158 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 7.1 时间复杂度

快速排序在最坏情况下的时间复杂度为O(n log n),可以通过随机化选择基准值(pivot)的方法完全避免退化。

A
对
B
错
答案与解析
正确答案:错
快速排序的时间复杂度取决于递归划分的平衡性。每次划分由基准值的选择决定,若基准值始终为最大或最小元素,将导致每层仅减少一个元素,形成n层递归,每层处理n、n-1、…个元素,时间复杂度为O(n²)。随机化选择基准值可改变划分结果的概率分布,使最坏情况发生的概率降低,但无法排除所有非均衡划分的可能性。因此,随机化影响划分的期望平衡性,不保证每次递归深度为O(log n)。算法复杂度分析包含最坏、平均与最好情况,随机化改变的是期望性能而非最坏情况的理论上界。
题目详情
159 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

在C++语言中,一个类可以拥有多个构造函数,也可以拥有多个析构函数。

A
对
B
错
答案与解析
正确答案:错
分析类的特殊成员函数定义规则,明确构造函数的重载机制与析构函数的唯一性约束。考察多个构造函数存在的语法支持条件,以及析构函数在类中可出现的次数限制。检查C++标准对构造函数和析构函数的数量规定,确认是否允许同时存在多个析构函数。
题目详情
160 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 8.1 算法优化方法

求两个序列的最长公共子序列(LCS)时,使用滚动数组优化空间后,仍然可以还原出具体的LCS序列。

A
对
B
错
答案与解析
正确答案:错
使用动态规划求解最长公共子序列时,状态转移基于前一行或当前行的值更新。滚动数组通过只保存必要行(如当前行和上一行)来减少空间占用。还原具体LCS序列需回溯路径,可在计算过程中记录决策位置或利用原序列与滚动数组状态逆推匹配点。匹配字符的位置可通过比较当前状态与前一状态差异确定,逐步向前追踪至序列起始。此过程不依赖完整二维表,仅需当前维护的压缩状态及原始输入序列即可实现路径重建。
题目详情