202503 GESP认证 C++编程 八级真题试卷
剩余时间 --:--:--
单选题 共 15 题
1.

国家“以旧换新”政策仍在继续，小杨家决定在家里旧的冰箱、电视、洗衣机、微波炉中选两种换新。其中，冰箱有4种型号可选，电视有6种型号可选，洗衣机有3种型号可选，微波炉有5种型号可选。请问小杨家共有多少种换新的方案？（ ）。

2.

小杨和3位朋友约好一起去看电影“哪吒2”。打开购票软件，他们发现，已经没有同一排连续的四个座位了（图中每个方框代表一个座位，红色方框代表已经售出）。朋友们商量了一下，决定分为两组，每组两人在同一排的相邻两个座位，且两组之间至少有一对座位是前后相邻的。请问共有多少种购票方案？（ ）。

3.

下面关于C++类构造和析构函数的说法，错误的是（  ）。

4.

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

5.

从1到2025这2025个数中，包含数字5的个数（ ）。

6.

已定义double类型的变量r和theta，分别表示图中圆半径和圆心角。下列表达式中可以求出弦长s的是（ ）。

7.

N个节点的平衡二叉树的高为（ ）。

8.

下列关于算法的说法，错误的是（ ）。

9.

2025是个神奇的数字，因为它是由两个数20和25拼接而成，而且2025=(20+25)2。小杨决定写个程序找找小于N的正整数中共有多少这样神奇的数字。下面程序横线处应填入的是（ ）。

1 #include <string> 
2 int count_miracle(int N) {
3  int cnt = 0; 
4  for (int n = 1; n * n < N; n++) { 
5   int n2 = n * n; 
6   std::string s = std::to_string(n2); 
7   for (int i = 1; i < s.length(); i++) 
8    if (s[i] != '0') { 
9     std::string sl = s.substr(0, i); 
10     std::string sr = s.substr(i); 
11     int nl = std::stoi(sl); 
12     int nr = std::stoi(sr); 
13     if (_________) // 在此处填入选项 
14      cnt++; 
15    } 
16  } 
17  return cnt; 
18 }


10.

2025是个神奇的数字，因为它是由两个数20和25拼接而成，而且2025=(20+25)2。小杨决定写个程序找找小于N的正整数中共有多少这样神奇的数字。该函数的时间复杂度为（ ）。

1 #include <string> 
2 int count_miracle(int N) { 
3  int cnt = 0; 
4  for (int n = 1; n * n < N; n++) { 
5   int n2 = n * n; 
6   std::string s = std::to_string(n2); 
7   for (int i = 1; i < s.length(); i++) 
8    if (s[i] != '0') { 
9     std::string sl = s.substr(0, i); 
10     std::string sr = s.substr(i); 
11     int nl = std::stoi(sl); 
12     int nr = std::stoi(sr); 
13     if (_________) // 在此处填入选项 
14      cnt++; 
15    } 
16  } 
17  return cnt; 
18 }


11.

下面的欧氏筛法程序中，两个横线处应填入的分别是（ ）。

1 int primes[MAXP], num = 0; 
2 bool isPrime[MAXN + 1] = {false}; 
3 void sieve() { 
4  for (int n = 2; n <= MAXN; n++) { 
5   if (!isPrime[n]) 
6    primes[num++] = n; 
7   for (int i = 0; i < num && ________; i++) { // 在此处填入选项 
8    isPrime[n * primes[i]] = true; 
9    if (________) // 在此处填入选项 
10     break; 
11   } 
12  } 
13 }

12.

下面Floyd算法中，横线处应该填入的是（ ）。

1 #include <iostream> 
2 using namespace std; 
3
4 #define N 21 
5 #define INF 99999999 
6 int map[N][N]; 
7 int main() { 
8  int n, m, t1, t2, t3; 
9  cin >> n >> m;
10  for (int i = 1; i <= n; i++) { 
11   for (int j = 1; j <= n; j++) { 
12    if (i == j) 
13     map[i][j] = 0; 
14    else 
15     map[i][j] = INF; 
16   } 
17  } 
18  for (int i = 1; i <= m; i++) { 
19   cin >> t1 >> t2 >> t3; 
20   map[t1][t2] = t3; 
21  } 
22  for (int k = 1; k <= n; k++) 
23   for (int i = 1; i <= n; i++) 
24    for (int j = 1; j <= n; j++) 
25     if (map[i][j] > map[i][k] + map[k][j]) 
26      ________; // 在此处填入选项 
27  for (int i = 1; i <= n; i++) { 
28   for (int j = 1; j <= n; j++) { 
29    cout.width(4); 
30    cout << map[i][j]; 
31   } 
32   cout << endl; 
33  } 
34 }


13.

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

1 #include <iostream> 
2 using namespace std; 
3
4 #define N 21 
5 #define INF 99999999 
6 int map[N][N]; 
7 int main() { 
8  int n, m, t1, t2, t3; 
9  cin >> n >> m; 
10  for (int i = 1; i <= n; i++) { 
11   for (int j = 1; j <= n; j++) {
12    if (i == j) 
13     map[i][j] = 0; 
14    else 
15     map[i][j] = INF; 
16   } 
17  } 
18  for (int i = 1; i <= m; i++) { 
19   cin >> t1 >> t2 >> t3; 
20   map[t1][t2] = t3; 
21  } 
22  for (int k = 1; k <= n; k++) 
23   for (int i = 1; i <= n; i++) 
24    for (int j = 1; j <= n; j++) 
25     if (map[i][j] > map[i][k] + map[k][j]) 
26      ________; // 在此处填入选项 
27  for (int i = 1; i <= n; i++) { 
28   for (int j = 1; j <= n; j++) { 
29    cout.width(4); 
30    cout << map[i][j]; 
31   } 
32   cout << endl; 
33  } 
34 }
14.

