一. 单选题（每题 2 分，共 30 分）

1. 下⾯关于C++类和对象的说法，错误的是（ ）。 {{ select(1) }}

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

2. 对于⼀个具有 个顶点的⽆向图，若采⽤邻接矩阵表示，则该矩阵的大小为（ ）。

{{ select(2) }}

• n x (n/2)
• n x n
• (n - 1) x (n - 1)
• (n + 1) x (n + 1)

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

{{ select(3) }}

• 5
• 120
• 20
• 60

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

{{ select(4) }}

• 100
• 60
• 30
• 17

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

{{ select(5) }}

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

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

{{ select(6) }}

• n / $2^n$$^-$$^1$
• 1 / $2^2$
• 1 / n
• 1 / $2^n$

7. 下⾯ 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++) {
 __________ // 在此处填入选项
} 
}

{{ select(7) }}

• 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]);

8. 上⼀题中，如果主函数为如下的程序，则最后的排列数是多少个？（ ）。

int main() {
 int a[5] = {1, 2, 3, 4, 5};
 pailie(0, 5, a);
 return 0;
 }

{{ select(8) }}

• 120
• 60
• 240
• 180

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

#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;
 }

{{ select(9) }}

• 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];

10. 下⾯最⼩⽣成树的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;
 }
 }
 }

{{ select(10) }}

• uParent == vParent
• uParent >= vParent
• uParent != vParent
• uParent <= vParent

11. 下⾯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;
 }

{{ select(11) }}

• 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]

12. 下列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];
                }
            }
        }
    }
 }

{{ select(12) }}

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

13. 下⾯Floyd算法中，横线处应该填⼊的是（ ）。

#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;
    }
 }

{{ select(13) }}

• 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]

14. 下⾯程序的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);
 }

{{ select(14) }}

• $O(n log n)$
• $O(n^2$)
• $O(2^n$)
• $O(log n)$

15. 下⾯fibonacci 函数的时间复杂度为（ ）。

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

{{ select(15) }}

• $O(1)$
• $O(∅^n$, ∅=(√5 -1)/2)
• $O(n)$
• $O(n log n)$

二. 判断题（每题 2 分，共 20 分）

1. 表达式'3' & 1 的结果为'1' 。 {{ select(16) }}

• 对
• 错

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

   {{ select(17) }}

• 对
• 错

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

   {{ select(18) }}

• 对
• 错

4. ⼆叉排序树的查找操作的平均时间复杂度，正⽐于树的⾼度。 {{ select(19) }}

• 对
• 错

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

{{ select(20) }}

• 对
• 错

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

• 对
• 错

7. 现有n个完全相同的元素，要将其分为k组，允许每组可以有0个元素，则⼀共有C(n-1,k-1)种分组⽅案。 {{ select(22) }}

• 对
• 错

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

{{ select(23) }}

• 对
• 错

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

   {{ select(24) }}

• 对
• 错

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

• 对
• 错