GESP 六级 · GESP 202512 C++ 六级 第 8 题

下面代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。

struct Symbol {
	char ch; //字符
	long long freq; //频率
	string code; //哈夫曼编码
};
struct Node {
	long long w; //权值
	int l, r; //左右孩子（节点下标），-1 表示空
	int sym; // 叶子对应符号下标；内部节点为 -1
	Node(long long _w=0, int _l=-1, int _r=-1, int _sym=-1)
	: w(_w), l(_l), r(_r), sym(_sym) {}
};
// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
static int PopMinNode(const vector<Node>& nodes,
					  const vector<int>& leafIdx, int n, int& pA,
					  const vector<int>& internalIdx, int& pB) {
	if (pA < n && (pB >= (int)internalIdx.size() ||
				   nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) {
		return leafIdx[pA++];
	}
	else {
		return internalIdx[pB++];
	}
}
// DFS 生成编码（左 0，右 1）
static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path) {
	if (u == -1) return;
	if (nodes[u].sym != -1) { // 叶子
		sym[nodes[u].sym].code = path;
		return;
	}
	path.push_back('0');
	DFSBuildCodes(nodes[u].l, nodes, sym, path);
	path.pop_back();
	path.push_back('1');
	DFSBuildCodes(nodes[u].r, nodes, sym, path);
	path.pop_back();
}
int BuildHuffmanCodes(Symbol sym[], int n) {
	for (int i = 0; i < n; i++) sym[i].code.clear();
	if (n <= 0) return -1;
	// 只有一个字符：约定编码为 "0"
	if (n == 1) {
		sym[0].code = "0";
		return 0;
	}
	vector<Node> nodes;
	nodes.reserve(2 * n);
	// 1) 建立叶子节点
	vector<int> leafIdx(n);
	for (int i = 0; i < n; i++) {
		leafIdx[i] = (int)nodes.size();
		nodes.push_back(Node(sym[i].freq, -1, -1, i));
	}
	// 2) 叶子按权值排序（A 队列）
	sort(leafIdx.begin(), leafIdx.end(),
		 [&](int a, int b) {
			 if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w;
			 return nodes[a].sym < nodes[b].sym; // 稳定一下
		 });
	// B 队列（内部节点下标队列）
	vector<int> internalIdx;
	internalIdx.reserve(n);
	int pA = 0, pB = 0;
	// 3) 合并 n-1 次
	for (int k = 1; k < n; k++) {
		int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
		int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
		int z = (int)nodes.size();
		________________________ // 在此处填写代码
	}
	int root = internalIdx.back();
	// 4) DFS 生成编码
	string path;
	DFSBuildCodes(root, nodes, sym, path);
	return root;
}

A.

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
internalIdx.push_back(z);

B.

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
leafIdx.push_back(z);

C.

internalIdx.push_back(z);
nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));

D.

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));
leafIdx.push_back(z);

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】哈夫曼树构建｜队列合并逻辑｜Node结构体语义

1. 🎯 考纲定位

GESP 六级算法模块，考查最小堆思想与结构体字段语义。命题人卡住的是学生对“内部节点”与“叶子节点”在数据结构中角色差异的区分能力。