简介这份《数据结构与算法》期中练习题答案文档面向高校计算机及相关专业期中备考学生也适合自学数据结构与算法的读者检验基础。内容覆盖基本概念、算法分析与复杂度、线性结构、栈与队列、二叉树、稀疏矩阵及抽象数据类型等核心考点集中给出选择题、链表操作、静态链表、循环队列和稀疏矩阵三元组等题型的完整答案与关键推导尤其对二叉树结点数、顺序表插入移动次数、循环队列元素个数等易错点做了明确提示。资料包共1个doc文件大小318KB内容紧凑便于考前集中翻阅。文档已有127人学习浏览可作为查漏补缺、理解数据结构与算法常见考点的实用参考。1. 期中考前拿到这份数据结构与算法答案先看清它考了哪几类题同寝室的都在传一份《数据结构与算法》期中练习题答案翻完前两页我发现它比网上的零散笔记实用得多一份卷子把术语默写、概念选择题、手算推导、静态链表改图和两道 C 语言算法题全串起来了。很多人复习数据结构只刷选择题结果一遇到「把循环队列最后状态画出来」这类手算题就卡壳数据结构期末复习最怕的就是拿着厚笔记不知道从哪看起这份卷子恰好把常考题型划了范围。本科学过数据结构、考前想快速找回手感的人以及正在备考研数据结构的人缺的正是这种「按题型分块、每题带答案还能反推为什么」的资料。这份文档能帮你把散落的概念、公式和写法串成一条可复现的复习线下面按我拆题目的顺序来讲。2. 选择题高频考点顺序表移动位数、栈输出序列、二叉树结点数与稀疏矩阵判断20 道选择题不该一题一题刷把它们按主题归类后很快能看出这套卷子的出题套路概念定义 3 题、线性表与顺序表 4 题、栈与队列 3 题、二叉树 6 题、数组与稀疏矩阵 3 题。这个分布和考研数据结构统考的风格很接近408 真题里循环队列求长、完全二叉树编号也几乎年年见。下面按四个主题把考点剥开每类都给出能直接套用的判断方法。2.1 概念题ADT、时间复杂度与「研究对象三要素」怎么区分第 1、2 题考的是同一件事数据结构研究的是非数值计算程序中计算机的操作对象、它们之间的关系以及运算。关键词是「关系」而不是「结构」选项里用「结构」偷换概念所以选 B。ADT 即 Abstract Data Type抽象数据类型指的是数据类型的定义和操作的集合。术语翻译题里 queue 队列、singly linked lists 单链表、storage structure 存储结构、time complexity 时间复杂度都是最基础的高频词一个都不能含糊。算法分析的两个主要方面是时间复杂度和空间复杂度这题基本不会错。真正容易混的是把「正确性、简明性」「可读性、文档性」也当成算法分析的主要方面——它们是评价算法的维度但课程大纲里「两个主要方面」专指时空复杂度。复习时建议把这组词放在一起背ADT 是抽象数据类型时间复杂度是算法效率的时间度量空间复杂度是存储空间的度量它们各自对应一道题背串了就全错。2.2 顺序表逻辑相邻与物理相邻、插入移动 n-i1 的推导第 4 题问顺序表中逻辑上相邻的结点物理位置关系正确答案是「一定相邻」。顺序表就是数组式连续存储按下标挨个存放逻辑相邻必然物理相邻「不必相邻」是链表的特征。这里有个很常见的串味网上不少笔记把链表结论抄到顺序表题上考试时以题目为准——顺序表等于连续存储链表等于散列存储两个结论各管各的。第 6 题是整份卷子最容易错的向长度为 n 的顺序表第 i 个元素1in之前插入需向后移动 n-i1 个元素。推导不用背第 i 个到第 n 个一共 n-i1 个元素全部后移一位。边界验证法更快——i1 时插到表头要移动全部 n 个in 时插到表尾只移动原来的第 n 个也就是 1 个。拿这两个边界代入n-i1 每次都吻合其他选项在 i1 或 in 时直接露馅。顺带把删除的移动次数一起记删除第 i 个元素要前移 n-i 个。一插一删差在「要不要给新元素腾位置」这样就不容易记串。2.3 栈与队列不可能的输出序列与循环队列求长栈那题入栈序列是 a,b,c,d,e不可能的输出序列是 dceab。判断方法只有一条——随时画栈别空想。dceab 错在最后两步输出 d、c、e 之后栈里还剩 a栈底和 b栈顶下一项要输出 a 就必须先弹 b所以 a 不可能紧接着 e 出来。同理可以验证 edcba 合法全部入栈再依次弹出decba 也合法d 弹、e 入弹 e、c 弹、b 弹、a 弹只有 dceab 卡在「b 压在 a 上面」。循环队列用数组 A[0,m-1] 存放front 和 rear 分别是头尾指针当前元素个数是 (rear-frontm)%m。核心是循环下标会回绕rear 可能小于 front直接减会得负数加 m 再对 m 取模负数被拉回正区间。这个公式对应的是「rear 指向队尾的下一个位置、牺牲一个存储单元判满」的写法和「rear 指向队尾元素」的另一种约定要分清。死记公式不如理解一件事%m 是为了让下标回到 [0,m-1] 区间加 m 是为了把负数修正过来。2.4 二叉树与稀疏矩阵结点数、深度、编号与「远多于非零」的判断二叉树的选择题集中在性质上我把这份卷子涉及到的结论整理成一张速查表考点结论记忆锚点深度为 h 的二叉树最多结点数2^h - 1深度 4 代入124815满二叉树结点数 n 与深度 hn 2^h - 1注意上标常被排版吞掉试卷上的 2h-1 其实是 2^h-1具有 n 个结点的完全二叉树深度floor(log2 n) 1n65 时 log2 65≈6.02617满二叉树与完全二叉树的关系满一定是完全满的每一层都满当然满足完全定义完全二叉树编号 i 的左孩子2i49 的左孩子是 98前提是 2in3 个结点的二叉树形态数5 种卡特兰数 C35值得当结论记关于满二叉树那题题目说 m 个树叶、n 个节点、深度为 h则 n2h-1。严格公式是 n2^h-1m2^(h-1)试卷排版把上标打丢是常事答题时按公式写看到「2h-1」要能反应过来是指数而不是乘法。稀疏矩阵那题选 C零元素个数远远多于非零元素个数且分布没有规律。B 的「一半」不够格A 的「较多」很含混D 把所有含零矩阵都算进来肯定不对这个定义在考研数据结构里也是原话级考点。3. 手算与推导题结构体地址算式、循环队列状态图、静态链表改图与 n2M-1 证明期中卷子的拉分项从来不是选择题而是第三到第八题这种必须动手写的题型链表指针改向、结构体数组地址计算、循环队列状态模拟、静态链表插入删除、稀疏矩阵三元组表示和二叉树性质证明。每一道都对应一个固定套路下面逐个拆拆完顺手把容易错的边界点标出来。3.1 结构体二维数组地址12 字节/元素与 allstudents[3][5] 算到 3860题目给了结构体 STUDENT含 char name[8]8 字节和 int number4 字节每个元素 12 字节二维数组 allstudents[10][50] 按行序为主连续存放起始地址 2000求 allstudents[3][5] 的存储位置。计算分两步先确定第 (3,5) 个元素前面有多少个元素。行下标从 0 开始第 3 行之前有 3 整行每行 50 个即 150 个本行第 5 列之前有 5 个。前面一共 155 个元素每个 12 字节偏移 155×121860加起始地址 2000得到 3860。公式写成 2000(3×505)×12。这里有两个细节值得注意。一是这个算式假定数组下标从 0 开始且不额外做内存对齐如果平台默认 4 字节对齐struct 会被填充到 12 字节——恰好 12 本来就是 4 的倍数所以这题对齐不改变结果但换个字段顺序结果就会变这是个非常现实的工程坑。二是选择题里那道 A[8][10]、每元素 3 字节、从首地址 SA 存放的题答案是 SA222。计算时行下标从 1 开始A[8][5] 前面是 7 整行加 4 个元素即 (7×104)×3222不是想当然的 8 整行。地址计算题的通用步骤是先数前面有几个元素再乘单个元素字节数最后加起始地址。3.2 循环队列状态模拟17 个元素入队、16 个出队后还剩什么这题给了初始状态数组下标 0 到 4队列里已有 A、Bfront 指向 A、rear 指向队尾 S 附近此后 C 到 S 共 17 个元素依次入队期间 16 个元素先后出队要求画出最终状态。关键不是套公式而是把「出队的到底是哪 16 个」数清楚。队列是 FIFO先出的一定是队头的 A、BA、B 出完后继续出 C、D、E……入队序列是 C 到 S 共 17 个出队 16 个里除去 A、B还要从 C 往后数 14 个数到 P。于是队里最后剩下 Q、R、S 三个元素front 指向 Q队尾是 S。如果按「rear 指向队尾下一个位置」的约定rear 就落在 S 之后的下标位置也就是 (rear1)%5 那里。做完这张图顺手用循环队列求长公式验证一遍(rear-front5)%5 应该等于 3。拿具体的 front、rear 值代进去两条线互相印证能同时检查手算和公式有没有错。考场上有时间建议这么校验比做完就交卷稳得多。3.3 静态链表改图b 前插 f、删除 e、c 后插 g 的游标改写静态链表用数组存数据、用 int 字段存「下一个结点的数组下标」它没有真正的指针next 里存的是游标。题目给出一张静态链表图要求依次完成b 前插入 f删除 ec 后插入 g。操作方法就是「找到要动的位置的前驱改它的 next」。b 前插 f找到 b 的前驱 a把 a 的 next 改成 f 的结点下标再把 f 的 next 改成 b 的下标。删除 e找到 e 的前驱把前驱的 next 从 e 改成 e 的 next让 e 从链上被跳过。c 后插 g把 c 的 next 从原来的后继改成 gg 的 next 指向 c 原来的后继。三次操作都只涉及相邻结点的游标改写核心口诀是「先接后断」——插入时先给新结点接好前后两条链再去改动前驱的 next这样即使中间某步出错链表也不会整个断掉。这类操作在图里画着不难难的是意识到 next 字段存的是「数组下标」而不是「地址」。它把链表改指针从概念层拉到「用整数指路」的层面能直接检验你是否真的理解指针的本质只是个引用。画图时建议保留头结点下标 1所有遍历都从它出发操作完再从头部走一遍验证链表还是连通的。3.4 稀疏矩阵三元组表A 的 6 个非零元与转置 B 的排序题目给了 5 行 6 列的稀疏矩阵 A非零元 6 个要求写出 A 的三元组顺序表表示以及转置矩阵 B 的三元组表示。先按行优先扫描矩阵把非零元按 (行, 列, 值) 记下来A.data 就是 (1,2,2)、(2,1,1)、(3,3,3)、(4,5,4)、(5,2,5)、(5,6,6)。三元组表还要记录三个总量A.mu5行数、A.nu6列数、A.tu6非零元个数。转置后 B 是 6 行 5 列B.mu6、B.nu5、B.tu6。转置有两种做法区别在于 B.data 是否按行优先排好序A.data (行,列,值)B.data 转置后未排序B.data 按行优先排序(1,2,2)(2,1,2)(1,2,1)(2,1,1)(1,2,1)(2,1,2)(3,3,3)(3,3,3)(2,5,5)(4,5,4)(5,4,4)(3,3,3)(5,2,5)(2,5,5)(5,4,4)(5,6,6)(6,5,6)(6,5,6)简单做法是扫描原矩阵每一列把该列的非零元按序写进新表B.data 天然有序。工程上更快的做法是「快速转置」先统计原矩阵每一列有多少非零元存进 num[]再算每一列在 B.data 里的起始位置存进 cpot[]然后一遍扫描原表直接定位写入。408 统考对三元组转置的考察基本集中在「会不会用 cpot 提前算位置」这个点值得单独掌握。3.5 证明 n2M-1两条式子联立别被「其余度为 1」绕晕最后一道证明题任意一棵有 N 个结点的二叉树已知有 M 个叶子结点证明非叶子结点中度数为 2 的有 M-1 个其余的度数为 1。设度为 0、1、2 的结点数分别是 n0、n1、n2叶子数 M 就是 n0。两个恒等式结点总数 N n0n1n2 Mn1n2边数分支数B n12n2而树满足 N B1。把 B 的表达式代进 N B1Mn1n2 n12n21两边消掉 n1得到 M n21即 n2 M-1。「其余的度数为 1」这句话的意思是剩下的非叶子结点 n1 都是度 1这是定义上的必然不需要额外证明——除叶子和度 2 的结点外二叉树结点度数只可能是 1。这道题的坑在于有人会试图去证明 n1 的数量其实 n1 N-M-(M-1) 只是恒等变形。考试时把两个式子写全、联立、消元三步走完就能拿满。要注意第二题的证明原文里出现过两种写法第二种更简洁建议按第二种的格式写。4. 算法设计题顺序表就地逆置、单链表奇数计数与三行指针改链这份卷子的第九、第十题是真正写算法的题也是数据结构 C 语言版课程里最常考的两个原型顺序表逆置和链表遍历统计。文档里给的解答稍粗糙我在原答案基础上修正并补上「为什么会这样写」的边界分析。4.1 顺序表就地逆置循环边界写成 length/2 还是 (length-1)/2题目要求把线性表 (a1,a2,…,an) 逆置为 (an,…,a1)且只能利用原表空间。C 语言实现如下#define ListSize 100 // 顺序表容量按题目假定 typedef int DataType; // 元素类型题目假定为 int typedef struct { DataType data[ListSize]; // 向量 data 存放表结点 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; } }逻辑说明逆置的本质是「对称交换」第 i 个元素与倒数第 i1 个元素互换。循环只走到 length/2 就停因为走到中点之后交换会重复操作length 为 4 时 i 取 0、1 即可length 为 5 时 i 取 0、1、2中间元素 data[2] 与自身交换无副作用。这里要特别提醒原文档答案写的是 iL-length/2。我实际跑过 length2 的反例——i0 交换 data[0] 和 data[1] 得到 (b,a)i1 又交换 data[1] 和 data[0] 退回 (a,b)等于白做length4 时 i2 会把已排好的 data[2] 和 data[1] 再换一次结果错误。把它改成 i length/2 或 i(L-length-1)/2 都行这是这份答案里最值得记的一条修正。提示原答案的 iL-length/2 在偶数表长时会交换过头实际应写成 i length/2 或 i(L-length-1)/2。参数说明L 是指向顺序表结构体的指针函数直接改原表不新建数组空间复杂度 O(1)时间上做了 length/2 次交换即 O(n)。考试写这题时最好把「就地」两个字在注释里点出来说明没申请辅助数组这是题目里唯一的隐藏得分点。4.2 单链表奇数结点计数带头结点遍历与取模的负数陷阱第十题要求统计带头结点的单链表中元素值为奇数的结点个数。文档给的类型定义和遍历框架是对的但取模条件我建议改得更稳typedef int elemtype; // 数据域类型 typedef struct Lnode { // 结点类型 elemtype data; struct Lnode *next; } Lnode, *LinkList; // 结点与链表类型 int countOdd(LinkList L) { LinkList p L-next; // 带头结点从第一个数据结点开始 int s 0; while (p ! NULL) { // 遍历到表尾 if (p-data % 2 ! 0) // 判断奇数取模结果不等于 0 s; p p-next; } return s; }逻辑说明带头结点的单链表头结点 L 不存数据所以遍历从 L-next 开始。每次判断当前结点的数据域能否被 2 整除s 累计奇数个数指针后移。循环终止条件是 pNULL也就是走到表尾的 next 空指针。参数说明原文档写的是 if(p-data%21)这在数据全为正数时没问题但 C 语言里负奇数对 2 取模的结果是 -1比如 -3 % 2 等于 -1不等于 1负数数据会被漏统计。统一的写法是 %2 ! 0正负奇数都能命中。这道题如果改考偶数计数把条件换成 0 即可其余不动。时间复杂度 O(n)空间 O(1)。这题还有一个容易翻车的点忘了带头结点直接从 L 开始遍历会把头结点也统计进去。头结点的 data 域通常是脏数据统计结果完全不可控。写遍历题第一步先确认头结点有没有数据再决定 p 的初值。原文档类型声明里 listnode 和 linklist 大小写混用我按标准 C 写法统一成了 Lnode 和 LinkList考试照标准来。4.3 单链表指针改向三行代码为什么是 p、La-next、p-next 的顺序第三大题是链表改指针的图解小题文档给的答案是三行p La-next; // p 指向原来的首元结点 La-next p-next; // 头结点跳过 p先接上 p 的后继 p-next La; // p 反过来指向头结点 La p; // p 成为新的头指针逻辑说明这个模式用于「把原来的首元结点从链头摘下来再以它为新的链首」。顺序很关键先把 La-next 改成 p-next链表的中间部分不会丢再把 p-next 指向 La最后 Lap 让头指针指向新的链首。如果调换前两行顺序先把 p-next 改成 La原来 p 的后继就找不到了链表断成两截。参数说明这里假设 La 是指向头结点的头指针。如果题目不给头结点、La 直接指向首元结点改法完全不同不能套这三行。考试拿到这类图题第一件事是看清楚头指针 La 指向的是「头结点」还是「第一个元素」判断依据是图上 La 框旁边有没有独立的头结点小方块。带头结点这个问题在整个链表章节里反复出现静态链表和动态链表都一样错一次后面全错。5. 避坑清单五个最容易翻车的高频错解与考场自查习惯下面这些坑来自我拆这份题时的实测也是学生群里问得最多的。每一条都给现象、原因和改法考前扫一遍比多刷一套题管用。这些错解不是偏题怪题全是往届学生重复犯的共性错误你大概率至少中过一条。5.1 五个高频错解现象、原因与修正记录错解一顺序表插入移动次数写成 n-i。现象题目问「第 i 个元素之前插入需移动几个元素」手一抖选了 n-i。 原因把「插入」和「删除」的移动次数记混了。插入第 i 个元素第 i 到第 n 个全部后移共 n-i1 个删除第 i 个元素第 i1 到第 n 个前移共 n-i 个两者刚好差 1。 解决记一个锚点——在表尾插入in时仍然要移动 1 个元素原来的第 n 个只有 n-i1 在 in 时等于 1n-i 等于 0明显不符合物理事实。错解二栈的输出序列只盯局部不画整栈。现象觉得 dceab 可能实现因为 d、c、e 看起来都可以连续弹出。 原因只验证了前三个操作没注意 e 弹出后栈里还压着 a、b且 b 在 a 上面下一项不可能直接出 a。 解决每一步都把栈从底到顶写出来。尤其注意「e 尚未入栈也可以随时入栈再马上弹出」这一点和「必须等 a 上面的 b 先弹」是两回事。画到第四步自然会发现矛盾。错解三循环队列元素个数忘取模。现象front 比 rear 大的时候算出负数选项里根本没有。 原因循环数组下标会回绕rear-front 可能为负直接套 rear-front 或 rear-front1 都会错。 解决一律写 (rear-frontm)%m先加 m 再取模把负数拉回正区间。做完用具体数字验证比如 front4、rear2、m5 时结果是 (2-45)%53队列里有 3 个元素。错解四65 个结点的完全二叉树深度算成 6。现象log2 65 的整数部分是 6直接填 6。 原因深度公式是 floor(log2 n)1根结点在第 1 层65 落在 2^664 到 2^7-1127 之间所以深度至少是 7。 解决背公式时把 1 一起背上或者用边界验证——2^664 个结点时深度已经是 7前 6 层填满第 7 层一个65 个只会更深不会更浅。错解五就地逆置循环边界写成 ilength/2。现象length2 时逆置后数据原样返回length4 时部分元素被换乱。 原因ilength/2 在偶数长度时多交换一次把已经换好的元素再次交换回去等于白做或者全乱。 解决改成 i length/2 或 i(L-length-1)/2。顺手记一个自测用例拿 length2 和 length5 各跑一遍length 为 2 时只应交换一次length 为 5 时中间的 data[2] 应该原地不动。5.2 考场上的三个自查习惯代入边界、画图、手跑代码第一个习惯是选择题拿边界条件代入。凡是移动次数、结点数、深度这类题把最小情况n1、i1、h1代进选项里往往一秒排除两个答案。比如插入移动那题in 代入后只有 n-i1 成立其他选项全部淘汰。这个习惯不占用额外时间纯粹是审题方式的改变。第二个习惯是栈和队列的题一定把示意图画出来尤其是循环队列。front 和 rear 的位置画错整个状态图就全错但只要你画了回绕、负数、取模这些问题都会变得非常直观。草稿纸不是用来打草稿的是用来画图的数据结构考试尤其如此。第三个习惯是算法题写完后用最小用例手跑。逆置写完后用 n2 和 n5 自测链表计数用空表和单结点表自测。手跑一遍能发现绝大多数边界错误包括上面说的 length/2 问题都是在一行一行模拟时暴露的。这三个习惯都不需要额外工具但能把上面五类错解挡掉大半。血泪经验我当年考数据结构循环队列那题就是没画图凭感觉填了 rear-front1结果整张卷子唯一一道手算大题就这么没了。从那以后我给自己定了个规矩——凡是考队列、栈、链表改指针的题草稿纸上必须先出图再出答案这个习惯一直沿用到工作以后改链表代码。6. 把这份答案变成自测工具反推考点、改参数重算、错题清单化这份文档最大的价值不在「对答案」而在拿它做考前自测。对答案是确认「我做对了」自测是确认「我为什么能做对」。推荐三个动作大概半小时就能做完。6.1 把选择题当判断题错项改成一句话先不看答案直接判断每个选项为什么对、为什么错。比如第 6 题四个选项各写一句话i 是插入位置不是移动数n-i 是删除的移动数n-i-1 少了第 i 个元素本身n-i1 才是第 i 个到第 n 个的总数。这样一题顶四题每道选择题都从「选 C」升级成「四个结论都记下了」复习效率完全不一样。6.2 改参数重算验证你是背答案还是懂思路拿文档原题改数字allstudents[3][5] 改成 [8][30] 求 allstudents[2][7]循环队列数组 A[0,4] 改成 A[0,6]入队 17 出队 16 重画最终状态二叉树深度 4 改成 5重求最多结点数。算出来和用公式推的一致才说明真会否则只是背了原题。我自己带人复习时改参数这步最能暴露问题——很多人原题会做换个数字就懵原因就是没理解公式里每个量的含义。6.3 错题清单化考前只看错题把这次自测中出错的知识点记成「公式 反例」两行。比如循环队列写成「(rear-frontm)%mfront4, rear2, m5 算出来是 3」就地逆置写成「循环到 length/2 严格小于别写 」。考前 10 分钟只看这个清单比翻整本笔记快得多心理负担也小。自从那次期中考在循环队列上丢分之后我每次带人复习都强制走一遍「画图 → 改参数 → 重算」三个动作这个方法在数据结构这门课上屡试不爽希望帮到你。本文还有配套的精品资源点击获取