GESP-C++八级 题库
对一个包含V个顶点、E条边的图,执行广度优先搜索,其最优时间复杂度是( )。
O(V)
O(V+E)
O(V^2)
O(E)
以下关于贪心法和动态规划的说法中,错误的是( )。
动态规划能解决大部分多阶段决策问题。
对特定的问题,贪心法不一定适用。
当特定的问题适用贪心法时,通常比动态规划的时间复杂度更低。
对很多问题,递推实现和递归实现动态规划方法的时间复杂度相当。
下列Dijkstra算法,假设图graph中顶点数v、边数e,则程序的时间复杂度为( )。

O(v^2)
O(vlogv+e)
O(v+e)logv
O(v+e)
下面 count_triple 函数的时间复杂度为( )。

O(n^2)
O(n^2logn)
O(n)
O(nlogn)
下面 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]
一间的机房要安排6名同学进行上机考试,座位共2行3列。考虑到在座位上很容易看到同一行的左右两侧的屏幕,安排中间一列的同学做A卷,左右两列的同学做B卷。
请问共有多少种排座位的方案?( )
又到了毕业季,学长学姐们都在开心地拍毕业照。现在有3位学长、3位学姐希望排成一排拍照,要求男生不相邻、女生不相邻。请问共有多少种拍照方案?( )
下列关于C++类和对象的说法,【错误】的是?( )
关于生成树的说法,【错误】的是( )。
一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下两个孩子时,实现儿女双全的概率是多少?( )
已定义变量 double a, b; ,下列哪个表达式可以用来判断一元二次方程 是否有实根?( )
n 个结点的二叉树,执行广度优先搜索的平均时间复杂度是?( )
以下关于动态规划的说法中,【错误】的是?( )
下面的 sum_digit 函数试图求出从 1 到 n (包含 1 和 n )的数中,包含数字 d 的个数。该函数的时间复杂度为?( )
