[GESP202409八级] 客观题

ID: 4296

客观题

尝试: 0

已通过: 0

难度: 2

上传者:

Hydro

标签>

GESP真题

八级

选择题

图论

数组排序

最小生成树

函数

数学

分支结构

数论

最短路

结构体

题目描述

以下为 GESP 2024 年 09 月 C++ 八级客观题。请在页面中完成选择题、判断题等题目作答。

一.单选题(每题2分，共30分)

下⾯关于C++类和对象的说法，错误的是

类的析构函数可以为虚函数。
类的构造函数不可以为虚函数。
class中成员的默认访问权限为private。
struct中成员的默认访问权限为private。

对于⼀个具有n个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵的⼤⼩为

$n ✖ \frac{n}{2}$
$n ✖ n$
$(n-1)✖(n-1)$
$(n+1)✖(n+1)$

设有编号为A、 B、 C、 D、 E的5个球和编号为A、 B、 C、 D、 E的5个盒⼦。现将这5个球投⼊5个盒⼦，要求每个盒⼦放⼀个球，并且恰好有两个球的编号与盒⼦编号相同，问有多少种不同的⽅法？

$5$
$120$
$20$
$60$

从甲地到⼄地，可以乘⾼铁，也可以乘汽车，还可以乘轮船。⼀天中，⾼铁有10班，汽车有5班，轮船有2班。那么⼀天中乘坐这些交通⼯具从甲地到⼄地共有多少种不同的⾛法？

$100$
$60$
$30$
$17$

n个结点的⼆叉树，执⾏释放全部结点操作的时间复杂度是

$O(n)$
$O(nlogn)$
$O(logn)$
$O(2^n)$

在⼀个单位圆上，随机分布个点，求这个点能被⼀个单位半圆周全部覆盖的概率

$\frac{n}{2^n-1}$
$\frac{1}{n^2}$
$\frac{1}{n}$
$\frac{1}{2^n}$

下⾯ pailie 函数是⼀个实现排列的程序，横线处可以填⼊的是（）。

#include <iostream>
using namespace std;
int sum = 0;
void swap(int & a, int & b) {
  int temp = a;
  a = b;
  b = temp;
}
void pailie(int begin, int end, int a[]) {
  if (begin == end) {
  for (int i = 0; i < end; i++)
        cout << a[i];
    cout << endl;
  }
  for (int i = begin; i < end; i++) {
    __________ // 在此处填入选项
  }
}

swap(a[begin + 1], a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin]);

swap(a[begin], a[i]);
pailie(begin, end, a);
swap(a[i], a[begin]);

swap(a[begin], a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin]);

swap(a[begin] + 1, a[i]);
pailie(begin + 1, end, a);
swap(a[i], a[begin + 1]);

上⼀题中，如果主函数为如下的程序，则最后的排列数是多少个 ?
```
int main() {
  int a[5] = {1, 2, 3, 4, 5};
  pailie(0, 5, a);
  return 0;
}
```

$120$
$60$
$240$
$180$

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

#include <iostream>
using namespace std;
#define N 35
int a[N][N];
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++) {
      if (j == 1 || j == i)
        a[i][j] = 1;
      else
        __________ // 在此处填入选项
    }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++)
      cout << a[i][j];
    cout<<endl;
  }
  return 0;
}

a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
a[i][j] = a[i][j - 1] + a[i - 1][j];
a[i][j] = a[i - 1][j] + a[i - 1][j];
a[i][j] = a[i - 1][j - 1] + a[i][j];

下⾯最⼩⽣成树的Kruskal算法程序中，横线处应该填⼊的是

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
  int u, v, weight;
  bool operator <(const Edge & other) const {
    return weight < other.weight;
  }
};
int findParent(int vertex, vector<int> & parent) {
  if (parent[vertex] == -1)
    return vertex;
  return parent[vertex] = findParent(parent[vertex], parent);
}
int main() {
  int n, m;
  cin >> n >> m; // n: 顶点数, m: 边数
  vector<Edge> edges(m);
  vector<int> parent(n, -1);
  int totalWeight = 0;
  for (int i = 0; i < m; i++)
    cin >> edges[i].u >> edges[i].v >> edges[i].weight;

  sort(edges.begin(), edges.end());
  for (const auto & edge : edges) {
    int uParent = findParent(edge.u, parent);
    int vParent = findParent(edge.v, parent);
    if (__________) { // 在此处填入选项
      parent[uParent] = vParent;
      totalWeight += edge.weight;
    }
  }
}

uParent == vParent
uParent == vParent
uParent != vParent
uParent <= vParent

下⾯Prim算法程序中，横线处应该填⼊的是

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prim(vector<vector<int>> & graph, int n) {
  vector<int> key(n, INT_MAX);
  vector<int> parent(n, -1);
  key[0] = 0;
  for (int i = 0; i < n; i++) {
    int u = min_element(key.begin(), key.end()) - key.begin();
    if (key[u] == INT_MAX)
      break;
    for (int v = 0; v < n; v++) {
      if (__________) { // 在此处填入选项
        key[v] = graph[u][v];
        parent[v] = u;
      }
    }
  }
  int sum = 0;
  for (int i = 0; i < n; i++) {
    if (parent[i] != -1) {
      cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] <<
      endl;
      sum += key[i];
    }
  }
  return sum;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> graph(n, vector<int>(n, 0));
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u][v] = w;
    graph[v][u] = w;
  }
  int result = prim(graph, n);
  cout << "Total weight of the minimum spanning tree: " << result << endl;
  return 0;
}

