1.
下列关于排序的说法，正确的是( )。
2.
下面的程序属于哪种算法( )。
1 int pos[8];
2 void queen(int n) {
3 for (int i = 0; i < 8; i++) {
4 pos[n] = i;
5 bool attacked = false;
6 for (int j = 0; j < n; j++)
7 if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j]- j) {
8 attacked = true;
9 break;
10 }
11 if (attacked)
12 continue;
13 if (n == 7) {
14 return;
15 } else {
16 queen(n + 1);
17 }
18 }
19 }
3.
下面有关C++类的说法，错误的是（ ）。
4.
一个连通的简单无向图，共有28条边，则该图至少有( )个顶点。
5.
以下哪个方案不能合理解决或缓解哈希表冲突（ ）。
6.
已知一颗二叉树的中序遍历序列为：{C F B A E D G}，后序遍历序列为：{F C B E G D A}，则下列说法中正 确的是( )。
7.
以下关于二叉排序树的说法，正确的是（ ）。
8.
已知x为double类型的变量，且值大于0，则下列表达式的值一定大于0的是( )。
9.
一个简单有向图有10个结点、30条边。再增加多少条边可以成为完全图。（ ）
10.
下列选项中，哪个可能是下图的深度优先遍历序列（ ）。
11.
下面schedule函数的时间复杂度为( )。
1 #include <algorithm>
2 using namespace std;
3 struct activity {
4 int id, start, end;
5 };
6 bool compare(activity a, activity b) {
7 return a.end < b.end;
8 }
9 int schedule(int n, activity * p) {
10 sort(p, p + n, compare);
11 int cnt = 0, end = 0;
12 for (int i = 0; i < n; i++) {
13 if (p[i].start >= end) {
14 end = p[i].end;
15 cnt++;
16 }
17 }
18 return cnt;
19 }
12.
下面search函数的平均时间复杂度为( )。
1 int search(int n, int * p, int target) {
2 int low = 0, high = n;
3 while (low <= high) {
4 int middle = (low + high) / 2;
5 if (target == p[middle]) {
6 return middle;
7 } else if (target > p[middle]) {
8 low = middle + 1;
9 } else {
10 high = middle - 1;
11 }
12 }
13 return -1;
14 }
13.
下面 count_triple 函数的时间复杂度为( )。
1 int count_triple(int n) {
2 int cnt = 0;
3 for (int a = 1; a <= n; a++)
4 for (int b = a; a + b <= n; b++)
5 for (int c = b; a + b + c <= n; c++)
6 if (a * a + b * b == c * c)
7 cnt++;
8 return cnt;
9 }
14.
下面程序的输出为（ ）。
1 #include <iostream>
2 using namespace std;
3 int down(int n) {
4 if (n <= 1)
5 return n;
6 return down(n - 1) + down(n - 2) + down(n - 3);
7 }
8 int main() {
9 cout << down(6) << endl;
10 return 0;
11 }
15.
下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。
1 int weight[4][4] = {
2 {0, 2, 5, 8},
3 {2, 0, 1, 7},
4 {5, 1, 0, 4},
5 {8, 7, 4, 0}};
1.
祖冲之是南北朝时期杰出的数学家、天文学家，其主要贡献在数学、天文历法和机械制造三方面。他首次将 “圆周率”精算到小数第七位，即在3.1415926和3.1415927之间。
2.
C++语言中，表达式 2 ^ 3 的结果类型为 int 、值为 8 。( )
3.
一棵有 个节点的完全二叉树，则树的深度为[log2(N)]+1 。( )
4.
能用动态规划解决的问题，一般也可以用贪心法解决，但动态规划的效率更高。( )
5.
使用 math.h 或 cmath 头文件中的正弦函数，表达式 sin(30) 的结果类型为 double 、值约为 0.5 。( )
6.
要求出简单有向图中从顶点A到顶点B的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适 合。( )
7.
某 N 个表项的哈希表，在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为O(1)，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为O(1) 。( )
8.
动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同。( )
9.
围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。( )
10.
类B继承了抽象类A，但未实现类A中的纯虚函数f，则类B不能直接实例化。( )
1.
试题名称：交流问题
3.1.1 问题描述
来⾃2所学校A校、B校的N名同学相聚在⼀起相互交流 ，⽅便起见 ，我们把这些同学从1⾄N编号 。他们共进⾏了M次交流 ，第i次交流中 ，编号为ui，ui的同学相互探讨了他们感兴趣的话题 ，并结交成为了新的朋友。
由于这次交流会的⽬的是促进两校友谊， 因此只有不同学校的同学之间会交流， 同校同学并不会相互交流。
作为A校顾问 ，你对B校的规模⾮常感兴趣 ，你希望求出B校⾄少有⼏名同学、⾄多有⼏名同学。
3.1.2 输入描述
第⼀⾏两个正整数N, M ，表⽰同学的⼈数 ，交流的次数。
接下来M⾏ ，每⾏两个正整数ui，ui ，表⽰⼀次交流。
题⽬保证输⼊合法， 即交流⼀定是跨校开展的。
3.1.3 输出描述
输出⼀⾏两个整数 ，⽤单个空格隔开 ，分别表⽰B校⾄少有⼏名同学、⾄多有⼏名同学。
3.1.4 特别提醒
在常规程序中 ，输⼊ 、输出时提供提⽰是好习惯 。但在本场考试中， 由于系统限定 ，请不要在输⼊ 、输出中附带任 何提⽰信息。
3.1.5 样例输入 1
3.1.6 样例输出 1
3.1.7 样例输入 2
3.1.8 样例输出 2
3.1.9 数据规模
对于30的测试点 ，保证N≤17 ，M≤50；
对于60的测试点 ，保证N≤500 ，M≤2000；
对于100的测试点 ，保证N≤ 105 ，M≤2×105 。
2.
试题名称：俄罗斯⽅块
3.2.1 题面描述
⼩杨同学⽤不同种类的俄罗斯⽅块填满了⼀个⼤⼩为nxm的⽹格图。
⽹格图由n×m个带颜⾊⽅块构成 。⼩杨同学现在将这个⽹格图交给了你 ，请你计算出⽹格图中俄罗斯⽅块的种类数。
如果两个同⾊⽅块是四连通（即上下左右四个相邻的位置） 的 ，则称两个同⾊⽅块直接连通 ；若两个同⾊⽅块同时 与另⼀个同⾊⽅块直接或间接连通 ，则称两个同⾊⽅块间接连通 。⼀个俄罗斯⽅块由⼀个⽅块和所有与其直接或间 接连通的同⾊⽅块组成 。定义两个俄罗斯⽅块的种类相同当且仅当通过平移其中⼀个俄罗斯⽅块可以和另⼀个俄罗 斯⽅块重合 ；如果两个俄罗斯⽅块颜⾊不同 ，仍然视为同⼀种俄罗斯⽅块。
例如 ，在如下情况中 ，⽅块1和⽅块2是同⼀种俄罗斯⽅块 ，⽽⽅块1和⽅块3不是同⼀种俄罗斯⽅块。
3.2.2 输入格式
第⼀⾏包含两个正整数n ,m ，表⽰⽹格图的⼤⼩ 。
对于之后n⾏ ，第i⾏包含m个正整数ai1,ai2 …, ，aim，表示该行m个方块的颜色。
3.2.3 输出格式
输出⼀个⾮负整数 ，表⽰俄罗斯⽅块的种类数。
3.2.4 样例 1
3.2.5 样例解释
7 种类型的俄罗斯⽅块如下：
3.2.6 数据范围
对于全部数据 ，保证有1≤n, m≤500 ，0≤aij≤5002 。