一、单选题
1、下列关于排序的说法，正确的是( )。
A 冒泡排序是最快的排序算法之一。
B 快速排序通常是不稳定的。
C 最差情况， 个元素做归并排序的时间复杂度为 。
D 以上均不正确。
2、下面的程序属于哪种算法( )。
int pos[8];
void queen(int n) {
for (int i = 0; i < 8; i++) {
pos[n] = i;
bool attacked = false;
for (int j = 0; j < n; j++)
if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j]- j) {
attacked = true;
break;
}
if (attacked)
continue;
if (n == 7) {
return;
} else {
queen(n + 1);
}
}
}A 贪心算法
B 动态规划
C 深度优先搜索
D 广度优先搜索
3、下面有关C++类的说法，错误的是（ ）。
A、
C++类对象销毁时，会执行析构函数。
B、 C++类可以通过定义构造函数实现自动类型转换。
C、
C++类可以通过重载 [] 运算符实现通过给定下标访问数组成员的元素。
D、
C++类可以包含任意类型的成员变量。
4、一个连通的简单无向图，共有28条边，则该图至少有( )个顶点。
A 6
B 7
C 8
D 9
5、以下哪个方案不能合理解决或缓解哈希表冲突（ ）。
A、
在每个哈希表项处，使用单链表管理该表项的冲突元素。
B、
建立额外的单链表，用来管理所有发生冲突的元素。
C、
使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。
D、 用新元素覆盖发生冲突的哈希表项。
6、已知一颗二叉树的中序遍历序列为：{C F B A E D G}，后序遍历序列为：{F C B E G D A}，则下列说法中正确的是( )。
A、
该树是平衡二叉树。
B、
该树的高为4。
C、
该树有4个叶节点。
D、 以上说法都不对。
7、以下关于二叉排序树的说法，正确的是（ ）。
A、 二叉排序树的中序遍历序列一定是有序的。
B、
在含 n 个节点的二叉排序树中查找元素，最差情况的时间复杂度为O(log(n))。
C、
二叉排序树一定是二叉平衡树。
D、
以上说法都不对。
8、已知 x 为 double 类型的变量，且值大于0，则下列表达式的值一定大于0的是( )。
A、
sin(x) / x
B、 exp(x) - x
C、
log(x) - x
D、
x * x - x
9、一个简单有向图有10个结点、30条边。再增加多少条边可以成为完全图。（ ）
A、
60
B、
70
C、
15
D、 20
10、下列选项中，哪个可能是下图的深度优先遍历序列（ ）。
A 8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9
B 7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10。
C 8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7
D 7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6。
11、下面 schedule 函数的时间复杂度为( )。
#include <algorithm>
using namespace std;
struct activity {
int id, start, end;
};
bool compare(activity a, activity b) {
return a.end < b.end;
}
int schedule(int n, activity * p) {
sort(p, p + n, compare);
int cnt = 0, end = 0;
for (int i = 0; i < n; i++) {
if (p[i].start >= end) {
end = p[i].end;
cnt++;
}
}
return cnt;
}A O(n)
B O(log(n))
C O(nlog(n))
D O(n2)
12、下面 search 函数的平均时间复杂度为( )。
int search(int n, int * p, int target) {
int low = 0, high = n;
while (low <= high) {
int middle = (low + high) / 2;
if (target == p[middle]) {
return middle;
} else if (target > p[middle]) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return -1;
}A O(n)
B O(log(n))
C O(1)
D 可能无法返回
13、下面 count_triple 函数的时间复杂度为( )。
nt count_triple(int n) {
int cnt = 0;
for (int a = 1; a <= n; a++)
for (int b = a; a + b <= n; b++)
for (int c = b; a + b + c <= n; c++)
if (a * a + b * b == c * c)
cnt++;
return cnt;
}A O(N)
B O(N2)
C O(N3)
D O(N4)
14、下面程序的输出为（ ）。
#include <iostream>
using namespace std;
int down(int n) {
if (n <= 1)
return n;
return down(n - 1) + down(n - 2) + down(n - 3);
}
int main() {
cout << down(6) << endl;
return 0;
}A 6
B 13
C、
20
D、 无法正常结束。
15、下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）
int weight[4][4] = {
{0, 2, 5, 8},
{2, 0, 1, 7},
{5, 1, 0, 4},
{8, 7, 4, 0}};A 6
B 7
C 8
D 9
二、判断题
16、祖冲之是南北朝时期杰出的数学家、天文学家，其主要贡献在数学、天文历法和机械制造三方面。他首次将“圆周率”精算到小数第七位，即在3.1415926和3.1415927之间。( )
A 正确
B 错误
17、C++语言中，表达式 2 ^ 3 的结果类型为 int 、值为 8 。( )
A 正确
B 错误
18、一棵有 个节点的完全二叉树，则树的深度为[log2(N)]+1。( )
A 正确
B 错误
19、能用动态规划解决的问题，一般也可以用贪心法解决，但动态规划的效率更高。( )
A 正确
B 错误
20、使用 math.h 或 cmath 头文件中的正弦函数，表达式 sin(30) 的结果类型为 double 、值约为 0.5 。( )
A 正确
B 错误
21、要求出简单有向图中从顶点 A 到顶点 B 的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适合。( )
A 正确
B 错误
22、某 N 个表项的哈希表，在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为O(1)，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为O(1)。( )
A 正确
B 错误
23、动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同。( )
A 正确
B 错误
24、围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。( )
A 正确
B 错误
25、类 B 继承了抽象类 A ，但未实现类 A 中的纯虚函数 f ，则类 B 不能直接实例化。( )
A 正确
B 错误
三、实操题
26、交流问题
问题描述
来自2所学校A校、B校的N名同学相聚在一起相互交流，方便起见，我们把这些同学从1至N编号。他们共进行了M次交流，第i次交流中，编号为ui,vi的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。
由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流，同校同学并不会相互交流。
作为 A 校顾问，你对 B 校的规模非常感兴趣，你希望求出 B 校至少有几名同学、至多有几名同学。
输入描述
第一行两个正整数N,M，表示同学的人数，交流的次数。
接下来M行，每行两个正整数ui,vi，表示一次交流。
题目保证输入合法，即交流一定是跨校开展的。
输出描述
输出一行两个整数，用单个空格隔开，分别表示 B 校至少有几名同学、至多有几名同学。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
4 3 1 2 2 3 4 2
样例输出 1
1 3
样例输入 2
7 5 1 2 2 3 4 2 5 6 6 7
样例输出 2
2 5
数据规模
对于30的测试点，保证N≤17，M≤50；
对于60的测试点，保证N≤500，M≤2000；
对于100的测试点，保证N≤105，M≤2×105。
参考答案：对于样例输入1，输出为1 3。对于样例输入2，输出为2 5。
27、俄罗斯方块
题面描述
小杨同学用不同种类的俄罗斯方块填满了一个大小为n×m的网格图。
网格图由n×m个带颜色方块构成。小杨同学现在将这个网格图交给了你，请你计算出网格图中俄罗斯方块的种类数。
如果两个同色方块是四连通（即上下左右四个相邻的位置）的，则称两个同色方块直接连通；若两个同色方块同时与另一个同色方块直接或间接连通，则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连通的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合；如果两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块。
例如，在如下情况中，方块1和方块2是同一种俄罗斯方块，而方块1和方块3不是同一种俄罗斯方块。
输入格式
第一行包含两个正整数n,m，表示网格图的大小。
对于之后n行，第i行包含m个正整数ai1,ai2,...,aim,表示该行m个方块的颜色。
输出格式
输出一个非负整数，表示俄罗斯方块的种类数。
样例输入
5 6 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 6 6 7 7 8 6 6 7 7 8 8
样例输出
7
样例解释
数据范围
参考答案：首先，我们需要对输入的网格图进行处理，将每个方块与其直接或间接连通的同色方块组成一个俄罗斯方块。然后，我们可以使用并查集（Union Find）算法来合并相同种类的俄罗斯方块。最后，返回并查集中集合的数量，即为俄罗斯方块的种类数。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
