选择题 共15道

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

判断题 共10道

16 17 18 19 20 21 22 23 24 25

编程题 共2道

26 27
823 202509GESP C++七级试卷-练习
选择题 共15道
01

已知小写字母 b 的ASCII码为98，下列C++代码的输出结果是（ ）。

#include <iostream>
using namespace std;
int main() {
	char a = 'b' + 1;
	cout << a;
	return 0;
}
2分
登录后查看选项
02

已知 a 为 int 类型变量， p 为 int * 类型变量，下列表达式不符合语法的是（ ）。

 2分
登录后查看选项
03

下列关于C++类的说法，错误的是（ ）。

 2分
登录后查看选项
04

已知数组 a 的定义 int a[10] = {-1}; ，下列说法不正确的是（ ）。

 2分
登录后查看选项
05 一棵完全二叉树有165个结点，则叶子结点有多少个？ 2分
登录后查看选项
06

下列关于二叉树的说法，错误的是（ ）。

 2分
登录后查看选项
07

下列关于树和图的说法，错误的是（ ）。

 2分
登录后查看选项
08

对一个包含 个顶点、 条边的图，执行广度优先搜索，其最优时间复杂度是（ ）。

 2分
登录后查看选项
09

以下哪个方案不能合理解决或缓解哈希表冲突（ ）。

 2分
登录后查看选项
10

以下关于贪心法和动态规划的说法中，错误的是（ ）。

 2分
登录后查看选项
11

下面程序的输出为（ ）。

#include <iostream>
using namespace std;
int fib(int n) {
	if (n == 0)
		return 1;
	return fib(n - 1) + fib(n - 2);
}
int main() {
	cout << fib(6) << endl;
	return 0;
}
2分
登录后查看选项
12

下面程序的时间复杂度为（ ）。

int rec_fib[MAX_N];
int fib(int n) {
	if (n <= 1)
		return n;
	if (rec_fib[n] != 0)
		return rec_fib[n];
	return fib(n - 1) + fib(n - 2);
}
2分
登录后查看选项
13

下面 init_sieve 函数的时间复杂度为( )。

int sieve[MAX_N];
void init_sieve(int n) {
	for (int i = 1; i <= n; i++)
		sieve[i] = i;
	for (int i = 2; i <= n; i++)
		for (int j = i; j <= n; j += i)
			sieve[j]--;
}
2分
登录后查看选项
14

下面 count_triple 函数的时间复杂度为( )。

int gcd(int m, int n) {
	if (m == 0) return n;
	return gcd(n % m, m);
}
int count_triple(int n) {
	int cnt = 0;
	for (int v = 1; v * v * 4 <= n; v++)
		for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
			if (gcd(u, v) == 1) {
				int a = u * u - v * v;
				int b = u * v * 2;
				int c = u * u + v * v;
				cnt += n / (a + b + c);
			}
	return cnt;
}
2分
登录后查看选项
15

下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。

 2分
登录后查看选项
判断题 共10道
16

C++语言中，表达式 9 && 12 的结果类型为 int 、值为 8 。

 2分
登录后查看选项
17

C++语言中，在有 int a[10]; 定义的范围内，通过表达式 a[-1] 进行访问将导致编译错误。

 2分
登录后查看选项
18

选择排序一般是不稳定的。

 2分
登录后查看选项
19

C++语言中， float 和 int 类型一般都是 4 字节，因此 float 类型能够表达不同的浮点数值的数量，与int 类型能够表达不同的整数值的数量是相同的。

 2分
登录后查看选项
20

使用 math.h 或 cmath 头文件中的对数函数，表达式 log(256) 的结果类型为 double 、值约为 8.0 。

 2分
登录后查看选项
21

一棵有 个节点的完全二叉树，则树的深度为 log2N + 1。

 2分
登录后查看选项
22

邻接表和邻接矩阵都是图的存储形式。通常，使用邻接表比使用邻接矩阵的时间复杂度更低。

 2分
登录后查看选项
23

C++语言中，类的构造函数可以声明为私有（private）。

 2分
登录后查看选项
24

泛洪算法的递归实现容易造成溢出，因此大的二维地图算法中，一般使用广度优先搜索实现。

 2分
登录后查看选项
25

很多游戏中为玩家设置多种可供学习的技能，要学习特定技能又往往需要先学习1个或以上的前置技能。尽管这样的技能间依赖关系常被玩家称为“技能树”，但它并不一定是树，更可能是有向无环图。

 2分
登录后查看选项
编程题 共2道
26

连通图

时间限制：1.0 s

内存限制：512.0 MB

题目描述

给定一张包含 n 个结点与 m 条边的无向图，结点依次以 1,2,……,n 编号，第 i 条边(1≤i≤m)连接结点 ui 与结点 vi 。如果从一个结点经过若干条边可以到达另一个结点，则称这两个结点是连通的。

你需要向图中加入若干条边，使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。

注意给出的图中可能包含重边与自环。


输入格式

第一行，两个正整数 n,m，表示图的点数与边数。

接下来 m 行，每行两个正整数 ui,vi，表示图中一条连接结点 ui 与结点 vi 的边。

输出格式

输出一行，一个整数，表示使得图中任意两个结点连通所需加入的边的最少数量。


样例

输入样例 1

4 4

1 2

2 3

3 1

1 4

输出样例 1

0

输入样例 2

6 4

1 2

2 3

3 1

6 5

输出样例 2

2


数据范围

对于 40% 的测试点，保证 1≤n≤100，1≤m≤100 。

对于所有测试点，保证 1≤n≤105，1≤m≤105 。

 25分
登录后作答
27

金币收集

时间限制：1.0 s

内存限制：512.0 MB

题目描述

小A正在游玩收集金币的游戏。具体来说，在数轴上将会出现 n 枚金币，其中第 i 枚(1≤i≤n)金币将会在时刻 ti 出现在数轴上坐标为 xi 的位置。小A必须在时刻 ti 恰好位于坐标 xi ，才可以获得第 i 枚金币。

游戏开始时为时刻 0，此时小A的坐标为 0。正常来说，小A可以按游戏机的按键在数轴上左右移动，但不幸的是游戏机的左方向键失灵了。小A每个时刻只能选择保持不动，或是向右移动一个单位。换言之，如果小A 在时刻 t 的坐标为 x，那么他在时刻 t+1 的坐标只能是 x 或是 x+1 二者之一，分别对应保持不动和向右移动。

小A想知道他最多能收集多少枚金币。你能帮他收集最多的金币吗?


输入格式

第一行，一个正整数 n，表示金币的数量。

接下来 行，每行两个正整数 xi ,ti ，分别表示金币出现的坐标与时刻。

输出格式

输出一行，一个整数，表示小 A 最多能收集的金币数量。


样例

输入样例 1

3

1 6

3 7

2 4

输出样例 1

2

输入样例 2

4

1 1

2 2

1 3

2 4

输出样例 2

3


数据范围

对于 40% 的测试点，保证 1≤n≤8。

对于另外 30% 的测试点，保证 1≤n≤100，1≤xi≤100 ，1≤ti≤100 。

对于所有测试点，保证 1≤n≤105，1≤xi≤109 ，1≤ti≤109。

 25分
登录后作答
登录练习