第2章 C语言与数据结构高频面试题：指针、数组、结构体、位运算、链表、队列、栈
本章聚焦单片机开发最常考的 C 语言与数据结构核心题型。指针、数组、位运算、结构体以及链表/队列/栈的手写实现，是面试中区分候选人基本功的关键。掌握回答框架与避坑要点，避免在“指针偏移”“内存对齐”“链表反转”等高频陷阱中失分。
📊 C语言与数据结构核心考点速查表
| 模块 | 高频考点 | 典型陷阱 | 推荐练习 |
|---|---|---|---|
| 指针 | 指针与数组、函数指针、多级指针 | &a[0]与a混淆；指针加减步长 | 手写strcpy，memmove |
| 数组 | 数组越界、二维数组行指针 | sizeof(数组名) vs sizeof(指针) | 实现环形缓冲区 |
| 结构体 | 内存对齐、位域、柔性数组 | 对齐规则导致sizeof不符合预期 | 计算结构体sizeof并验证 |
| 位运算 | 置位/清零、位掩码、字节序转换 | 有符号数右移符号位扩展 | 实现寄存器位操作宏 |
| 链表 | 单链表反转、环检测、有序合并 | 断链、空指针解引用 | 手写反转链表（迭代/递归） |
| 队列/栈 | 循环队列、括号匹配、LRU | 队列判空判满、函数调用栈 | 数组模拟循环队列 |
🎯 面试问题 1
问题：请解释以下代码输出什么？为什么？
int a[5] = {1,2,3,4,5};
int *p = (int*)(&a+1);
printf("%d", *(p-1));面试官考察点：
- 是否理解 &a 与 a 的区别（数组指针 vs 首元素指针）
- 指针加法本质：移动多少个字节
- 指针与数组在解引用时的行为差异
回答框架：
- 明确 a 的类型：int[5]，&a 类型是 int(*)[5]
- &a+1 跨过整个数组，指向数组末尾之后
- 强转后 p 指向 int，p-1 回退一个 int 大小
- 结论：输出数组最后一个元素 5
示例回答（<60字）：
a 是 int[5] 数组，&a 取数组地址，+1 跳 5×4=20 字节到末尾后；强转为 int* 后 p-1 指向 a[4]，输出 5。关键：指针加减以自身类型为单位。
可能追问：
- 如果 p = (int*)(a+1); 再 *(p-1) 输出什么？（输出 1）
- sizeof(a) 和 sizeof(p) 分别是多少？
- 如果把 a 改成二维数组 int b[2][5]，&b+1 又如何？
避坑提醒：
❌ 常见错误：混淆 &a 与 a 导致偏移计算错误。回答时一定要区分“数组地址”和“首元素地址”。
🎯 面试问题 2
问题：32位系统下，sizeof(struct Test) 是多少？
struct Test {
char a;
int b;
char c;
};面试官考察点：
- 是否掌握内存对齐规则（默认 4 字节对齐）
- 能否手动计算每个成员偏移和整体大小
- 是否了解 packed 和 alignment 特性
回答框架：
- 列出各成员自身对齐值：char 1，int 4
- 从偏移0开始：a占1，b需对齐到4的倍数，填充3字节
- b占用4字节到偏移7，c占用1字节
- 结构体总大小需是最大对齐值(4)的倍数，凑整到12
示例回答（<80字）：
结果为12字节。a偏移0占1，填充3使b对齐到4，b占4字节得偏移8；c占1字符偏移8，总大小9，向上取4的倍数得12。若使用 #pragma pack(1) 则变为6字节。
可能追问：
- 如果结构体包含 double 成员，对齐规则如何？
- 如何用 offsetof 宏验证？
- 位域成员的 sizeof 如何计算？
避坑提醒：
⚠️ 一定要先说明系统位数和默认对齐值，再计算。不要只背结果，要展示推导过程。位域成员不能取地址，注意区分。
🎯 面试问题 3
问题：请手写单链表反转函数，要求 O(1) 空间复杂度。
// 结点定义
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head);面试官考察点：
- 能否正确操作指针反转，避免丢失节点
- 是否理解迭代法与递归法的优缺点
- 边界条件（空链表、单节点）处理
回答框架：
- 定义三个指针：prev=NULL, curr=head, next=NULL
- 遍历 curr，先保存下一节点，再反转 curr->next 指向 prev
- 移动 prev 和 curr，循环直到 curr 为空
- 返回 prev 作为新头节点
示例回答（<100字）：
迭代法：三个指针 prev初始NULL，curr=head。每次先保存next=curr->next，将curr->next指向prev，然后prev=curr，curr=next。最后返回prev。时间复杂度O(n)，空间O(1)。注意空链表直接返回NULL。
可能追问：
- 递归法如何实现？递归的空间复杂度是多少？
- 反转前k个节点（类似LeetCode 92）
- 如果链表有环，反转会怎样？
避坑提醒：
🧨 迭代法最容易失误的是：在修改 curr->next 之前忘记保存下一节点，导致断链。面试时先在纸上画指针变化，再写代码。
💡 位运算高频补充： 置位 BIT_SET(x, n) = x | (1<>n) & 1。注意有符号数右移是算术移位，尤其在对负数操作时。