1、某班级有8名男生和6名女生，现要选出3人组成学习小组，要求小组中至少有1名男生和1名女生，则不同的选法共有（ ）种。

{{ select(1) }}

• 112
• 168
• 224
• 288

---

2、在杨辉三角中，从第0行开始计数，第10行的所有数之和为（ ）。

{{ select(2) }}

• 512
• 1024
• 2048
• 4096

---

3、下列代码实现了快速幂算法，其时间复杂度为（ ）。

long long fastPow(long long b, long long e, long long mod) {
    long long result = 1;
    while (e > 0) {
        if (e & 1)
            result = result * b % mod;
        b = b * b % mod;
        e >>= 1;
    }
    return result;
}

{{ select(3) }}

• O(log b)
• O(log e)
• O(log mod)
• O(e)

---

4、从5本不同的数学书和4本不同的物理书中选取3本书，要求至少包含1本数学书，则不同的选法有（ ）种。

{{ select(4) }}

• 60
• 74
• 80
• 84

---

5、在二叉搜索树（BST）中，若中序遍历的序列为 {1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（ ）。

{{ select(5) }}

• 该树一定是一棵完全二叉树
• 元素4和5不可能是兄弟节点
• 元素1所在节点的深度可能大于3（根节点深度为1）
• 元素2一定是元素1的父节点

---

6、在一个有向带权图中，使用Dijkstra算法求单源最短路时，若使用优先队列（小根堆）优化，其时间复杂度为（ ）。

{{ select(6) }}

• $O(V^2)$
• $O(V \cdot E)$
• $O((V+E)\log V)$
• $O(V^2 \log V)$

---

7、对于含n个顶点（$n\ge 2$）的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（ ）条边。

{{ select(7) }}

• n
• n-1
• n+1
• 无法确定，取决于图的具体边数

---

8、在使用Floyd算法求任意两点间最短路径时，时间复杂度为 $O(V^3)$。若在某次算法执行前，已经用Dijkstra算法正确求出了所有点对的最短路并存入了dist数组。如果此时继续对该dist数组执行一次完整的Floyd算法过程（无任何提前终止），执行完毕后dist数组内的值（ ）。

{{ select(8) }}

• 会发生改变，因为Floyd又做了一次松弛
• 不会发生改变
• 可能变大，因为未针对已有最短路优化
• 可能在某些负权图中陷入死循环

---

9、关于图论中的最短路径算法，下列说法中严格正确的是（ ）。

{{ select(9) }}

• Dijkstra算法能够高效处理包含负权边的有向图。
• Floyd算法可以求出任意两点间的最短路径，且允许图中存在负权边（但不能有负权环）。
• 单源最短路径算法无法用于无向图，无向图只能通过BFS求解。
• Dijkstra算法的每一步必定从当前未访问的节点中，选取距离起始点最远的节点进行松弛操作。

---

10、有6个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有（ ）种。

{{ select(10) }}

• 120
• 144
• 192
• 240

---

11、下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（ ）。

void floyd(int n, int dist[][MAXN]) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (__________________) // 在此处填入选项
                    dist[i][j] = dist[i][k] + dist[k][j];
}

{{ select(11) }}

• dist[i][k] + dist[k][j] < dist[i][j]
• dist[i][k] != INF && dist[k][j] != INF
• dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]
• dist[i][j] == INF

---

12、用数字0、1、2、3、4组成无重复数字的五位偶数，共有（ ）个。

{{ select(12) }}

• 48
• 60
• 72
• 96

---

13、在一个无向带权图中，若使用Prim算法从顶点0开始构造最小生成树（边权均为正整数，且 graph[u][v] == 0 表示无边），下列代码中横线处应填入（ ）。

int prim(vector<vector<int>>& graph, int n) {
    vector<bool> inMST(n, false);
    vector<int> minEdge(n, INT_MAX);
    minEdge[0] = 0;
    int result = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++)
            if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))
                u = j;
        inMST[u] = true;
        result += minEdge[u];
        for (int v = 0; v < n; v++)
            if (__________________) // 在此处填入选项
                minEdge[v] = graph[u][v];
    }
    return result;
}

{{ select(13) }}

• graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v]
• !inMST[v] && graph[u][v] < minEdge[v]
• graph[u][v] > 0 && !inMST[v]
• !inMST[v] && minEdge[v] > 0

---

14、已知三个点A($x_1, y_1$)，B($x_2, y_2$)，C($x_3, y_3$)在平面直角坐标系中的坐标。下列C++表达式中，在精度误差范围1e-8内能正确计算判断这三个点是三点共线的表达式是（ ）。

{{ select(14) }}

• (x2 - x1) / (y2 - y1) == (x3 - x1) / (y3 - y1)
• (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) == 0
• fabs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) < 1e-8
• fabs((x2 - x1) / (y2 - y1) - (x3 - x1) / (y3 - y1)) < 1e-8

---

15、在64位操作系统下（LP64/LLP64模型），下面代码的输出结果是（ ）。

#include <iostream>
using namespace std;

int main() {
    int a[4] = {1, 2, 3, 4};
    int (*p)[4] = &a;
    int *q = a;
    
    cout << sizeof(a) << " ";
    cout << sizeof(p) << " ";
    cout << sizeof(p + 1) << " ";
    cout << sizeof(q + 1) << " ";
    cout << (p + 1) - p << " ";
    cout << (q + 1) - q << endl;
}

{{ select(15) }}

• 16 8 8 8 1 1
• 16 8 16 8 1 1
• 16 8 8 4 4 1
• 16 8 8 8 4 1

---