模块 04 · 结构进阶
数据结构进阶应用
数据结构是算法的骨架。进入第二赛段,考查重心从简单的一维数组拓展到二维数组的物理存储、字符串回文特性、栈的先进后出约束以及循环周期取模。
4.2 C++ 二维数组内存布局与语法声明
在概念上,二维数组是一个由行和列构成的表格;但是在物理计算机的内存条中,所有内存单元都是一条连续的一维线性地址链。C++ 采用行优先存储(Row-Major Order)。
🔑 为什么声明二维数组时,行数可省但列数绝对不能省?
编译器在将 a[i][j] 翻译成内存物理地址时,使用的是如下公式:
地址(a[i][j]) = 首地址 + (i × 列数 + j) × 单个元素字节数
关键所在:要计算下一行(i + 1)在内存中跳跃多少个字节,编译器必须精确知道每一行到底包含多少列(即列数)!因此:
- ✔
int a[][2] = {{1, 2}, {3, 4}};—— 合法!编译器看到总共 4 个数,每行 2 列,自动推导出有 2 行。 - ❌
int a[][] = {{1, 2}, {3, 4}};—— 非法!行列均省略,编译器无法计算物理寻址步长。 - ❌
int a[2][] = {{1, 2}, {3, 4}};—— 非法!省略了列数,编译器直接报错。
互动实验 03
二维数组物理内存映射可视化
点击下方 3 行 4 列矩阵中的任意单元格,观察其二维坐标 (i, j) 如何瞬间转换为物理内存中的一维扁平序号:
💡 点击上方矩阵方格体验物理内存映射计算。
4.3 字符串高级技巧与最长回文子串
子串(Substring):必须是原字符串中连续的一段字符。例如对于 "ABCD","BC" 是子串,而 "AC" 只能叫子序列。
回文子串:正着读和反着读完全一致的子串(如 "ABA"、"ABBA")。
真题直击 · 2025 第2题
挖掘字符串中的最长回文子串
已知字符串 S = "CABCBAABCABCBCBAB",求其最长回文子串的长度。
核心算法:中心扩散法
回文串一定具有对称中心。对称中心有两种可能:
1. 奇数长度:以单个字符为中心(如
2. 偶数长度:以两个相邻相同字符的缝隙为中心(如
1. 奇数长度:以单个字符为中心(如
...C-B-A-[B]-A-B-C...);2. 偶数长度:以两个相邻相同字符的缝隙为中心(如
...A-B-[B]-A...)。在串中精准定位
观察 S =
子串
• 正向读:A → B → C → B → C → B → A;
• 反向读:A → B → C → B → C → B → A;
其长度为 7!经全串扫描,不存在长度为 8 的回文子串。因此最长回文子串长度为 7(选 C)。
"C A B C B A A B C [A B C B C B A] B" 的后半段:子串
"ABCBCBA":• 正向读:A → B → C → B → C → B → A;
• 反向读:A → B → C → B → C → B → A;
其长度为 7!经全串扫描,不存在长度为 8 的回文子串。因此最长回文子串长度为 7(选 C)。
4.4 栈(Stack)的先进后出与出栈序列合法性
栈是受限线性表,只允许在同一端进行插入和删除。核心原则:后进先出(LIFO, Last In First Out)。在信息学竞赛中,出栈合法性判断是百考不厌的题型。
⚖️ 经典判定规则:任何时候出栈的元素,必须是当前已入栈元素的最顶端!
真题考查(2025 第3题):入栈顺序为 1, 2, 3, 4, 5, 6, 7,为什么 1, 4, 2, 3, 7, 6, 5 是非法的?
第一步
元素 1 入栈,接着立即出栈。此时栈空。输出序列:
[1];第二步
序列下一个要求出栈的是 4!为了让 4 出栈,必须将 2, 3, 4 依次压栈。此时栈内状态(底→顶):
[2, 3, 4];第三步
元素 4 出栈。此时栈顶露出来的元素是 3!栈底是 2。栈内状态:
[2, 3];矛盾爆发!
序列下一个出栈的居然写着 2!根据栈的规则,只要 3 还在栈顶,2 就被压在底下,绝对不可能跳过 3 先出 2!因此该序列彻底非法!
4.5 循环队列与周期模运算(2025 填空真题解码)
真题直击 · 2025 第27题
滑动窗口差分与循环数组周期
100 个小球排入 36 个盒子。任意相邻 5 个盒子小球和为 14,第 1 个盒有 2 个小球。问第 36 个盒有几个?
滑动窗口差分推导:
窗口 1:a[1] + a[2] + a[3] + a[4] + a[5] = 14
窗口 2:a[2] + a[3] + a[4] + a[5] + a[6] = 14
两式相减:a[6] - a[1] = 0 ⇒ a[6] = a[1]!
同理可证:a[i + 5] = a[i],周期严格为 5!
求 a[36]:因为 36 = 7 × 5 + 1 ≡ 1 (mod 5),
所以 a[36] = a[31] = ... = a[1] = 2 个!
窗口 1:a[1] + a[2] + a[3] + a[4] + a[5] = 14
窗口 2:a[2] + a[3] + a[4] + a[5] + a[6] = 14
两式相减:a[6] - a[1] = 0 ⇒ a[6] = a[1]!
同理可证:a[i + 5] = a[i],周期严格为 5!
求 a[36]:因为 36 = 7 × 5 + 1 ≡ 1 (mod 5),
所以 a[36] = a[31] = ... = a[1] = 2 个!
真题直击 · 2025 第30题
卡牌平移循环回归与最小公倍数
一副 54 张扑克牌,最上面是红桃 K。每次把最顶上 12 张移到底部,至少几次移动红桃 K 重回顶端?
模周期数学模型:
红桃 K 重新回到第 1 个位置,说明所有牌在环形队列中累计平移的张数必须是整副牌数 54 的整数倍。
设移动 k 次,累计移动了 12k 张牌。
要求 12k 是 54 的倍数,求最小正整数 k:
12k = lcm(12, 54)。
因为 gcd(12, 54) = 6,故 lcm(12, 54) = 12 × 54 / 6 = 108。
因此 k = 108 / 12 = 9 次!
红桃 K 重新回到第 1 个位置,说明所有牌在环形队列中累计平移的张数必须是整副牌数 54 的整数倍。
设移动 k 次,累计移动了 12k 张牌。
要求 12k 是 54 的倍数,求最小正整数 k:
12k = lcm(12, 54)。
因为 gcd(12, 54) = 6,故 lcm(12, 54) = 12 × 54 / 6 = 108。
因此 k = 108 / 12 = 9 次!
课后强化测验
模块四 · 全真过关检测(共5题)
在 C++ 语言中,以下关于二维数组的声明与初始化,哪个选项是符合语法的?( )
【解题精析】
C++ 规定二维数组物理存储按行连续展开,编译器必须根据列数计算每一行的首地址偏移,因此行数可省但列数绝不能省。B 选项完全合法。故选 B。
C++ 规定二维数组物理存储按行连续展开,编译器必须根据列数计算每一行的首地址偏移,因此行数可省但列数绝不能省。B 选项完全合法。故选 B。
回文子串指的是一个字符串中正读和反读都完全相同的连续字符序列。对于字符串 S = "CABCBAABCABCBCBAB",其最长回文子串的长度是( )。
【解题精析】
子串 "ABCBCBA" 连续且中心对称,长度为 7,是串中最长的回文子串。故选 C。
子串 "ABCBCBA" 连续且中心对称,长度为 7,是串中最长的回文子串。故选 C。
对于入栈顺序为 1, 2, 3, 4, 5, 6, 7 的序列,下列序列中不可能是合法的出栈序列的是( )。
【解题精析】
C 选项中,4 出栈后栈顶为 3,底为 2,下一个必须出 3,不能先出 2。故选 C。
C 选项中,4 出栈后栈顶为 3,底为 2,下一个必须出 3,不能先出 2。故选 C。
将 100 个小球放入依次排列的 36 个盒子中。如果任意相邻 5 个盒子中的小球总数均为 14,且第 1 个盒子里有 2 个小球。那么第 36 个盒子中有( )个小球。
【解题精析】
相邻 5 盒和恒定推出周期为 5。36 ≡ 1 (mod 5),故第 36 盒球数等于第 1 盒球数,即 2 个。故选 A。
相邻 5 盒和恒定推出周期为 5。36 ≡ 1 (mod 5),故第 36 盒球数等于第 1 盒球数,即 2 个。故选 A。
一副扑克牌共 54 张,最上面一张是红桃 K。如果每次把最上面的 12 张牌平移到底部且不改变它们的相对顺序,那么至少经过( )次移动,红桃 K 才会再次出现在最上面?
【解题精析】
移动张数是 54 的倍数:lcm(12, 54) = 108,因此移动次数 k = 108 / 12 = 9 次。故选 B。
移动张数是 54 的倍数:lcm(12, 54) = 108,因此移动次数 k = 108 / 12 = 9 次。故选 B。