GESP 六级 · GESP202609 C++ 六级 第 12 题

下面代码用反射法生成 n 位格雷编码，横线处应填写（　　）。

vector<string> gray(int n) {
vector<string> ans = {"0", "1"};
for (int bit = 2; bit <= n; ++bit) {
int oldSize = ans.size();
for (int i = oldSize - 1; i >= 0; --i)
ans.push_back(__________________________);
for (int i = 0; i < oldSize; ++i)
ans[i] = "0" + ans[i];
}
return ans;
}

格雷码的反射法生成规则是：先保留原序列，再在末尾追加"1"+原序列的反转。代码中正向循环已处理"0"+原序列，反向循环必须补"1"+原序列的反转。由于反向循环 i 从 oldSize-1 递减到 0，直接取 ans[i] 正好是原序列的逆序，因此横线处应填"1"+ans[i]。

A 项把"1"拼在末尾，破坏格雷码相邻仅一位不同的性质；B 项与正向循环重复，会生成"00"这种非法格雷码；D 项只是取反转索引，缺少"1"前缀，无法完成反射构造。反向循环的 i 递减顺序是命题人埋下的隐蔽提示——它暗示你正在构造反转序列，但很多考生会忽略这一点，机械地选 D 以为取反转索引就够了。

1. 考纲定位

本题考查 GESP 六级《算法与数据结构》模块中的格雷码构造，属于递归与迭代结合的典型题型。命题人把这道题放在六级，是因为它同时考察了字符串拼接、列表操作和算法思维——大多数考生能看懂格雷码概念，但一到代码实现就卡壳，尤其是反向构造那一步。

2. 解题思维

格雷码的反射法生成规则是：先保留原序列，再在末尾追加"1"+原序列的反转。代码中正向循环已处理"0"+原序列，反向循环必须补"1"+原序列的反转。由于反向循环 i 从 oldSize-1 递减到 0，直接取 ans[i] 正好是原序列的逆序，因此横线处应填"1"+ans[i]。