试卷总分：100分
选择题 15题 30分
判断题 10题 20分
编程题 2题 50分
下面程序的运行结果为（ ）。
#include <iostream> #include <algorithm> bool check(int n, int a[], int k, int dist) { int cnt = 1; int last = a[0]; for (int i = 1; i < n; i++) { if (a[i] - last >= dist) { cnt++; last = a[i]; } } return cnt >= k; } int solve(int n, int a[], int k) { std::sort(a, a + n); int l = 0; int r = a[n - 1] - a[0]; while (l < r) { int mid = (l + r + 1) / 2; if (check(n, a, k, mid)) l = mid; else r = mid - 1; } return l; } int main() { int a[] = {1, 2, 8, 4, 9}; int n = 5; int k = 3; std::cout << solve(n, a, k) << std::endl; return 0; }
下面程序的时间复杂度是（ ），假设数组 的值域范围是 。
##include <iostream> #include <algorithm> bool check(int n, int a[], int k, int dist) { int cnt = 1; int last = a[0]; for (int i = 1; i < n; i++) { if (a[i] - last >= dist) { cnt++; last = a[i]; } } return cnt >= k; } int solve(int n, int a[], int k) { std::sort(a, a + n); int l = 0; int r = a[n - 1] - a[0]; while (l < r) { int mid = (l + r + 1) / 2; if (check(n, a, k, mid)) l = mid; else r = mid - 1; } return l; } int main() { int a[] = {1, 2, 8, 4, 9}; int n = 5; int k = 3; std::cout << solve(n, a, k) << std::endl; return 0; }
下面哪一个可能是下图的深度优先遍历序列（ ）。
下面这个有向图的强连通分量的个数是（ ）。
在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号
更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。