GESP-C++八级 题库
下面是使用邻接矩阵实现的Dijkstra算法的核心片段,用于求单源最短路径。在找到当前距离起点最近的顶点u 后,需要更新其邻接点 j 的距离。横线处应填入的代码是( )。
下列程序实现了线性筛法(欧拉筛),用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数只被其最小质因子筛掉,横线处应填入的语句是( )。
对连通无向图执行Kruskal算法。已按边权从小到大依次扫描到某条边e=(u,v)。此时在已经构建的部分MST结构中, (u,v)已在同一连通块内。关于边 的处理,下列说法正确的是( )。
小杨想点一杯奶茶外卖,但还差5元起送。于是,小杨决定点一些小料。可选的小料包括:珍珠1元、椰果2元、奶冻3元、奶盖4元。每种小料最多点1份。请问共有多少种满足起送条件的点小料方案?( )。
16
10
9
7
小杨和小刘是好朋友,她们在逛商场时发现新设置的大头贴自拍机,于是决定一起拍一组照片。一组照片包括4张,这4张照片没有顺序区分。拍每张照片时,可以选择有相框或无相框、两人可以分别选择有头饰或无头饰、 还可以从2种位置(小杨在左,或小刘在左)中选出一种。她们不希望一组照片中出现完全相同的相框、头饰、位置的组合。请问一组照片共有多少种不同的方案?( )。
1820
70
24
16
下列关于C++类的说法,错误的是( )。
派生类对象占用的内存总是不小于基类对象。
派生类可以不实现基类的虚函数。
如果一个类包含纯虚函数,则它不能包含成员变量。
如果一个类包含纯虚函数,则不能用它定义对象。
下列关于树和图的说法,错误的是( )。
每个连通图都存在生成树。
每个存在生成树的有向图,都一定是强连通的。
保留树的所有节点,并把树的每个节点指向其父节点,则可以将树转换为一个有向弱连通图。
保留树的所有节点,并把树的每个节点指向其子节点,则可以将树转换为一个有向无环图。
一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下三个孩子时,实现儿女双全的概率是多少?( )。
1/4
1/2
3/4
7/8
以下关于贪心法和动态规划的说法中,错误的是( )。
动态规划能解决大部分多阶段决策问题。
对特定的问题,贪心法不一定适用。
当特定的问题适用贪心法时,通常比动态规划的时间复杂度更低。
对很多问题,递推实现和递归实现动态规划方法的时间复杂度相当。
下面 merge_sort 函数试图实现归并排序算法,横线处应该填入的是( )。

arr, left, mid
arr, mid, right
arr, left, mid + 1
arr, mid + 1, right
arr, left, mid
arr, mid + 1, right
arr, left, mid + 1
arr, mid + 1, right + 1
下面Prim算法程序中,横线处应该填入的是( )。

graph[u][v] >= 0 && key[v] > graph[u][v]
graph[u][v] <= 0 && key[v] > graph[u][v]
graph[u][v] == 0 && key[v] > graph[u][v]
graph[u][v] != 0 && key[v] > graph[u][v]
下面的欧氏筛法程序中,两个横线处应填入的分别是?( )
第—空应该保证 n * primes[i] 不超过筛法的范围,第二空应该是如果当前 primes[i] 是 n 的最小素因子 则停止循环。(数论:质数筛法)
下面Floyd算法中,横线处应该填入的是?( )
根据 Floyd 算法,如果 i 到 k 加上 k 到 j 的最短路长度小于当前 i 到 j 的最短路长度,则用前者更新后者。 (图论算法: Floyd 算法)
下面最小生成树的Kruskal算法程序中,横线处应该填入的是( )。
Kruskal基于避圈法和贪心思想,先按照边权升序,依次考虑每条边(x,y,z),如果x和y已经处于同一个生成树中,则过滤掉当前的边,否则将x和y的生成树通过z边连接,同时用并查集维护x和y(联接x和y的集合),组成更大的生成树。
横线处为判断x和y是否处于同一个集合,不是则链接,并更新最小生成树的边权和。答案选C。
下面Prim算法程序中,横线处应该填入的是( )。
最小生成树的Prim算法思想:选择圈内的一个点x(一开始随便选一个点作为x),遍历x的所有出边y,从中选取一个边权z最小的y,该(x,y,z)一定是最小生成树的生成边(因为最小生成树的点之间相互连通),程序中key数组就是用来记录过程中每个节点距离圈的距离的最小值,parent数组是记录节点和边权依次加入圈的具体路径(最终形成一棵生成树),横线处是比较圈外距离u最小的边权v,因此答案选D。
下列Dijkstra算法中,横线处应该填入的是( )。
朴素dijkstra算法,在非负权图中,用cheak[]标记已经求得最短路的点(因为已经求得,所以后续不会再更新),每次选择距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx,由非负权图的原因,该节点minxj将加入已经求得最短路的点的集合,同时用minx尝试是否能更新S到其他待球节点的最短路。横线处就是求解距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx的,因此选B。