graph[u][v] >= 0 && key[v] > graph[u][v]
graph[u][v] <= 0 && key[v] > graph[u][v]
graph[u][v] == 0 && key[v] > graph[u][v]
graph[u][v] != 0 && key[v] > graph[u][v]

下列Dijkstra算法中，横线处应该填⼊的是

#include <iostream>
using namespace std;
#define N 100
int n, e, s;
const int inf = 0x7fffff;
int dis[N + 1];
int cheak[N + 1];
int graph[N + 1][N + 1];
int main() {
  for (int i = 1; i <= N; i++)
  dis[i] = inf;
  cin >> n >> e;
  for (int i = 1; i <= e; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a][b] = c;
  }
    cin >> s;
  dis[s] = 0;
  for (int i = 1; i <= n; i++) {
    int minn = inf, minx;
    for (int j = 1; j <= n; j++) {
      if (__________) { // 在此处填入选项
        minn = dis[j];
        minx = j;
      }
    }
    cheak[minx] = 1;
    for (int j = 1; j <= n; j++) {
      if (graph[minx][j] > 0) {
        if (minn + graph[minx][j] < dis[j]) {
          dis[j] = minn + graph[minx][j];
        }
      }
    }
  }
}

dis[j] > minn && cheak[j] == 0
dis[j] < minn && cheak[j] == 0
dis[j] >= minn && cheak[j] == 0
dis[j] < minn && cheak[j] != 0

下⾯Floyd算法中，横线处应该填⼊的是

```cpp
#include <iostream>
using namespace std;

#define N 21
#define INF 99999999
int map[N][N];
int main() {
  int n, m, t1, t2, t3;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j)
        map[i][j] = 0;
      else
        map[i][j] = INF;
    }
    }
  for (int i = 1; i <= m; i++) {
    cin >> t1 >> t2 >> t3;
    map[t1][t2] = t3;
  }
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (__________) // 在此处填入选项
          map[i][j] = map[i][k] + map[k][j];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cout.width(4);
      cout << map[i][j];
    }
    cout << endl;
  }
}
```

map[i][j] < map[i][k] + map[k][j]
map[i][j] > map[i][k] + map[k][j]
map[i][j] > map[i][k] - map[k][j]
map[i][j] < map[i][k] - map[k][j]

下⾯程序的 Merge_Sort 函数时间复杂度为

void Merge(int a[], int left, int mid, int right) {
int temp[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (a[i] < a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= mid)
temp[k++] = a[i++];
while (j <= right)
temp[k++] = a[j++];
for (int m = left, n = 0; m <= right; m++, n++)
a[m] = temp[n];
}
void Merge_Sort(int a[], int left, int right) {
if (left == right)
return;
int mid = (left + right) / 2;
Merge_Sort(a, left, mid);
Merge_Sort(a, mid + 1, right);
Merge(a, left, mid, right);
}

$O(nlogn)$
$O(n^2)$
$O(2^n)$
$O(logn)$

下⾯ fibonacci 函数的时间复杂度为

int fibonacci(int n) {
if (n <= 1)
  return n;
else
  return fibonacci(n - 1) + fibonacci(n - 2);
}

$O(1)$
$O(\empty^n)$ ， $\empty=\frac{\sqrt{5}-1}{2}$
$O(n)$
$O(nlogn)$

二.判断题(每题2分，共20分)

表达式 '3' & 1 的结果为 '1' 。

{{ select(16) }}

正确
错误

在C++语⾔中，变量定义必须在某⼀个函数定义之内。

{{ select(17) }}

正确
错误

冒泡排序⼀般是不稳定的。

{{ select(18) }}

正确
错误

⼆叉排序树的查找操作的平均时间复杂度，正⽐于树的⾼度。

正确
错误

使⽤ math.h 或 cmath 头⽂件中的余弦函数，表达式 cos(60) 的结果类型为 double 、值约为 0.5 。

{{ select(20) }}

正确
错误

你有三种硬币，分别⾯值2元、 5元和7元，每种硬币都有⾜够多。买⼀本书需要27元，则最少可以⽤5个硬币组合起来正好付清，且不需要对⽅找钱。

{{ select(21) }}

正确
错误

现有个完全相同的元素，要将其分为k组，允许每组可以有0歌个元素，则一共有C(n-1,k-1)种分组方案。

{{ select(22) }}

正确
错误

已知 int 类型的变量 a 和 b 中分别存储着⼀个直角三角形的两条直角边的长度，则该三角形的⾯积可以通过表达式a/2.0*b求得。

{{ select(23) }}

正确
错误

已知等差数列的通项公式 $a_n=a_1+(n-1)*d$ ，则前n项和求和公式 $S_n=n*(a_1+a_n)/2$ 。使用这一公式计算 $S_n$ 的时间复杂度是O(1)。

{{ select(24) }}

正确
错误

诚实国公民只说实话，说谎国公民只说谎话。你来到⼀处分岔⼝，⼀条通往诚实国，⼀条通往说谎国，但不知是哪⼀条通往哪⾥。正在为难之际，⾛来两位路⼈，他们都⾃称是诚实国公民，都说对⽅是说谎国公民。你想去说谎国，可以这样问其中⼀位路⼈： “我要去说谎国，如果我去问另⼀个路⼈，他会指向哪⼀条路？ ”。

{{ select(25) }}

正确
错误

输入格式

本题为客观题，无标准输入。

输出格式

本题为客观题，无标准输出；请在交互页面中直接选择答案。

数据范围与提示

按题面客观题要求作答；本题不使用文件输入输出。

来源

GESP 2024 年 09 月 C++ 八级

#GESP1072. [GESP202409八级] 客观题

题目描述

输入格式

输出格式

数据范围与提示

来源

登录