E1037 202603 CCF-GESP C++八级真题-练习

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

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

下列代码试图实现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];
}

在一个无向带权图中，若使用 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;
}

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