GESP-C++八级 题库
n个结点的二叉树,执行释放全部结点操作的时间复杂度是( )。
对二叉树执行DFS,在回溯阶段依次释放每个节点,复杂度O(n)。
下面 pailie 函数是一个实现排列的程序,横线处可以填入的是( )。
函数作用:在0n-1的区间,对A[0n-1]的元素进行全排列。
全排列可以这么理解,每个元素都有尝试在开头的机会,之后其他的元素在这个前提之下,继续在该元素后方继续尝试。当然在尝试完成后,还需要将排列还原,方便后续尝试,符合该要求的只有C选项。
下列程序实现了输出杨辉三角形,代码中横线部分应该填入的是( )。
下面最小生成树的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。
下面Floyd算法中,横线处应该填入的是( )。
Floyd算法本质是个DP,或者可以理解为松弛操作:
i和j的最短路如果可以通过中间节点k做更新:
则需要map[i][j]>map[i][k]+map[k][j];选B。
下面程序的 Merge_Sort 函数时间复杂度为( )。
归并排序基于分治
时间复杂度为O(nlogn)。空间复杂度O(n);
GESP活动期间,举办方从获胜者ABCDE五个人中选出三个人排成一队升国旗,其中A不能排在队首,请问有多少种排法?
排列组合问题。A不能排队首,因此第一位有4种选法;第二位不能与第一位相同,因此有4种选法;第三位不能与前两位相同,有3种选法;共计4*4*3=48种。
7进制数235转换成3进制数是( )。
先将235转换成十进制124,然后再转换成3进制即可。
0,1,2,3,4,5这些数字组成一个三位数,请问没有重复数字的情况下,有多少种组法( )。
一共6个数字,百位不能为0,因此有5种可能;然后再选2个数字排列,就是P(5,2),答案是5*P(5,2)=100
有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为( )。
每个顶点每条边都会被访问一次,所有时间复杂度是C。
一对夫妻生男生女的概率相同。已知这对夫妻有两个孩子,其中一个是女孩,另一个是男孩的概率是多少?

概率知识。每次男孩和女孩的概率都是1/2。
从1到2024这2024个数中,共有( )个包含数字6的数。
1位数字,只有1个6。
2位数字,有6的情况是6*,*表示0到9,共10种;*6,*表示1-9(除掉6),共8种,所以两位数有6的共18种。
3位数字,有6的情况,1位数字6,十位补0,*06,*表示1-9(除掉6),有8种;两位数前面加数字1-9(除掉6),(含6),818=144,百位是6的有600-699,共100个数字,总计100+144+8=252种。
同理1000-1999,1位数补成4位数,1006;2位数补成10(含6),3位数前面加1,有1+18+252=271种。
2000-2024有2个含数字6的数字,总数是1+18+252+271+2=544.
以下函数声明,哪个是符合C++语法的?( )。
考察的是二维数组定义的知识。二维数组第二维长度必须确定。
下面有关C++重载的说法,错误的是( )。
不能重载的运算符还是挺多的。“::”、“.”、“?:”等。
小于或等于给定正整数n的数中,与n互质的数的个数,我们称为欧拉函数,记作
。下面说法错误的是( )。
两个不同的质数是互质数。