简介《数据结构与算法期中练习题答案》是一份面向高校计算机专业学生、用于期中复习与查漏补缺的题库解答文档围绕数据结构基本概念与算法分析展开覆盖时间复杂度与空间复杂度、抽象数据类型、顺序表与链表、栈和队列、二叉树及完全二叉树特性、稀疏矩阵三元组表示等高频考点。资源包共1个文件为约318KB的doc格式文档可直接打开查阅便于对照练习与考前集中记忆。文档在客观题之外还包含线性链表指针修改、C语言结构体数组存储位置计算、循环队列状态模拟、静态链表插入删除以及稀疏矩阵转置等应用型题目答案能帮助读者理解理论知识的具体用法。已有127人学习下载适合正在学习《数据结构与算法》课程并希望快速核对答案、掌握解题思路的同学。1. 从一套期中题看数据结构复习的优先级期中考前最有效率的事不是翻教材从头看一遍而是拿一套往年题把「容易记混的结论」一次性过掉。这份《数据结构与算法》期中练习题答案覆盖了线性表、栈、队列、二叉树和稀疏矩阵五个模块题型风格和考研数据结构的选择题很接近适合在考前两三天用来做记忆校准。真正值得留意的不是那些定义题而是几处边角顺序表第 i 个位置插入要移动 n-i1 个元素而不是 n-i 个循环队列元素个数必须用 (rear-frontm)%m 补正顺序表就地逆置的循环边界处理不好时偶数长度下会多交换一次把结果改坏。这套题的答案都给了但收益在于自己重新推一遍尤其是链表的指针操作题判卷时最容易丢分的反而是最基础的边界条件。2. 顺序表与单链表从移动次数到指针翻转这章的题目集中在两组一组是顺序表的插入移动次数和二维数组寻址另一组是单链表的指针操作。它们考察的是同一个能力——能不能把「逻辑相邻」和「物理相邻」区分清楚再落实到具体代码上。2.1 顺序表插入为什么移动 n-i1 个元素顺序表用数组存储逻辑上相邻的元素在物理位置上一定相邻这是它和链表最本质的区别。Insert 操作要在第 i 个元素之前插入新元素下标从 i 到 n 的元素都得往后挪一位。这里 i 从 1 开始计数所以需要移动的是第 i 个到第 n 个一共 n-i1 个。边界情况很好验证插入到第 1 个元素之前所有 n 个元素都要后移插入到第 n 个元素之后也就是表尾追加移动 0 个。平均来看在等概率插入到任意位置的前提下移动次数是 n/2所以顺序表插入的时间复杂度是 O(n)。很多复习资料会把「是否需要移动」和「移动多少个」混在一起记选择题第 6 题选 D 的原因就在这里。2.2 单链表前插三行代码的顺序不能反大题第 1 题给了一个经典场景q 是 p 的前驱要在 q 和 p 之间插入 s。正确操作是q-next s; s-next p;两条赋值语句的顺序很关键。如果先执行s-next q-next这时候 q-next 还是 p效果等价但如果先写q-next sq 的下一个节点就从 p 变成了 s原来的 p 节点就再也找不到了链表在这里断掉。稳妥的写法是先接后链s-next q-next; q-next s;这种写法不依赖临时变量也不会丢失后继。选择第 7 题里干扰项 A 和 D 都是把 next 指针接到了错误的位置上本质上是没有意识到「先改前驱的 next原后继会丢失」这个事实。2.3 结构数组寻址12 字节一步算到位题目里的 struct STUDENT 包含一个 8 字节的字符数组和一个 4 字节的 int每个元素占用 12 字节。二维数组 allstudents[10][50] 按行优先存储起始地址 SA 2000那么 allstudents[i][j] 的地址就是SA (i * 50 j) * 12i * 50 j 是它前面有多少个元素再乘上每个元素的字节数。代入 i 3j 52000 (3 * 50 5) * 12 2000 155 * 12 3860最常见的错误是把二维数组的第二维 50 写成第一维 10或者漏乘元素大小直接加下标。另一个隐蔽的坑是 C 语言的结构体内存对齐这里 char[8] 结束于偏移 8int 天然对齐所以结构体大小恰好是 12如果字段顺序调整成 int 在前、char 在后在 64 位平台上实际占用的字节数也可能仍然一样但换到其他字段组合时就要用 sizeof 确认。2.4 就地逆置偶数长度下的循环边界陷阱这道题要求把顺序表 (a1, a2, ..., an) 逆置为 (an, ..., a1)并且只能用原表空间。思路是交换首尾对称位置前半段和后半段一一对调。#define ListSize 100 typedef int DataType; typedef struct { DataType data[ListSize]; int length; } Seqlist; void ReverseList(Seqlist *L) { DataType temp; int i; for (i 0; i L-length / 2; i) { temp L-data[i]; L-data[i] L-data[L-length - 1 - i]; L-data[L-length - 1 - i] temp; } }L-length是当前表长度最后一个元素的下标是 length-1。外层循环只需要做 length/2 次交换因为中间元素在奇数长度下不需要动。注意循环条件必须是i L-length / 2如果写成i L-length / 2奇数长度没事但偶数长度会多交换一次对称对把已经逆置好的结果又换回去。拿长度为 4 的表演示一下错误条件造成的后果i交换对数组状态0data[0] ↔ data[3]a3 a1 a2 a01data[1] ↔ data[2]a3 a2 a1 a02data[2] ↔ data[1]a3 a1 a2 a0i 2 时把 data[1] 和 data[2] 又交换了一次最终结果变成 a3 a1 a2 a0。参考实现里这个 bug 很常见因为长度是奇数时测试用例恰好能通过。逆置的时间复杂度是 O(n)额外空间 O(1)也符合「就地」的要求。3. 栈与队列从序列判定到指针推算栈和队列的题在期中卷里几乎必出。出栈序列的合法性判定考的是对后进先出的直觉循环队列的元素个数公式考的是对取模运算的理解静态链表则考察在数组上模拟指针的能力。3.1 出栈序列 dceab 为什么不可能入栈序列是 a, b, c, d, e题目问哪个出栈序列不可能。用一张表模拟 dceab 的执行过程步骤操作栈底→顶输出1a, b, c, d 依次入栈d 出栈a, b, cd2c 出栈a, bc3e 入栈并出栈a, be4下一个要求 a 出栈a, b栈顶是 b不可能关键在第 4 步e 出栈后栈里从底到顶是 a、b下一个要求输出 a但 a 被 b 压着必须先出 b 才能出 a。所以 dceab 不可能是合法输出序列。判断这类问题最直接的方法是模拟每次只关注「当前栈顶是否能匹配输出序列的下一个元素」。另一种技巧是如果某个元素 x 先出栈那么所有在 x 之前入栈且仍在栈内的元素出栈顺序必须严格符合栈的逆序。这个规则对 a* 算法题和括号匹配题都通用。3.2 循环队列取模公式的两个方向循环队列把数组当作环形缓冲区关键在于 front 和 rear 的移动都要对 m 取模。元素个数不能直接相减因为 rear 可能已经绕过数组尾部回到前面。情形条件元素个数rear 在 front 后面rear ≥ frontrear - frontrear 绕过数组尾部rear frontrear - front m统一写法任意(rear - front m) % m#define MAXSIZE 6 typedef struct { int data[MAXSIZE]; int front, rear; } SqQueue; int QueueLength(SqQueue Q) { return (Q.rear - Q.front MAXSIZE) % MAXSIZE; } int EnQueue(SqQueue *Q, int x) { if ((Q-rear 1) % MAXSIZE Q-front) return 0; /* 队满 */ Q-data[Q-rear] x; Q-rear (Q-rear 1) % MAXSIZE; return 1; } int DeQueue(SqQueue *Q, int *x) { if (Q-front Q-rear) return 0; /* 队空 */ *x Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; }这套实现牺牲了一个存储单元来区分队空和队满front rear 表示空(rear 1) % MAXSIZE front表示满。入队时 rear 后移出队时 front 后移都做取模。题目里 17 个元素进队、16 个元素出队等效于队列中净增加 1 个元素rear 的最终位置等于初始位置加 17 再取模front 的最终位置等于初始位置加 16 再取模。原题的图 OCR 之后已经看不清但这个推算方法在考场上可以直接写出来答案图填完后再用元素个数公式验算一遍即可。3.3 静态链表用游标维护逻辑关系静态链表的每个节点依然有数据域和指针域只不过指针换成了数组下标。题目要求对序列 (a, b, c, d, e) 依次完成在 b 前插入 f删除 e在 c 后插入 g。操作游标修改b 前插入 f找到 a 和 bf 的游标指向 ba 的游标指向 f删除 e找到 dd 的游标直接指向 e 原来指向的地址e 归还空闲链表c 后插入 gg 的游标指向 dc 的游标指向 g核心代码只有两行的变体def insert_after(prev_idx, new_idx, nodes): nodes[new_idx].cur nodes[prev_idx].cur nodes[prev_idx].cur new_idx def delete_next(prev_idx, nodes): del_idx nodes[prev_idx].cur nodes[prev_idx].cur nodes[del_idx].cur静态链表在嵌入式和无指针环境下仍然有实用价值核心难点不是插入删除本身而是空闲链表的管理。删除的节点必须归还到空闲链表否则下次申请新节点时无从取用。这一点和动态内存管理的思路完全一致只是这里要手动维护。4. 二叉树与稀疏矩阵性质、编号和压缩存储二叉树这部分的考点集中在性质推导和编号规律上稀疏矩阵则考三元组的压缩表示和转置。两者都有一个共同特点结论是有限的但推导思路需要真正理解。4.1 深度、节点数和满二叉树深度为 h 的二叉树第 k 层最多有 2^(k-1) 个结点所以整个树最多有 2^h - 1 个结点。深度为 4 的时候就是 2^4 - 1 15选择第 12 题答案 B。满二叉树的每一层都达到最大节点数因此 n 2^h - 1叶子节点数 m 2^(h-1)两个式子联立得到 n 2m - 1。文档里第 13 题答案写成 n 2h - 1这里的上标在 OCR 时丢了正确关系是 n 2^h - 1 或 n 2m - 1。满二叉树一定是完全二叉树但完全二叉树不一定是满的。这个关系的方向容易记反判断时只要看「最后一层是否从右往左缺节点」完全二叉树最后一层只能从左往右连续缺不能中间空洞。4.2 完全二叉树的编号和孩子定位完全二叉树按层序编号后节点的编号规律非常整齐编号 i 的节点左孩子是 2i如果存在右孩子是 2i1父节点是 floor(i/2)。编号 49 的节点左孩子就是 98选择第 16 题答案 B。如果节点总数是 100编号 49 的右孩子是 99也在这个范围内而编号 50 的节点左孩子编号是 100刚好是最后一个节点。完全二叉树的深度可以用公式 floor(log2 n) 1 直接算出65 个结点时深度为 7。另外3 个结点能组成多少种不同形态的二叉树是一个容易忽略的考点答案是 5 种对应卡特兰数 C(3) 5。4.3 叶子节点数 m 与度数为 2 的节点数的证明这题要求证明N 个结点的二叉树有 M 个叶子节点则非叶子节点中度为 2 的节点有 M-1 个。设度为 0、1、2 的节点数分别为 n0、n1、n2已知 n0 M。节点总数满足N M n1 n2二叉树的分支数 B 等于度为 1 和度为 2 的节点贡献的分支之和即 B n1 2·n2。同时每个节点除根外都有且仅有一个分支指向它所以 N B 1。联立M n1 n2 n1 2·n2 1 M n2 1 n2 M - 1推导的关键是「边数等于节点数减 1」这个等式。它不依赖二叉树是满的还是完全的对任意二叉树都成立。剩下的非叶子节点自然是度为 1 的节点。4.4 稀疏矩阵的三元组与快速转置稀疏矩阵的定义是零元素个数远远多于非零元素且分布没有规律。压缩存储时只记录非零元素的行号、列号和值也就是三元组 (i, j, v)。以题中的 5×6 矩阵为例6 个非零元素按行优先排列ijv122211323454525566转置后矩阵变成 6×5非零元素的行列互换但顺序必须重新按行排列否则后续的矩阵运算没法做。转置后的三元组表ijv121212233255544656朴素做法是遍历原三元组表按列号排序填入复杂度 O(tu·nu)。快速转置的思路是先统计原矩阵每一列的非零元素个数得到转置后每一行的起始存放位置再一次性填入// 假设 A.data 已按行优先存储num[col] 统计 A 中第 col 列的非零元个数 // cpot[col] 表示转置后第 col 行第一个非零元在 B.data 中的下标 for (col 1; col A.nu; col) { cpot[col] cpot[col - 1] num[col - 1]; } for (t 1; t A.tu; t) { col A.data[t].j; q cpot[col]; B.data[q].i A.data[t].j; B.data[q].j A.data[t].i; B.data[q].v A.data[t].v; }cpot数组是关键它记录的是每个列号在转置表中的起始位置每填入一个元素就自增一次。这样一趟就能完成转置时间复杂度降到 O(nu tu)空间上只多了一个长度 nu 的数组。这个思路在后续学习图的邻接表转置时还会再次遇到。5. 带头结点单链表统计奇数的鲁棒写法最后一道算法题是统计带头结点的单链表中值为奇数的节点个数。基础实现很直接从第一个数据节点开始遍历判断每个节点的 data 是否为奇数。#include stdio.h #include stdlib.h typedef int elemtype; typedef struct Lnode { elemtype data; struct Lnode *next; } Lnode, *LinkList; int count_odd(LinkList L) { int s 0; Lnode *p L-next; /* 跳过带头结点 */ while (p ! NULL) { if ((p-data 1) ! 0) { /* 位运算判断奇偶 */ s; } p p-next; } return s; } int main(void) { LinkList L (LinkList)malloc(sizeof(Lnode)); L-next NULL; int vals[] {-3, 2, 5, -7, 8}; int n sizeof(vals) / sizeof(int); for (int i n - 1; i 0; i--) { /* 头插法构建链表 */ Lnode *t (Lnode*)malloc(sizeof(Lnode)); t-data vals[i]; t-next L-next; L-next t; } printf(%d\n, count_odd(L)); return 0; }这段代码里p L-next跳过的是头结点头结点本身不存有效数据只有下一节点的指针。遍历终止条件是 p 为 NULL也就是链表尾部。时间复杂度 O(n)额外空间 O(1)。测试数据{-3, 2, 5, -7, 8}包含两个负奇数期望输出 3。多数参考实现会用p-data % 2 1判断奇偶这个写法在 C 语言里有一个隐蔽的缺陷C99 规定负数取模的符号与被除数一致所以 -3 % 2 的结果是 -1 而不是 1负奇数会被全部漏掉。题目虽然没要求处理负数但数据域的类型是 int谁能保证链表里不会出现负数改用位运算(p-data 1) ! 0判断奇偶在常见的补码平台上对正数和负数的判定结果完全一致-3 1 等于 15 1 等于 18 1 等于 0。把判断条件从取模改成位运算后这个统计函数在负数场景下也能正确工作这也是工程实现和教材代码之间最常见的差异之一。本文还有配套的精品资源点击获取
数据结构期中复习：顺序表、链表、栈队列与二叉树考点解析
简介《数据结构与算法期中练习题答案》是一份面向高校计算机专业学生、用于期中复习与查漏补缺的题库解答文档围绕数据结构基本概念与算法分析展开覆盖时间复杂度与空间复杂度、抽象数据类型、顺序表与链表、栈和队列、二叉树及完全二叉树特性、稀疏矩阵三元组表示等高频考点。资源包共1个文件为约318KB的doc格式文档可直接打开查阅便于对照练习与考前集中记忆。文档在客观题之外还包含线性链表指针修改、C语言结构体数组存储位置计算、循环队列状态模拟、静态链表插入删除以及稀疏矩阵转置等应用型题目答案能帮助读者理解理论知识的具体用法。已有127人学习下载适合正在学习《数据结构与算法》课程并希望快速核对答案、掌握解题思路的同学。1. 从一套期中题看数据结构复习的优先级期中考前最有效率的事不是翻教材从头看一遍而是拿一套往年题把「容易记混的结论」一次性过掉。这份《数据结构与算法》期中练习题答案覆盖了线性表、栈、队列、二叉树和稀疏矩阵五个模块题型风格和考研数据结构的选择题很接近适合在考前两三天用来做记忆校准。真正值得留意的不是那些定义题而是几处边角顺序表第 i 个位置插入要移动 n-i1 个元素而不是 n-i 个循环队列元素个数必须用 (rear-frontm)%m 补正顺序表就地逆置的循环边界处理不好时偶数长度下会多交换一次把结果改坏。这套题的答案都给了但收益在于自己重新推一遍尤其是链表的指针操作题判卷时最容易丢分的反而是最基础的边界条件。2. 顺序表与单链表从移动次数到指针翻转这章的题目集中在两组一组是顺序表的插入移动次数和二维数组寻址另一组是单链表的指针操作。它们考察的是同一个能力——能不能把「逻辑相邻」和「物理相邻」区分清楚再落实到具体代码上。2.1 顺序表插入为什么移动 n-i1 个元素顺序表用数组存储逻辑上相邻的元素在物理位置上一定相邻这是它和链表最本质的区别。Insert 操作要在第 i 个元素之前插入新元素下标从 i 到 n 的元素都得往后挪一位。这里 i 从 1 开始计数所以需要移动的是第 i 个到第 n 个一共 n-i1 个。边界情况很好验证插入到第 1 个元素之前所有 n 个元素都要后移插入到第 n 个元素之后也就是表尾追加移动 0 个。平均来看在等概率插入到任意位置的前提下移动次数是 n/2所以顺序表插入的时间复杂度是 O(n)。很多复习资料会把「是否需要移动」和「移动多少个」混在一起记选择题第 6 题选 D 的原因就在这里。2.2 单链表前插三行代码的顺序不能反大题第 1 题给了一个经典场景q 是 p 的前驱要在 q 和 p 之间插入 s。正确操作是q-next s; s-next p;两条赋值语句的顺序很关键。如果先执行s-next q-next这时候 q-next 还是 p效果等价但如果先写q-next sq 的下一个节点就从 p 变成了 s原来的 p 节点就再也找不到了链表在这里断掉。稳妥的写法是先接后链s-next q-next; q-next s;这种写法不依赖临时变量也不会丢失后继。选择第 7 题里干扰项 A 和 D 都是把 next 指针接到了错误的位置上本质上是没有意识到「先改前驱的 next原后继会丢失」这个事实。2.3 结构数组寻址12 字节一步算到位题目里的 struct STUDENT 包含一个 8 字节的字符数组和一个 4 字节的 int每个元素占用 12 字节。二维数组 allstudents[10][50] 按行优先存储起始地址 SA 2000那么 allstudents[i][j] 的地址就是SA (i * 50 j) * 12i * 50 j 是它前面有多少个元素再乘上每个元素的字节数。代入 i 3j 52000 (3 * 50 5) * 12 2000 155 * 12 3860最常见的错误是把二维数组的第二维 50 写成第一维 10或者漏乘元素大小直接加下标。另一个隐蔽的坑是 C 语言的结构体内存对齐这里 char[8] 结束于偏移 8int 天然对齐所以结构体大小恰好是 12如果字段顺序调整成 int 在前、char 在后在 64 位平台上实际占用的字节数也可能仍然一样但换到其他字段组合时就要用 sizeof 确认。2.4 就地逆置偶数长度下的循环边界陷阱这道题要求把顺序表 (a1, a2, ..., an) 逆置为 (an, ..., a1)并且只能用原表空间。思路是交换首尾对称位置前半段和后半段一一对调。#define ListSize 100 typedef int DataType; typedef struct { DataType data[ListSize]; int length; } Seqlist; void ReverseList(Seqlist *L) { DataType temp; int i; for (i 0; i L-length / 2; i) { temp L-data[i]; L-data[i] L-data[L-length - 1 - i]; L-data[L-length - 1 - i] temp; } }L-length是当前表长度最后一个元素的下标是 length-1。外层循环只需要做 length/2 次交换因为中间元素在奇数长度下不需要动。注意循环条件必须是i L-length / 2如果写成i L-length / 2奇数长度没事但偶数长度会多交换一次对称对把已经逆置好的结果又换回去。拿长度为 4 的表演示一下错误条件造成的后果i交换对数组状态0data[0] ↔ data[3]a3 a1 a2 a01data[1] ↔ data[2]a3 a2 a1 a02data[2] ↔ data[1]a3 a1 a2 a0i 2 时把 data[1] 和 data[2] 又交换了一次最终结果变成 a3 a1 a2 a0。参考实现里这个 bug 很常见因为长度是奇数时测试用例恰好能通过。逆置的时间复杂度是 O(n)额外空间 O(1)也符合「就地」的要求。3. 栈与队列从序列判定到指针推算栈和队列的题在期中卷里几乎必出。出栈序列的合法性判定考的是对后进先出的直觉循环队列的元素个数公式考的是对取模运算的理解静态链表则考察在数组上模拟指针的能力。3.1 出栈序列 dceab 为什么不可能入栈序列是 a, b, c, d, e题目问哪个出栈序列不可能。用一张表模拟 dceab 的执行过程步骤操作栈底→顶输出1a, b, c, d 依次入栈d 出栈a, b, cd2c 出栈a, bc3e 入栈并出栈a, be4下一个要求 a 出栈a, b栈顶是 b不可能关键在第 4 步e 出栈后栈里从底到顶是 a、b下一个要求输出 a但 a 被 b 压着必须先出 b 才能出 a。所以 dceab 不可能是合法输出序列。判断这类问题最直接的方法是模拟每次只关注「当前栈顶是否能匹配输出序列的下一个元素」。另一种技巧是如果某个元素 x 先出栈那么所有在 x 之前入栈且仍在栈内的元素出栈顺序必须严格符合栈的逆序。这个规则对 a* 算法题和括号匹配题都通用。3.2 循环队列取模公式的两个方向循环队列把数组当作环形缓冲区关键在于 front 和 rear 的移动都要对 m 取模。元素个数不能直接相减因为 rear 可能已经绕过数组尾部回到前面。情形条件元素个数rear 在 front 后面rear ≥ frontrear - frontrear 绕过数组尾部rear frontrear - front m统一写法任意(rear - front m) % m#define MAXSIZE 6 typedef struct { int data[MAXSIZE]; int front, rear; } SqQueue; int QueueLength(SqQueue Q) { return (Q.rear - Q.front MAXSIZE) % MAXSIZE; } int EnQueue(SqQueue *Q, int x) { if ((Q-rear 1) % MAXSIZE Q-front) return 0; /* 队满 */ Q-data[Q-rear] x; Q-rear (Q-rear 1) % MAXSIZE; return 1; } int DeQueue(SqQueue *Q, int *x) { if (Q-front Q-rear) return 0; /* 队空 */ *x Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; }这套实现牺牲了一个存储单元来区分队空和队满front rear 表示空(rear 1) % MAXSIZE front表示满。入队时 rear 后移出队时 front 后移都做取模。题目里 17 个元素进队、16 个元素出队等效于队列中净增加 1 个元素rear 的最终位置等于初始位置加 17 再取模front 的最终位置等于初始位置加 16 再取模。原题的图 OCR 之后已经看不清但这个推算方法在考场上可以直接写出来答案图填完后再用元素个数公式验算一遍即可。3.3 静态链表用游标维护逻辑关系静态链表的每个节点依然有数据域和指针域只不过指针换成了数组下标。题目要求对序列 (a, b, c, d, e) 依次完成在 b 前插入 f删除 e在 c 后插入 g。操作游标修改b 前插入 f找到 a 和 bf 的游标指向 ba 的游标指向 f删除 e找到 dd 的游标直接指向 e 原来指向的地址e 归还空闲链表c 后插入 gg 的游标指向 dc 的游标指向 g核心代码只有两行的变体def insert_after(prev_idx, new_idx, nodes): nodes[new_idx].cur nodes[prev_idx].cur nodes[prev_idx].cur new_idx def delete_next(prev_idx, nodes): del_idx nodes[prev_idx].cur nodes[prev_idx].cur nodes[del_idx].cur静态链表在嵌入式和无指针环境下仍然有实用价值核心难点不是插入删除本身而是空闲链表的管理。删除的节点必须归还到空闲链表否则下次申请新节点时无从取用。这一点和动态内存管理的思路完全一致只是这里要手动维护。4. 二叉树与稀疏矩阵性质、编号和压缩存储二叉树这部分的考点集中在性质推导和编号规律上稀疏矩阵则考三元组的压缩表示和转置。两者都有一个共同特点结论是有限的但推导思路需要真正理解。4.1 深度、节点数和满二叉树深度为 h 的二叉树第 k 层最多有 2^(k-1) 个结点所以整个树最多有 2^h - 1 个结点。深度为 4 的时候就是 2^4 - 1 15选择第 12 题答案 B。满二叉树的每一层都达到最大节点数因此 n 2^h - 1叶子节点数 m 2^(h-1)两个式子联立得到 n 2m - 1。文档里第 13 题答案写成 n 2h - 1这里的上标在 OCR 时丢了正确关系是 n 2^h - 1 或 n 2m - 1。满二叉树一定是完全二叉树但完全二叉树不一定是满的。这个关系的方向容易记反判断时只要看「最后一层是否从右往左缺节点」完全二叉树最后一层只能从左往右连续缺不能中间空洞。4.2 完全二叉树的编号和孩子定位完全二叉树按层序编号后节点的编号规律非常整齐编号 i 的节点左孩子是 2i如果存在右孩子是 2i1父节点是 floor(i/2)。编号 49 的节点左孩子就是 98选择第 16 题答案 B。如果节点总数是 100编号 49 的右孩子是 99也在这个范围内而编号 50 的节点左孩子编号是 100刚好是最后一个节点。完全二叉树的深度可以用公式 floor(log2 n) 1 直接算出65 个结点时深度为 7。另外3 个结点能组成多少种不同形态的二叉树是一个容易忽略的考点答案是 5 种对应卡特兰数 C(3) 5。4.3 叶子节点数 m 与度数为 2 的节点数的证明这题要求证明N 个结点的二叉树有 M 个叶子节点则非叶子节点中度为 2 的节点有 M-1 个。设度为 0、1、2 的节点数分别为 n0、n1、n2已知 n0 M。节点总数满足N M n1 n2二叉树的分支数 B 等于度为 1 和度为 2 的节点贡献的分支之和即 B n1 2·n2。同时每个节点除根外都有且仅有一个分支指向它所以 N B 1。联立M n1 n2 n1 2·n2 1 M n2 1 n2 M - 1推导的关键是「边数等于节点数减 1」这个等式。它不依赖二叉树是满的还是完全的对任意二叉树都成立。剩下的非叶子节点自然是度为 1 的节点。4.4 稀疏矩阵的三元组与快速转置稀疏矩阵的定义是零元素个数远远多于非零元素且分布没有规律。压缩存储时只记录非零元素的行号、列号和值也就是三元组 (i, j, v)。以题中的 5×6 矩阵为例6 个非零元素按行优先排列ijv122211323454525566转置后矩阵变成 6×5非零元素的行列互换但顺序必须重新按行排列否则后续的矩阵运算没法做。转置后的三元组表ijv121212233255544656朴素做法是遍历原三元组表按列号排序填入复杂度 O(tu·nu)。快速转置的思路是先统计原矩阵每一列的非零元素个数得到转置后每一行的起始存放位置再一次性填入// 假设 A.data 已按行优先存储num[col] 统计 A 中第 col 列的非零元个数 // cpot[col] 表示转置后第 col 行第一个非零元在 B.data 中的下标 for (col 1; col A.nu; col) { cpot[col] cpot[col - 1] num[col - 1]; } for (t 1; t A.tu; t) { col A.data[t].j; q cpot[col]; B.data[q].i A.data[t].j; B.data[q].j A.data[t].i; B.data[q].v A.data[t].v; }cpot数组是关键它记录的是每个列号在转置表中的起始位置每填入一个元素就自增一次。这样一趟就能完成转置时间复杂度降到 O(nu tu)空间上只多了一个长度 nu 的数组。这个思路在后续学习图的邻接表转置时还会再次遇到。5. 带头结点单链表统计奇数的鲁棒写法最后一道算法题是统计带头结点的单链表中值为奇数的节点个数。基础实现很直接从第一个数据节点开始遍历判断每个节点的 data 是否为奇数。#include stdio.h #include stdlib.h typedef int elemtype; typedef struct Lnode { elemtype data; struct Lnode *next; } Lnode, *LinkList; int count_odd(LinkList L) { int s 0; Lnode *p L-next; /* 跳过带头结点 */ while (p ! NULL) { if ((p-data 1) ! 0) { /* 位运算判断奇偶 */ s; } p p-next; } return s; } int main(void) { LinkList L (LinkList)malloc(sizeof(Lnode)); L-next NULL; int vals[] {-3, 2, 5, -7, 8}; int n sizeof(vals) / sizeof(int); for (int i n - 1; i 0; i--) { /* 头插法构建链表 */ Lnode *t (Lnode*)malloc(sizeof(Lnode)); t-data vals[i]; t-next L-next; L-next t; } printf(%d\n, count_odd(L)); return 0; }这段代码里p L-next跳过的是头结点头结点本身不存有效数据只有下一节点的指针。遍历终止条件是 p 为 NULL也就是链表尾部。时间复杂度 O(n)额外空间 O(1)。测试数据{-3, 2, 5, -7, 8}包含两个负奇数期望输出 3。多数参考实现会用p-data % 2 1判断奇偶这个写法在 C 语言里有一个隐蔽的缺陷C99 规定负数取模的符号与被除数一致所以 -3 % 2 的结果是 -1 而不是 1负奇数会被全部漏掉。题目虽然没要求处理负数但数据域的类型是 int谁能保证链表里不会出现负数改用位运算(p-data 1) ! 0判断奇偶在常见的补码平台上对正数和负数的判定结果完全一致-3 1 等于 15 1 等于 18 1 等于 0。把判断条件从取模改成位运算后这个统计函数在负数场景下也能正确工作这也是工程实现和教材代码之间最常见的差异之一。本文还有配套的精品资源点击获取