下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（ ）。

1 #include <iostream> 
2 using namespace std; 
3 #define N 35 
4 int a[N]; 
5 int main() { 
6  int n; 
7  cin >> n; 
8  for (int i = 0; i < n; i++) { 
9   a[i] = 1; 
10   for (int j = i - 1; j > 0; j--) 
11    ________; // 在此处填入选项 
12   for (int j = 0; j <= i; j++) 
13    cout << a[j] << " "; 
14   cout << endl; 
15  } 
16  return 0; 
17 }
15.

下列程序实现了输出杨辉三角形，其时间复杂度为（ ）。

1 #include <iostream> 
2 using namespace std; 
3 #define N 35 
4 int a[N]; 
5 int main() { 
6  int n; 
7  cin >> n; 
8  for (int i = 0; i < n; i++) { 
9   a[i] = 1; 
10   for (int j = i - 1; j > 0; j--) 
11    ________; // 在此处填入选项 
12   for (int j = 0; j <= i; j++) 
13   cout << a[j] << " "; 
14   cout << endl; 
15  } 
16  return 0; 
17 }
判断题 共 10 题
1.

表达式'5'-3.0的结果为2.0，类型为double。

2.

在C++语言中，如果想要在一个函数内调用一个类的私有方法，可以在该类中将该函数声明为友元函数。

3.

插入排序一般是稳定的。

4.

5个相同的红球和4个相同的蓝球排成一排，要求蓝球不能相邻，则一共有15种排列方案。

5.

使用math.h或cmath头文件中的函数，表达式pow(2,5)的结果类型为int、值为32。

6.

C++是一种面向对象编程语言，C则不是。多态是面向对象三大特性之一，虚函数是动态多态的代表特性。因此，使用C语言无法实现虚函数。

7.

在N个节点的平衡二叉树中查找指定元素的最差时间复杂度为O(N)。

8.

定义int类型的变量a和b，求二次函数y=x2+ax+b取最小值时x的值，可以通过表达式-a/2.0求得。

9.

判断无向图中是否有环，可以通过广度优先搜索实现。

10.

从32名学生中选出4人分别担任班长、副班长、学习委员和组织委员，共有C(32,4)种不同的选法。

问答题 共 2 题
1.

3.1 编程题 1

时间限制：1.0 s

内存限制：512.0 MB

3.1.1 上学

3.1.2 题目描述

C城可以视为由n个结点与m条边组成的无向图。这些结点依次以1,2,…,n标号，边依次以 1,2,…,m标号。第i条边（1≤i≤m）连接编号为ui与ui的结点，长度为li米。

小A的学校坐落在C城中编号为s的结点。小A的同学们共有q位，他们想在保证不迟到的前提下，每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小A。第i位同学（1≤i≤q）告诉小A，他的家位于编号为hi的结点，并且他每秒能行走1米。请你帮小A计算，每位同学从家出发需要多少秒才能到达学校呢？

3.1.3 输入格式

第一行，四个正整数n,m,s,q，分别表示C城的结点数与边数，学校所在的结点编号，以及小A同学们的数量。

接下来m行，每行三个正整数ui,ui,li，表示C城中的一条无向边。

接下来q行，每行一个正整数hi，表示一位同学的情况。

3.1.4 输出格式

共q行，对于每位同学，输出一个整数，表示从家出发到学校的最短时间。

3.1.5 样例

3.1.5.1 输入样例 1

3.1.5.2 输出样例 1

3.1.6 数据范围

对于20%的测试点，保证q=1。

对于另外20%的测试点，保证1≤n≤500，1≤m≤500。

对于所有测试点，保证1≤n≤2×105，1≤m≤2×105，1≤q≤2×105，1≤ui,ui,s,hi≤n，1≤li≤106。保证给定的图联通。

2.

3.2 编程题 2

试题名称：割裂

时间限制：4.0 s

内存限制：512.0 MB

3.2.8 题面描述

小杨有一棵包含n个节点的树，其中节点的编号从1到n。

小杨设置了a个好点对｛＜u1,u1＞,＜u2,u2＞,…,＜ua,ua＞｝和1个坏点对＜bu,bu。一个节点能够被删除，当且仅当：

删除该节点后对于所有的i(1≤i≤a)，好点对ui和ui仍然连通；

删除该节点后坏点对bu和bu不连通。

如果点对中的任意一个节点被删除，其视为不连通。

小杨想知道，有多少个节点能够被删除。

3.2.9 输入格式

第一行包含两个正整数n,a，含义如题面所示。

之后n-1行，每行包含两个正整数xi,yi，代表存在一条连接节点xi和yi的边。

之后a行，每行包含两个正整数ui,ui，代表一个好点对＜ui,ui＞。

最后一行包含两个正整数bu,bu，代表坏点对＜bu,bu＞。

3.2.10 输出格式

输出一个正整数，代表能够删除的节点个数。

3.2.11 样例

3.2.12 输入样例

3.2.13 输出样例

3.2.14 数据范围

对于全部数据，保证有1≤n≤106,0≤a≤105,ui≠ui,bu≠bu。

C++ 编辑器
输入
输出