企业官网建设流程全解析

简介：这份文档资料是《数据结构与算法》期中练习题的配套答案，面向正在学习数据结构课程的高校学生与备考者，帮助其核对解题思路、巩固核心考点。内容覆盖基本概念、线性结构、栈与队列、二叉树、算法设计及稀疏矩阵等模块，包含选择题、链表指针操作、结构体存储位置计算、循环队列状态推演、静态链表插入删除以及稀疏矩阵三元组转置等典型题型，并给出对应解答过程。资源包共1个doc文件，约318KB，以文字与图表混排形式呈现，便于打印或对照复习。目前已有127人学习下载。通过逐题答案与推导，读者可检验对时间复杂度、空间复杂度、抽象数据类型、满二叉树与完全二叉树性质等知识点的掌握程度，也可作为期末复习前的查漏补缺材料。

1. 一份期中卷答案，为什么值得当成数据结构自查清单

期中刚过，后台收到最多的一类消息是：「顺序表插入到底移动 n-i 还是 n-i+1？」「完全二叉树编号 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 个元素之前插入一个元素，需向后移动多少个元素。答案是 D，n-i+1。很多人选 B 的 n-i，漏掉了「第 i 个元素本身也要后移」这一位。推导过程是这样的：第 i 个到第 n 个元素一共 n-i+1 个，全部要往后挪一格。这个公式在后面写顺序表插入算法时直接决定循环边界，记错一位，代码就多移或者少移一个元素。

第 9 题：循环队列用数组 A[0, m-1] 存放，头尾指针分别是 front 和 rear，当前元素个数是 (rear-front+m)%m。答案是 A。这里的关键是「循环」两个字——当 rear 小于 front 时，直接相减是负数，加 m 再取模才能得到正确个数。我见过有人在笔试里写 rear-front，面试官追问「队列绕回数组头部时怎么办」，当场卡住。这个公式在实现循环队列的入队、出队、判空、判满时都要用到，属于必须条件反射写出来的那种。

第 11 题：数组 A 每个元素占 3 字节，行下标 1 到 8，列下标 1 到 10，从首地址 SA 开始按行存放，求 A[8][5] 的起始地址。答案是 C，SA+222。计算逻辑：按行存放，A[8][5] 前面有 7 整行（第 1 到第 7 行），每行 10 个元素，加上第 8 行前 4 个元素，一共 7×10+4=74 个元素，每个 3 字节，偏移 74×3=222。这里最容易错的是把行下标当成从 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->next，p 就丢了。我批改作业时见过最常见的错误是写成 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，而类型定义是 LinkList，C 语言大小写敏感，编译会报错，抄的时候注意统一。

4. 二叉树性质与稀疏矩阵：公式要会推，不能只背

4.1 二叉树五道题的公式推导链

第 12 到 16 题集中考二叉树，这几道题的公式是连着的。深度为 4 的二叉树至多 2^4-1=15 个结点，这是满二叉树的情况。满二叉树中 m 个树叶、n 个结点、深度 h，则 n=2h-1，注意这里的 h 是深度，公式和结点数关系是 n=2^h-1，参考答案写 n=2h-1 是排版省略了上标，实际是 2 的 h 次方减 1。具有 65 个结点的完全二叉树深度为 7，因为 2^6-1=63 < 65 ≤ 2^7-1=127。满二叉树一定是完全二叉树，反之不成立。100 个结点的完全二叉树编号，49 号结点的左孩子是 98，因为左孩子编号等于父结点编号乘 2，49×2=98，右孩子是 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」这个桥梁。很多二叉树相关的证明题，突破口都是这个等式。

参考答案给了两种证法，本质一样，第二种写得更清楚。抄答案的时候注意，第一种证法里「B=0+n1+2*n2」的 0 代表叶子结点的分支数，这个 0 写出来是为了对齐，不写也不影响。但「N=B+1」这一步必须写清楚，它是整个证明的关键。

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]，当 length=1 时是自己和自己换，不影响结果，但当 length=0 时访问 data[-1] 就越界了。实际工程里我会在函数开头加 if (L->length <= 1) return; 把边界挡掉。参考答案是教学版本，追求简洁，但拿去实际用要补边界判断。

5.2 第四大题：结构体数组地址计算的完整推导

第四大题是整份卷子里计算量最大的一道。结构体 STUDENT 包含 char name[8] 和 int number，char 占 1 字节，int 占 4 字节，但结构体大小不是 8+4=12 吗？参考答案写的是 12，说明没有考虑内存对齐。在默认对齐规则下，int 要 4 字节对齐，name 占 8 字节后偏移是 8，8 能被 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 + (350+5)12 = 2000 + 15512 = 2000 + 1860 = 3860。参考答案写的是 2000(350+5)12=3860，中间漏了加号，实际是 2000+(350+5)*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 指向 A，rear 指向 B 的下一个位置。每进一个元素 rear 后移一位并对 5 取模，每出一个元素 front 后移一位并对 5 取模。17 次进队和 16 次出队交替进行，最终 front 和 rear 的位置要逐步推。参考答案最终 front 指向 Q，rear 指向 S，队列里元素是 Q、R、S。

这道题没有捷径，就是拿一张纸画五个格子，一步一步标 front 和 rear，进队就 rear 加一取模，出队就 front 加一取模。推两遍就能找到规律。循环队列的判空和判满条件也在这里体现：front == rear 时队列空，但队列满时也是 front == rear（如果牺牲一个存储单元），所以通常用 (rear+1)%m == front 判满。这道题虽然只要求填状态，但把循环队列的指针移动规则练熟了，后面写队列代码就是水到渠成的事。

6. 把这份答案用出最大价值：我的三轮自测法

这份文档我前后翻过三遍，第一遍当普通答案对，第二遍把每道题对应的知识点在教材里定位，第三遍遮住答案自己重做。三轮下来，最大的收获不是记住了某道题的答案，而是摸清了数据结构期中考试的出题套路——概念题考边界，链表题考指针顺序，二叉树题考公式推导，算法题考循环边界和空表处理。如果你也在准备类似的考试或者想补基本功，我建议按这个顺序用这份资料。

第一轮，限时 90 分钟做完前两大题，对答案后把错题涉及的概念在教材目录里标出来。第二轮，把第三、六、九、十这四道操作和算法题在纸上手写一遍，不看书，写完对照参考答案找差异，重点看指针顺序和循环边界。第三轮，把第四、五、七、八这四道计算和证明题重新推一遍，尤其是第四题的地址计算和第八题的证明，要能独立写出完整过程。三轮走完，这份期中卷的价值就榨干了。

下面这张表是我整理的各题对应知识点和易错点，方便你按图索骥：

最后说一个我自己的习惯：每次做完这类卷子，我会把错题对应的代码在编译器里跑一遍，比如第九题的逆置，把 length 设成 0、1、2、5 分别测，看会不会越界。纸上推和机器跑是两回事，很多边界问题只有跑起来才暴露。从那以后我每次复习数据结构，都强制自己把算法题敲进编辑器跑通再算过。希望这份拆解帮到你，答案文档本身不长，但每一道题背后都有一条可以往下挖的线，顺着挖，比刷十套卷子管用。

本文还有配套的精品资源，点击获取