数据结构期中卷答案精讲：从概念到代码的自查清单

简介这份文档资料是《数据结构与算法》期中练习题的配套答案面向正在学习数据结构课程的高校学生与备考者帮助其核对解题思路、巩固核心考点。内容覆盖基本概念、线性结构、栈与队列、二叉树、算法设计及稀疏矩阵等模块包含选择题、链表指针操作、结构体存储位置计算、循环队列状态推演、静态链表插入删除以及稀疏矩阵三元组转置等典型题型并给出对应解答过程。资源包共1个doc文件约318KB以文字与图表混排形式呈现便于打印或对照复习。目前已有127人学习下载。通过逐题答案与推导读者可检验对时间复杂度、空间复杂度、抽象数据类型、满二叉树与完全二叉树性质等知识点的掌握程度也可作为期末复习前的查漏补缺材料。1. 一份期中卷答案为什么值得当成数据结构自查清单期中刚过后台收到最多的一类消息是「顺序表插入到底移动 n-i 还是 n-i1」「完全二叉树编号 49 的左孩子为什么是 98 不是 99」这些问题看着零散其实都指向同一件事——对存储结构和逻辑结构的边界没吃透。这份《数据结构与算法》期中练习题答案覆盖了基本概念、线性结构、栈与队列、二叉树、稀疏矩阵、算法设计六大块一共十道大题从英文术语翻译一直写到就地逆置算法和单链表奇数结点统计。它适合两类人一类是正在跟严蔚敏版教材、准备 408 数据结构或者期末复习的在校生拿它当自测卷另一类是工作几年后想回头补链表、队列、二叉树这些基本功的开发者用它快速定位自己哪块概念是模糊的。整份文档不是零散答案堆砌而是一条从概念判断到代码实现的完整链路下面我按「怎么用、坑在哪」拆开讲。2. 从术语翻译到选择题把概念题当索引而不是答案2.1 第一、二大题的定位概念自检的入口第一大题是英译中queue 对应队列、singly linked lists 对应单链表、storge structure 对应存储结构、time complexity 对应时间复杂度、Abstract Data Type 对应抽象数据类型。这五个词不是随便挑的它们正好是后面所有题目的概念地基。很多人做选择题靠语感比如第 4 题「顺序表中逻辑上相邻的节点其物理位置也___」凭直觉选「一定相邻」但正确答案是 A顺序表确实物理相邻——这里容易和第 2 题「数据结构研究操作对象以及它们之间的___」混淆后者答案是 B 关系不是结构。我一般建议把第一大题当成索引表先把这五个术语的中英文对应关系背熟再去做选择题正确率会明显不一样。第二大题 20 道选择题覆盖线性结构的一对一关系、算法分析的两个方面时间复杂度和空间复杂度、顺序表插入移动元素个数、单链表插入语句、栈的输出序列、循环队列元素个数公式、空格串长度、二维数组按行存放的地址计算、二叉树结点数、满二叉树与完全二叉树关系、完全二叉树编号规则、递归转非递归用的辅助结构、稀疏矩阵定义。这些题不是孤立的第 6 题和第 7 题考的是线性表两种存储方式的差异第 8 题和第 9 题考的是栈和队列的操作特性第 12 到 16 题集中考二叉树性质。做题时如果某道错了不要只记答案回到对应知识点把公式推一遍。2.2 选择题里最容易翻车的三道逐个拆第 6 题向长度为 n 的顺序表第 i 个元素之前插入一个元素需向后移动多少个元素。答案是 Dn-i1。很多人选 B 的 n-i漏掉了「第 i 个元素本身也要后移」这一位。推导过程是这样的第 i 个到第 n 个元素一共 n-i1 个全部要往后挪一格。这个公式在后面写顺序表插入算法时直接决定循环边界记错一位代码就多移或者少移一个元素。第 9 题循环队列用数组 A[0, m-1] 存放头尾指针分别是 front 和 rear当前元素个数是 (rear-frontm)%m。答案是 A。这里的关键是「循环」两个字——当 rear 小于 front 时直接相减是负数加 m 再取模才能得到正确个数。我见过有人在笔试里写 rear-front面试官追问「队列绕回数组头部时怎么办」当场卡住。这个公式在实现循环队列的入队、出队、判空、判满时都要用到属于必须条件反射写出来的那种。第 11 题数组 A 每个元素占 3 字节行下标 1 到 8列下标 1 到 10从首地址 SA 开始按行存放求 A[8][5] 的起始地址。答案是 CSA222。计算逻辑按行存放A[8][5] 前面有 7 整行第 1 到第 7 行每行 10 个元素加上第 8 行前 4 个元素一共 7×10474 个元素每个 3 字节偏移 74×3222。这里最容易错的是把行下标当成从 0 开始或者忘记列下标也要减 1。二维数组地址计算是后面第四大题的直接前奏第四大题把元素类型从 3 字节的简单类型换成了包含 char[8] 和 int 的结构体计算逻辑一样但元素大小要自己算。提示选择题做完不要对完答案就翻篇把错题对应的知识点在教材目录里标出来第二轮复习直接看标记处。3. 链表指针操作与静态链表画图比背代码管用3.1 第三大题三行指针语句的顺序为什么不能换第三大题给了一个线性链表头指针 La要求把左图的指针指向改成右图。答案是p La-next; La-next p-next; p-next La; La p;这四行看着简单但顺序一换就断链。第一步 p 指向 La 的下一个结点第二步把 La 的 next 跳过 p 直接连到 p 的后继第三步把 p 的 next 指回 La第四步把头指针 La 移到 p。整个过程相当于把第二个结点摘出来放到链表头部。如果先执行 La-next p-next 再执行 p La-nextp 就丢了。我批改作业时见过最常见的错误是写成 p-next La; La-next p-next;这样 La 的 next 被覆盖后半条链直接丢失。链表指针操作没有后悔药写之前先在纸上画三个方框加箭头把每一步之后各指针的指向标出来确认不断链再落笔。3.2 第六大题静态链表的插入与删除第六大题是静态链表序列 (a,b,c,d,e) 已存在头指针指向 1 号结点。要求标出逻辑关系然后依次执行 b 前插入 f、删除 e、c 后插入 g画出新的静态链表。静态链表用数组模拟指针每个结点存数据和 next 下标0 号位置通常作头结点。这道题的坑在于插入和删除操作会改变空闲链表新结点要从空闲链表头部取删除的结点要回收。答案里图 a 到图 b 的演变核心是维护两条链——数据链和空闲链。很多人只画数据链忘记空闲链的 next 也要更新导致后面再插入时找不到可用结点。静态链表在实际工程里用得不多但它是理解「用数组实现链表」的绝佳模型。如果你在嵌入式环境或者对内存分配有严格限制的场景下工作静态链表的思想会 reappear。做这道题时建议用表格把每个下标对应的 data 和 next 列出来逐行更新比画箭头图更不容易出错。3.3 第十大题单链表奇数结点统计的边界第十大题要求统计带表头单链表中元素值为奇数的结点个数。参考答案typedef int elemtype; typedef struct Lnode { elemtype data; struct Lnode *next; } Lnode, *LinkList; int sum(LinkList L) { Lnode *p; int s 0; for (p L-next; p ! NULL; p p-next) if (p-data % 2 1) s; return s; }这段代码逻辑没问题但有两个细节值得说。第一循环从 L-next 开始跳过头结点这是带表头链表的标配。第二判断奇数用 p-data % 2 1如果数据域是负数C 语言里 -3 % 2 结果是 -1不等于 1会漏掉负奇数。更稳妥的写法是 p-data % 2 ! 0。参考答案没考虑负数场景但实际数据里出现负数是常有的事这个坑我踩过。另外函数返回类型和参数类型要匹配参考答案里 sum 的参数写的是 linklist而类型定义是 LinkListC 语言大小写敏感编译会报错抄的时候注意统一。4. 二叉树性质与稀疏矩阵公式要会推不能只背4.1 二叉树五道题的公式推导链第 12 到 16 题集中考二叉树这几道题的公式是连着的。深度为 4 的二叉树至多 2^4-115 个结点这是满二叉树的情况。满二叉树中 m 个树叶、n 个结点、深度 h则 n2h-1注意这里的 h 是深度公式和结点数关系是 n2^h-1参考答案写 n2h-1 是排版省略了上标实际是 2 的 h 次方减 1。具有 65 个结点的完全二叉树深度为 7因为 2^6-163 65 ≤ 2^7-1127。满二叉树一定是完全二叉树反之不成立。100 个结点的完全二叉树编号49 号结点的左孩子是 98因为左孩子编号等于父结点编号乘 249×298右孩子是 99。这几条性质不是孤立的它们共同构成二叉树顺序存储的基础。完全二叉树用数组存储时父子结点下标关系就是这些公式的直接应用。堆排序、线段树、优先队列底层都用数组存完全二叉树下标计算错一位整个结构就乱了。我建议把这五道题涉及的公式整理到一张纸上结点总数与深度的关系、叶子结点与度为 2 结点的关系、完全二叉树编号规则反复推到不看书能写出来为止。4.2 第八大题的证明非叶子结点中度为 2 的有 M-1 个第八大题要求证明任意 N 个结点的二叉树M 个叶子结点则非叶子结点中度为 2 的有 M-1 个。证明过程用到了两个等式结点总数 N n0 n1 n2分支数 B n1 2n2且 N B 1。代入 n0 M得 M n1 n2 n1 2n2 1化简得 n2 M - 1。这个证明是二叉树性质里最经典的一个408 考试里反复出现。它的价值不在于记住结论而在于掌握「结点数 分支数 1」这个桥梁。很多二叉树相关的证明题突破口都是这个等式。参考答案给了两种证法本质一样第二种写得更清楚。抄答案的时候注意第一种证法里「B0n12*n2」的 0 代表叶子结点的分支数这个 0 写出来是为了对齐不写也不影响。但「NB1」这一步必须写清楚它是整个证明的关键。4.3 第七大题稀疏矩阵三元组表与转置第七大题给了一个稀疏矩阵要求写出三元组顺序表表示和转置矩阵的三元组顺序表。原矩阵是 5 行 6 列非零元素 6 个三元组表按行优先顺序排列(1,2,2)、(1,6,1)、(3,2,3)、(4,5,4)、(5,2,5)、(5,6,6)。转置后变成 6 行 5 列三元组表要按转置后的行优先顺序重新排列答案是 (1,2,2)、(2,1,1)、(2,3,3)、(2,5,5)、(5,4,4)、(6,5,6)。这里有两个版本排序后和未排序。排序后的是标准三元组顺序表未排序的是转置过程中间状态。实际写转置算法时常见做法是遍历原三元组表把每个元素的行列互换后放到新表对应位置最后再按行排序。如果矩阵很大排序开销不可忽略所以还有快速转置算法用两个辅助数组记录每列非零元素个数和起始位置一次遍历就能得到有序结果。这道题虽然只要求填表但背后对应的是稀疏矩阵存储和转置的完整知识块值得顺着往下挖。注意三元组表的行列下标从 1 开始还是从 0 开始不同教材不一样抄答案前先确认自己教材的约定混用会全错。5. 算法设计题与地址计算从伪代码到可运行代码的距离5.1 第九大题顺序表就地逆置的循环边界第九大题要求写算法实现顺序表就地逆置。参考答案#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; } }这段代码能跑但循环边界 i L-length/2 在长度为偶数时会多交换一次中间两个元素相当于换过去又换回来结果正确但多做一次无用功。更严谨的写法是 i L-length/2。另外如果 length 为 0 或 1循环条件 i 0 会执行一次交换 data[0] 和 data[length-1]当 length1 时是自己和自己换不影响结果但当 length0 时访问 data[-1] 就越界了。实际工程里我会在函数开头加 if (L-length 1) return; 把边界挡掉。参考答案是教学版本追求简洁但拿去实际用要补边界判断。5.2 第四大题结构体数组地址计算的完整推导第四大题是整份卷子里计算量最大的一道。结构体 STUDENT 包含 char name[8] 和 int numberchar 占 1 字节int 占 4 字节但结构体大小不是 8412 吗参考答案写的是 12说明没有考虑内存对齐。在默认对齐规则下int 要 4 字节对齐name 占 8 字节后偏移是 88 能被 4 整除所以 number 紧跟着放结构体大小就是 12。如果 name 是 char[7]偏移 7 不能被 4 整除编译器会填充 1 字节结构体变成 12 字节。这道题恰好 name[8] 让对齐不产生额外填充所以 12 成立。allstudents[10][50] 是二维数组每个元素 12 字节按行存放。allstudents[i][j] 的地址 2000 (i50 j)12。allstudents[3][5] 2000 (3505)12 2000 15512 2000 1860 3860。参考答案写的是 2000(3505)123860中间漏了加号实际是 2000(3505)*12。这个计算逻辑和选择题第 11 题完全一致只是元素大小从 3 变成了 12。把这两道题放在一起看二维数组地址计算的通用公式就清楚了首地址 (行下标×列数 列下标) × 元素大小注意下标从 0 还是从 1 开始。5.3 第五大题循环队列 17 进 16 出的状态推演第五大题用下标 0 到 4 的一维数组存循环队列初始有两个元素 A、B状态如图 a。然后 17 个元素 C 到 S 依次进队其间 16 个元素出队要求填图 b 的最终状态。数组容量 5初始有 2 个元素17 进 16 出净增 1 个元素最终队列里有 3 个元素。关键是确定 front 和 rear 的最终位置。初始状态图 a 里 front 指向 Arear 指向 B 的下一个位置。每进一个元素 rear 后移一位并对 5 取模每出一个元素 front 后移一位并对 5 取模。17 次进队和 16 次出队交替进行最终 front 和 rear 的位置要逐步推。参考答案最终 front 指向 Qrear 指向 S队列里元素是 Q、R、S。这道题没有捷径就是拿一张纸画五个格子一步一步标 front 和 rear进队就 rear 加一取模出队就 front 加一取模。推两遍就能找到规律。循环队列的判空和判满条件也在这里体现front rear 时队列空但队列满时也是 front rear如果牺牲一个存储单元所以通常用 (rear1)%m front 判满。这道题虽然只要求填状态但把循环队列的指针移动规则练熟了后面写队列代码就是水到渠成的事。6. 把这份答案用出最大价值我的三轮自测法这份文档我前后翻过三遍第一遍当普通答案对第二遍把每道题对应的知识点在教材里定位第三遍遮住答案自己重做。三轮下来最大的收获不是记住了某道题的答案而是摸清了数据结构期中考试的出题套路——概念题考边界链表题考指针顺序二叉树题考公式推导算法题考循环边界和空表处理。如果你也在准备类似的考试或者想补基本功我建议按这个顺序用这份资料。第一轮限时 90 分钟做完前两大题对答案后把错题涉及的概念在教材目录里标出来。第二轮把第三、六、九、十这四道操作和算法题在纸上手写一遍不看书写完对照参考答案找差异重点看指针顺序和循环边界。第三轮把第四、五、七、八这四道计算和证明题重新推一遍尤其是第四题的地址计算和第八题的证明要能独立写出完整过程。三轮走完这份期中卷的价值就榨干了。下面这张表是我整理的各题对应知识点和易错点方便你按图索骥题号知识点易错点一术语英译中storge 拼写、ADT 全称二 1-5基本概念逻辑结构与物理结构混淆二 6-11线性表、栈、队列、数组插入移动个数、循环队列公式、地址计算二 12-20二叉树、稀疏矩阵完全二叉树编号、满二叉树关系三单链表指针操作语句顺序导致断链四结构体数组地址计算元素大小、下标起始五循环队列状态推演front/rear 移动取模六静态链表插入删除空闲链维护七稀疏矩阵三元组转置后排序八二叉树性质证明结点数与分支数关系九顺序表就地逆置循环边界、空表处理十单链表奇数统计负数取模、类型大小写最后说一个我自己的习惯每次做完这类卷子我会把错题对应的代码在编译器里跑一遍比如第九题的逆置把 length 设成 0、1、2、5 分别测看会不会越界。纸上推和机器跑是两回事很多边界问题只有跑起来才暴露。从那以后我每次复习数据结构都强制自己把算法题敲进编辑器跑通再算过。希望这份拆解帮到你答案文档本身不长但每一道题背后都有一条可以往下挖的线顺着挖比刷十套卷子管用。本文还有配套的精品资源点击获取