数据结构：题库练习¶

已整理本章知识点练习 77 条来源题目，共 77 道练习。题号沿用来源序号；同材料的不同小问分别保留。

题干保留事实条件、选项与必要题图；平台答案、整理解析与纠错默认收起。解析重新归纳为复习笔记，平台答案不等同于官方答案。

题库整理进度 · 历年试卷清单

知识点练习¶

题目 001¶

来源：知识点练习「数据结构」第 1 题（原站入口）。

某线性表主要用于按任意给定序号访问元素，并在表尾插入、删除元素。适合采用哪一种存储方式（）？

A. 顺序表
B. 单链表
C. 双向链表
D. 哈希表

答案与解析

平台答案：A。

整理解析

选 A。顺序表可按下标 O(1) 访问任意元素，尾部删除也无需搬移其他元素。容量足够时尾部插入为 O(1)；动态数组扩容时单次插入可能为 O(n)，通常讨论摊还 O(1)。链表按序号定位通常需要遍历。

题目 002¶

来源：知识点练习「数据结构」第 2 题（原站入口）。

下图二叉树若用一维数组顺序存储，结点间的关系由下标表示：下标为 i 的结点，其左、右孩子下标分别为 2i、2i+1。数组至少需要（2）个存储位置。若改用三叉链表，每个结点包含数据、父结点指针、左孩子指针和右孩子指针，则全部结点的空指针总数为（3）。

请作答：第 2 题。

A. 6
B. 10
C. 12
D. 15

答案与解析

平台答案：D。

整理解析

本问选 D。以根下标为 1，图中 6 个结点的位置依次为 1、2、3、7、14、15，故最大使用下标为 15，按题目的一基存储口径需 15 个位置。不能仅凭高度 h 就断言任意二叉树都必须占满 2^h−1 个位置；本图恰有最右下结点。若在零基编程数组中闲置下标 0，实际分配长度应为 16，这是另一种计数口径。

题目 003¶

来源：知识点练习「数据结构」第 3 题（原站入口）。

下图二叉树若用一维数组顺序存储，结点间的关系由下标表示：下标为 i 的结点，其左、右孩子下标分别为 2i、2i+1。数组至少需要（2）个存储位置。若改用三叉链表，每个结点包含数据、父结点指针、左孩子指针和右孩子指针，则全部结点的空指针总数为（3）。

请作答：第 3 题。

A. 6
B. 8
C. 12
D. 14

答案与解析

平台答案：B。

整理解析

本问选 B。图中有 n=6 个结点，共 3n=18 个指针域。5 条父子边各占一个孩子指针和一个父指针，非空指针为 2(n−1)=10 个，故空指针有 18−10=8 个，即 n+2；根的父指针也计为空。

同材料可参照第 2 题。

题目 004¶

来源：知识点练习「数据结构」第 4 题（原站入口）。

图示双端队列要求每个元素从哪一端入队，就从同一端出队。对 4 个元素的序列 e1、e2、e3、e4，前 2 个元素 e1、e2 按顺序全部从 A 端进入，后两个元素 e3、e4 按顺序全部从 B 端进入。下列哪一个出队序列可能出现（）？

A. e1、e2、e3、e4
B. e2、e3、e4、e1
C. e3、e4、e1、e2
D. e4、e3、e2、e1

答案与解析

平台答案：D。

整理解析

按题意理解为各元素已按指定次序全部入队，选 D。A 端出队须先 e2 后 e1，B 端须先 e4 后 e3，只有 e4、e3、e2、e1 同时满足两条约束。若允许在本端两个元素尚未全部入队时就穿插出队，约束会改变，平台结论依赖题中的“全部进入”阶段划分。

题目 005¶

来源：知识点练习「数据结构」第 5 题（原站入口）。

与顺序存储相比，使用链表存储线性表的缺点是（）。

A. 数据元素之间的关系需要占用存储空间，导致存储密度不高
B. 表中结点必须占用地址连续的存储单元，存储密度不高
C. 插入新元素时需要遍历整个链表，运算的时间效率不高
D. 删除元素时需要遍历整个链表，运算的时间效率不高

答案与解析

平台答案：A。

整理解析

选 A。链表除数据外还要存储链接指针，因此存储密度通常低于顺序表。链表结点无需地址连续；已知所需结点及其前驱时，插入、删除只需修改局部链接，不能说每次都必须遍历整个链表。链表仍受可用内存限制。

题目 006¶

来源：知识点练习「数据结构」第 6 题（原站入口）。

一个初始为空的栈依次接收 1，2，3，…，n-1，n。若第一个出栈元素是 k，且 1≤k≤「n/2」，则最后一个出栈元素为（）。

A. 值为n的元素
B. 值为1的元素
C. 值为n-k的元素
D. 不确定的

答案与解析

平台答案：D。

整理解析

一般不能据此确定最后一个元素，平台选 D。例如 n=4、k=2 时，2、1、3、4 与 2、3、4、1 都是合法出栈序列，末元素分别为 4 和 1。原页截图已确认界限写作「n/2」，左端横线在上、右端横线在下，是原站不规范的一对角括号，不能明确读作一对向上或向下取整符号。这里保留原符号；上述 n=4 反例不受影响。

题目 007¶

来源：知识点练习「数据结构」第 7 题（原站入口）。

对二叉查找树（二叉排序树）进行查找时，哪一种树形会造成最差的查找效率（）？

A. 完全二叉树
B. 平衡二叉树
C. 单枝树
D. 满二叉树

答案与解析

平台答案：C。

整理解析

选 C。单枝树退化为一条长度为 n 的链，最坏需比较 n 个结点，查找为 O(n)。高度受控的平衡树能将最坏查找路径降至 O(log n)。

题目 008¶

来源：知识点练习「数据结构」第 8 题（原站入口）。

KMP 字符串匹配算法使用模式串的 next 函数，其定义见下图，字符序号 j 从 1 开始。模式串 p 为“abaac”时，next 值依次为（）。

A. 01234
B. 01122
C. 01211
D. 01111

答案与解析

平台答案：B。

整理解析

选 B，即 0、1、1、2、2。按图中从 1 起算的 next 定义，首项为 0；其后考察当前字符之前子串的最长相等真前后缀，再加 1。“a”“ab”没有非空匹配，“aba”“abaa”的最长匹配都是“a”。第 5 个字符实际是 c，平台解析写成 a、并把前缀写成“abaa0”，属于文字错误。

题目 009¶

来源：知识点练习「数据结构」第 9 题（原站入口）。

某文件的字符及其出现频率见下表。若使用二进制定长编码，每个字符需要（9）位；若使用 Huffman 编码，字符序列“face”的编码为（10）。

请作答：第 9 题。

A. 2
B. 3
C. 4
D. 5

答案与解析

平台答案：B。

整理解析

本问选 B。图中有 a、b、c、d、e、f 共 6 种字符，二进制定长码需要满足 2^b≥6，最小 b 为 3。频率 45%、13%、12%、16%、9%、5% 用于后一问的不等长编码，不改变定长码的最低位数。

题目 010¶

来源：知识点练习「数据结构」第 10 题（原站入口）。

某文件的字符及其出现频率见下表。若使用二进制定长编码，每个字符需要（9）位；若使用 Huffman 编码，字符序列“face”的编码为（10）。

请作答：第 10 题。

A. 110001001101
B. 001110110011
C. 101000010100
D. 010111101011

答案与解析

平台答案：A。

整理解析

按平台使用的码表，a=0、b=101、c=100、d=111、e=1101、f=1100，故 face=1100|0|100|1101，选 A。哈夫曼合并权重为 5+9=14、12+13=25、14+16=30、25+30=55、45+55=100。频率并不唯一确定各边标 0 还是 1，题干未给分支约定；A 是选项中可由该哈夫曼树产生的编码，不应把这张具体码表说成唯一结果。

同材料可参照第 9 题。

题目 011¶

来源：知识点练习「数据结构」第 11 题（原站入口）。

循环队列 Q 使用 front、rear 两个域变量：front 指向队头元素，rear 指向队尾元素之后的位置，如图所示。队列容量为 M 时，队列长度的计算式为（）。

A. (Q.rear-Q.front +1)
B. (Q.rear-Q.front+M)
C. (Q.rear-Q.front+1)%M
D. (Q.rear-Q.front+M)%M

答案与解析

平台答案：D。

整理解析

按常用循环队列约定选 D。rear 位于尾元素之后，从 front 沿环到 rear 的距离为 (Q.rear−Q.front+M)%M。这个公式通常配合预留一个空槽来区分队空、队满；若 M 个槽全可占用，还须增加计数或满标志，否则 front=rear 无法区分长度 0 与 M。

题目 012¶

来源：知识点练习「数据结构」第 12 题（原站入口）。

栈 S 与队列 Q 最初都为空，元素 a、b、c、d、e、f、g 按此顺序进入 S，每个元素一出栈就立即进入 Q。若这 7 个元素的出队顺序为 b、d、f、e、c、a、g，则 S 至少需要容纳（）个元素。

A. 5
B. 4
C. 3
D. 2

答案与解析

平台答案：B。

整理解析

选 B，最小容量为 4。先压入 a、b 后弹出 b，再压入 c、d 后弹出 d；为下一个弹出 f，必须再压入 e、f，此时栈为 a、c、e、f，共 4 个。随后依次弹出 f、e、c、a，再让 g 入栈出栈即可，故 4 既必要又足够。

题目 013¶

来源：知识点练习「数据结构」第 13 题（原站入口）。

某二叉树的先序遍历为 c、a、b、f、e、d、g，中序遍历为 a、b、c、d、e、f、g。该树属于（）。

A. 完全二叉树
B. 最优二叉树
C. 平衡二叉树
D. 满二叉树

答案与解析

平台答案：C。

整理解析

选 C。由两种遍历还原：根为 c，左子树为 a 的右孩子 b；右子树根为 f，左孩子 e 的左孩子为 d，右孩子为 g。每个结点的左右子树高度差均不超过 1，且中序有序，符合平衡二叉查找树。a 无左孩子却有右孩子，因此不是完全二叉树，也不是满二叉树。

题目 014¶

来源：知识点练习「数据结构」第 14 题（原站入口）。

优先队列通常以（14）作为实现的数据结构；向其中插入一个元素的时间复杂度为（15）。

请作答：第 14 题。

A. 堆
B. 栈
C. 队列
D. 线性表

答案与解析

平台答案：A。

整理解析

本问选 A。二叉堆把最高优先级元素保持在堆顶，支持高效插入和取出。优先级与数值的对应关系可采用大根堆或小根堆，并非所有场景都固定为最大数值先出。

题目 015¶

来源：知识点练习「数据结构」第 15 题（原站入口）。

优先队列通常以（14）作为实现的数据结构；向其中插入一个元素的时间复杂度为（15）。

请作答：第 15 题。

A. O(n)
B. O(1)
C. O(lgn)
D. O(n²)

答案与解析

平台答案：C。

整理解析

本问选 C。沿用前一空的二叉堆实现，插入时先放到完全二叉树的末尾，再向上调整，最坏经过 O(log n) 层，因此最坏时间为 O(lg n)。最好情况可不需上移，不能据此把一般复杂度答成 O(1)。

同材料可参照第 14 题。

题目 016¶

来源：知识点练习「数据结构」第 16 题（原站入口）。

一个长度为 n（n>1）、元素互不相同的序列，依次经过初始为空的栈，再经过初始为空的队列。两者容量均足够大；栈非空时允许出栈，队列非空时允许出队。以下哪项关系必然成立（）？

A. 出队序列和出栈序一定互为逆序
B. 出队序列和出栈序列一定相同
C. 入栈序列与入队序列一定相同
D. 入栈序列与入队序列一定互为逆序

答案与解析

平台答案：B。

整理解析

选 B。每个元素出栈后按同一次序入队，队列的先进先出性质又保持该次序，所以出队序列必定等于出栈序列。入栈与出栈可交错进行，出栈序列既不必等于入栈序列，也不必是其逆序。

题目 017¶

来源：知识点练习「数据结构」第 17 题（原站入口）。

n 阶三对角矩阵 A_n×n 如图所示。把其非零元素按行存入一维数组 B[k]，其中 1≤k≤3*n-2。元素 A[i,j] 对应的下标 k 为（）。

A. k=2i+j-2
B. k=2i-j+2
C. k=3i+j-1
D. K=3i-j+2

答案与解析

平台答案：A。

整理解析

选 A。图中 A 的下标从 1 开始，首行占 2 个位置；对 i≥2，第 i 行之前有 2+3(i−2)=3i−4 个位置，本行 A[i,j] 的行内序号为 j−i+2，相加得到 k=2i+j−2，首行也适用。这里按固定的三条对角带存储 3n−2 个位置；若连带内偶然出现的零也逐个删去，下标公式就不能只由 i、j 决定。

题目 018¶

来源：知识点练习「数据结构」第 18 题（原站入口）。

对于非空二叉树，D 表示根结点，L、R 分别表示左、右子树。图示二叉树的遍历结果是 7、6、5、4、3、2、1，对应的遍历方式为（）。

A. LRD
B. DRL
C. RLD
D. RDL

答案与解析

平台答案：D。

整理解析

选 D，即递归按右子树、根、左子树访问。图中根为 3，右子树按此规则得到 7、6、5、4，然后访问 3，最后左子树得到 2、1，合起来正是题设序列。

题目 019¶

来源：知识点练习「数据结构」第 19 题（原站入口）。

一个简单有向图有 n 个顶点、e 条弧，以邻接矩阵存储。A[i][j] 为 1 表示有从 i 到 j 的弧，为 0 表示没有，则矩阵中非零元素共有（）个。

A. e
B. 2e
C. n-e
D. n+e

答案与解析

平台答案：A。

整理解析

选 A。有向弧 i→j 只对应 A[i][j] 中的一个 1，因此 e 条弧贡献 e 个非零元素。2e 是无向图中每条普通边在对称位置各记一次时的计数。

题目 020¶

来源：知识点练习「数据结构」第 20 题（原站入口）。

初始为空的栈按 a、b、c、d、e 的次序接收元素，每个元素只入栈、出栈各 1 次。要求第一个出栈的是 d，共有（）种合法的出栈序列。

A. 4
B. 5
C. 6
D. 24

答案与解析

平台答案：A。

整理解析

选 A。d 第一个弹出后，栈中 a、b、c 的相对出栈顺序只能是 c、b、a，e 尚未入栈。把 e 的出栈位置放在 c、b、a 的前面、两个间隙或后面，共 4 种。

题目 021¶

来源：知识点练习「数据结构」第 21 题（原站入口）。

依次插入关键码以建立图示二叉排序树（二叉查找树），下列哪个序列不可能得到该树（）？

A. 23 31 17 19 11 27 13 90 61
B. 23 17 19 31 27 90 61 11 13
C. 23 17 27 19 31 13 11 90 61
D. 23 31 90 61 27 17 19 11 13

答案与解析

平台答案：C。

整理解析

选 C。图中根为 23，右子树根为 31。C 在插入 23、17 后就插入 27，此时 27 会占据 23 的右孩子位置，随后插入 31 也不会把它改成图示结构。其余三组按二叉查找树规则插入都能得到原图。

题目 022¶

来源：知识点练习「数据结构」第 22 题（原站入口）。

一棵二叉树的高度按层数计为 h，下列关于它的结点数量的说法正确的是（）。

A. 有2^h个节点
B. 有2^h-1个节点
C. 最少有2^h-1个节点
D. 最多有2^h-1个节点

答案与解析

平台答案：D。

整理解析

选 D。第 i 层最多有 2ⁱ⁻¹ 个结点，h 层相加为 1+2+…+2^h−1=2^h−1，满二叉树达到该上限。非空树高度为 h 时最少只需 h 个结点，即一条单枝链。

题目 023¶

来源：知识点练习「数据结构」第 23 题（原站入口）。

关于图的遍历，下列说法正确的是（）。

A. 图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程
B. 图的深度优先遍历方法不适用于无向图
C. 使用队列对图进行广度优先遍历
D. 图中有回路时则无法进行遍历

答案与解析

平台答案：C。

整理解析

平台选 C。广度优先遍历用先进先出的队列保存待扩展顶点；深度优先也适用于无向图，回路可通过访问标记处理。A 的表述有歧义：它接近常见遍历定义，但从一个给定源点未必能到达非连通图或有向图的全部顶点，完整遍历须在有未访问顶点时另选起点。若限定所有顶点均从源点可达，A 也可成立；平台以“未写沿路径”为由直接否定 A 并不充分。

题目 024¶

来源：知识点练习「数据结构」第 24 题（原站入口）。

二维数组 a[1..N,1..N] 分别采用按行与按列存储。对元素 a[i,j]（1≤i,j≤N），当（）时，两种方式下的偏移量相同。

A. i≠j
B. i=j
C. i > j
D. i < j

答案与解析

平台答案：B。

整理解析

选 B。以元素个数计，按行偏移为 (i−1)N+(j−1)，按列偏移为 (j−1)N+(i−1)，两者相减得 (N−1)(i−j)。N>1 时相等当且仅当 i=j；N=1 时唯一合法下标也满足 i=j。

题目 025¶

来源：知识点练习「数据结构」第 25 题（原站入口）。

有向无环图的拓扑序列包含其全部顶点；若存在弧（v,w）或从 v 到 w 的路径，则 v 必须排在 w 之前。下列哪一个序列是图示有向图的拓扑序列（）？

A. 41235
B. 43125
C. 42135
D. 41325

答案与解析

平台答案：A。

整理解析

选 A。图中的 4→1→2→3→5 已形成包含全部顶点的先后约束链，另有 4→2、4→3、2→5，故唯一拓扑序列为 4、1、2、3、5。平台解析说访问 2 后可以先访问 3 或 5，忽略了图中的 3→5；必须先 3 后 5。

题目 026¶

来源：知识点练习「数据结构」第 26 题（原站入口）。

一个有序线性表含 n 个元素，等概率删除其中任意一个。若以顺序结构存储，平均要移动（26）个元素；若以单链表存储，平均要移动（27）个元素。

请作答：第 26 题。

A. 1
B. （n-1）/2
C. logn
D. n

答案与解析

平台答案：B。

整理解析

本问选 B。顺序表删除第 i 个元素需将后面的 n−i 个元素前移。各位置等概率，平均移动数为 [(n−1)+(n−2)+…+0]/n=(n−1)/2。这里只统计元素搬移，不含定位被删元素的比较次数。

题目 027¶

来源：知识点练习「数据结构」第 27 题（原站入口）。

一个有序线性表含 n 个元素，等概率删除其中任意一个。若以顺序结构存储，平均要移动（26）个元素；若以单链表存储，平均要移动（27）个元素。

请作答：第 27 题。

A. 0
B. 1
C. （n-1）/2
D. n/2

答案与解析

平台答案：A。

整理解析

本问选 A。单链表删除结点时调整其前驱的 next 链接并释放被删结点，其余元素无需搬移，所以移动数为 0。寻找目标及其前驱可能需要遍历，不能将“移动数为 0”等同于任意删除操作整体为 O(1)。

同材料可参照第 26 题。

题目 028¶

来源：知识点练习「数据结构」第 28 题（原站入口）。

恰好包含 3 个结点的二叉树，共有（）种不同形态。

A. 2
B. 3
C. 5
D. 7

答案与解析

平台答案：C。

整理解析

选 C。二叉树区分左、右孩子。除根外的两个结点可分配为左 0 右 2、左 1 右 1、左 2 右 0，对应 2、1、2 种，共 5 种。这里计算树形，不给结点附加不同标签。

题目 029¶

来源：知识点练习「数据结构」第 29 题（原站入口）。

关于二叉排序树（也称二叉查找树、二叉搜索树），下列说法正确的是（）。

A. 对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列
B. 含有n个结点的二叉排序树高度为[log₂n]+1
C. 从根到任意一个叶子结点的路径上，结点的关键字呈现有序排列的特点
D. 从左到右排列同层次的结点，其关键字呈现有序排列的特点

答案与解析

平台答案：D。

整理解析

选 D。同层从左到右的任意两个结点，在其最近公共祖先处分别落入左、右子树，故关键字按该方向有序。二叉查找树只有中序遍历保证有序；高度可退化为 n；根到叶的路径也可先减后增，如 30→19→25。左子树所有关键字受祖先约束，不能像平台解析的部分措辞那样仅理解为父子大小关系。

题目 030¶

来源：知识点练习「数据结构」第 30 题（原站入口）。

某文件中各字符的出现频率见下表。按霍夫曼编码，字符序列“bee”的编码为（30）；位串“110001001101”对应的字符序列为（31）。

请作答：第 30 题。

A. 10111011101
B. 10111001100
C. 001100100
D. 110011011

答案与解析

平台答案：A。

整理解析

平台选 A。其码表取 b=101、e=1101，故 bee=101|1101|1101。原题只给频率，未指定分支 0/1 的标记；把同一哈夫曼树中 e、f 的边标互换，令 e=1100、f=1101，仍是合法最优前缀码，此时 bee=101|1100|1100，正好是 B。因此单独按题干不能唯一排除 B，A 依赖平台使用的具体码表。

题目 031¶

来源：知识点练习「数据结构」第 31 题（原站入口）。

某文件中各字符的出现频率见下表。按霍夫曼编码，字符序列“bee”的编码为（30）；位串“110001001101”对应的字符序列为（31）。

请作答：第 31 题。

A. bad
B. bee
C. face
D. bace

答案与解析

平台答案：C。

整理解析

按平台码表 a=0、b=101、c=100、d=111、e=1101、f=1100，位串可唯一切分为 1100|0|100|1101，即 face，选 C。“唯一解码”以码表已确定为前提；仅给字符频率而未给分支标记，不能认为位串的译文天然唯一。本问与第 30 题共用材料，但作答内容和选项不同。

同材料可参照第 30 题。

题目 032¶

来源：知识点练习「数据结构」第 32 题（原站入口）。

关于字符串，下列说法正确的是（）。

A. 包含任意个空格字符的字符串称为空串
B. 字符串不是线性数据结构
C. 字符串的长度是指串中所含字符的个数
D. 字符串的长度是指串中所含非空格字符的个数

答案与解析

平台答案：C。

整理解析

选 C。串是字符组成的线性序列，长度计入全部字符，包括空格。空串长度为 0；只含一个或多个空格的串属于空白串，长度不为 0。

题目 033¶

来源：知识点练习「数据结构」第 33 题（原站入口）。

栈 S 初始为空，I 表示入栈，O 表示出栈。元素按 a₁、a₂、a₃、a₄、a₅ 的顺序入栈；要得到 a₂、a₄、a₅、a₃、a₁ 的出栈序列，应采用操作序列（）。

A. IIOIIOIOOO
B. IOIOIOIOIO
C. IOOIIOIOIO
D. IIOOIOIOOO

答案与解析

平台答案：A。

整理解析

选 A。IIOIIOIOOO 依次执行压入 a1、a2，弹出 a2；压入 a3、a4，弹出 a4；压入 a5，随后弹出 a5、a3、a1。B 得到原顺序，C 的第三步就对空栈出栈，D 只有 4 次入栈却有 6 次出栈。

题目 034¶

来源：知识点练习「数据结构」第 34 题（原站入口）。

一棵二叉树的先序遍历为 ABCDEF，中序遍历为 BADCFE。该树的高度（层数）是（）。

A. 3
B. 4
C. 5
D. 6

答案与解析

平台答案：B。

整理解析

选 B。先序首结点 A 为根，中序将其分为左子树 B 和右子树 DCFE；右子树根为 C，其左孩子 D、右孩子 E，E 的左孩子为 F。最长根叶路径 A→C→E→F 含 4 个结点，因此高度为 4 层。

题目 035¶

来源：知识点练习「数据结构」第 35 题（原站入口）。

非空字符串 S 长度为 n，所有字符互不相同。它的互异非平凡子串，即非空且不等于 S 本身的子串，共有（）个。

A. 2n-1
B. n²
C. n(n+1)/2
D. (n+2) (n-1)/2

答案与解析

平台答案：D。

整理解析

选 D。长度为 l 的连续子串有 n−l+1 个，各字符互异保证不同位置的同长度子串也不同。全部非空子串共 n(n+1)/2 个，去掉 S 本身后为 n(n+1)/2−1=(n+2)(n−1)/2；n=1 时结果为 0。

题目 036¶

来源：知识点练习「数据结构」第 36 题（原站入口）。

一条消息只含 7 种字符 {a，b，c，d，e，f，g}，对应出现次数为 {5，24，8，17，34，4，13}。用哈夫曼树（最优二叉树）为这 7 种字符构造满足前缀编码条件的不等长编码，下列哪组字符码长符合要求（）？

A. a:4，b:2，c:3，d:3，e:2，f:4，g:3
B. a:6，b:2，c:5，d:3，e:1，f:6，g:4
C. a:3，b:3，c:3，d:3，e:3，f:2，g:3
D. a:2，b:6，c:3，d:5，e:6，f:1，g:4

答案与解析

平台答案：A。

整理解析

选 A。一种合法合并顺序为 4+5=9、8+9=17、13+17=30、17+24=41、30+34=64、41+64=105；其中把原字符 d 的权重 17 与 13 合并，可得 a、b、c、d、e、f、g 的码长 4、2、3、3、2、4、3，加权路径长度为 266。中途有两个权重 17，另一种合并也可能得到不同码长的最优树，故 A 是选项中的正确方案，不是唯一最优码长分配。平台解析图将 13+17 标为 29，应为 30。

题目 037¶

来源：知识点练习「数据结构」第 37 题（原站入口）。

一棵二叉树用二叉链表存储，每个结点有分别指向左、右孩子的两个指针。若树中有 k 个结点，全部结点的空孩子指针共有（）个。

A. k-1
B. k
C. k+1
D. 2k

答案与解析

平台答案：C。

整理解析

对非空树选 C。k 个结点共有 2k 个孩子指针域，而树的 k−1 条边恰好占用 k−1 个非空孩子指针，因此空指针为 2k−(k−1)=k+1。这个计数针对 k≥1；空树没有结点内部的指针域，外部根指针是另一种统计口径。

题目 038¶

来源：知识点练习「数据结构」第 38 题（原站入口）。

对于无向连通图 G，下列说法不正确的是（）。

A. G中任意两个顶点之间均有边存在
B. G中任意两个顶点之间存在路径
C. 从G中任意顶点出发可遍历图中所有顶点
D. G的邻接矩阵是对称矩阵

答案与解析

平台答案：A。

整理解析

选 A。连通要求任意两点之间有路径，不要求每对顶点直接相邻；任意两点都有边是完全图的条件。无向图的邻接关系对称，连通性也保证从任意顶点可遍历全图。平台所说“不一定有边”应理解为“两点之间不一定有直接边”，不能理解为多个顶点的连通图可以一条边都没有。

题目 039¶

来源：知识点练习「数据结构」第 39 题（原站入口）。

队列遵循先进先出规则。若采用循环单链表表示队列，下列说法正确的是（）。

A. 入队列和出队列操作都不需要遍历链表
B. 入队列和出队列操作都需要遍历链表
C. 入队列操作需要遍历链表而出队列操作不需要
D. 入队列操作不需要遍历链表而出队列操作需要

答案与解析

平台答案：A。

整理解析

平台选 A，依赖维护尾指针 rear 等实现条件。对不带头结点的循环单链表，rear→next 可直接定位队头；尾部插入并更新 rear、删除队头并修复链接，都可 O(1) 完成，单结点情况需另作处理。原题没有说明保存尾指针：若仅保存队头指针，入队通常要遍历找尾结点，对应 C。循环链接本身不等于必带尾指针。

题目 040¶

来源：知识点练习「数据结构」第 40 题（原站入口）。

n 阶三对角矩阵 A 的非零元素仅位于主对角线和与其平行、紧邻的两条对角线上。现按行压缩存入数组 B：A 的下标从 0 开始，B 的下标从 1 开始，A[0,0] 对应 B[1]，A[n-1,n-1] 对应 B[3n-2]。对非零元素 A[i,j]（0≤i<n，0≤j<n，|i-j|≤1），它应存入 B[（）]。

A. 2i+j-1
B. 2i+j
C. 2i+j+1
D. 3i-j+1

答案与解析

平台答案：C。

整理解析

选 C。A 下标从 0 开始，而 B 从 1 开始。第 i 行（i≥1）之前共有 2+3(i−1)=3i−1 个带内位置，A[i,j] 在本行的序号为 j−i+2，相加得 2i+j+1，首行也适用。代入 (0,0) 得 1，代入 (n−1,n−1) 得 3n−2。它与第 17 题的矩阵下标起点不同，不能直接套用 2i+j−2。

题目 041¶

来源：知识点练习「数据结构」第 41 题（原站入口）。

把图示二叉树按顺序存储方式放入数组 MEM。已知 A、B、C 的下标依次为 1、2、3，那么 D、E、F 的下标依次是多少？

A. 4、5、6
B. 4、7、10
C. 6、7、8
D. 6、7、14

答案与解析

平台答案：D。

整理解析

数组从 1 起编号时，下标 i 的左、右孩子位置分别为 2i、2i+1，缺失孩子的位置仍需保留。原图中 D、E 是 C 的左右孩子，因此为 6、7；F 是 E 的左孩子，下标为 2×7 = 14，选 D。已核对题干指定的 2018-05/d137… 原图，不能把实际结点按层简单挤紧编号。

题目 042¶

来源：知识点练习「数据结构」第 42 题（原站入口）。

无向图有 n 个结点、e 条边，采用邻接矩阵（数组表示法）存储。对整个图进行深度优先遍历，其时间复杂度是哪项？

A. O(n²)
B. O(e²)
C. O(n+e)
D. O(n*e)

答案与解析

平台答案：A。

整理解析

每个顶点至多展开一次，但寻找它的邻接点需检查矩阵一整行的 n 个位置；遍历 n 个顶点共需 O(n²)，选 A。若用邻接表则通常为 O(n+e)。纠错：平台解析提到“把边终点的入度加 1”，那不是深度优先遍历的步骤，DFS 应依据访问标记递归或用栈展开邻接点。

题目 043¶

来源：知识点练习「数据结构」第 43 题（原站入口）。

用单链表实现后进先出的栈，头指针同时作为栈顶指针。入栈与出栈是否需要遍历链表？

A. 两种操作都不需要遍历
B. 两种操作都需要遍历
C. 入栈需要遍历，出栈不需要
D. 入栈不需要遍历，出栈需要

答案与解析

平台答案：A。

整理解析

入栈把新结点接在表头，出栈移除表头并把头指针移向下一结点，两者只需修改少量链接，均为 O(1)，选 A。把栈顶设在表头，使弹出栈顶时无需寻找前驱。

题目 044¶

来源：知识点练习「数据结构」第 44 题（原站入口）。

某二叉树的先序序列为 ABCDEF，中序序列为 BADCFE。依据这两种遍历，可以确定下列哪项成立？

A. 是单支树，即每个非叶子结点都只有一个孩子
B. 高度为 4，即共有 4 层结点
C. 根的左子树为空
D. 根的右子树为空

答案与解析

平台答案：B。

整理解析

先序首项 A 是根，中序在 A 左侧只有 B。右子树根为 C，其左孩子是 D、右孩子是 E，E 的左孩子为 F。因此最长根到叶路径为 A→C→E→F，共 4 层，选 B。根两侧均非空，且 A、C 都有两个孩子，不是单支树。

题目 045¶

来源：知识点练习「数据结构」第 45 题（原站入口）。

从空树开始，依次插入下列哪组关键码，能得到图中的二叉排序树（又称二叉检索树、二叉查找树）？

A. 10 13 17 19 23 27 31 40 65 91
B. 23 40 91 17 19 10 31 65 27 13
C. 23 19 40 27 17 13 10 91 65 31
D. 27 31 40 65 91 13 10 17 23 19

答案与解析

平台答案：B。

整理解析

图中根为 23，因此首项为 10、27 的 A、D 不符；C 会先把 19 放成根的左孩子，而原图该位置是 17。逐项插入 B 可得到左侧 17 的孩子 10、19，10 的右孩子 13；右侧 40 的孩子 31、91，31 的左孩子 27、91 的左孩子 65，与原图一致，选 B。

题目 046¶

来源：知识点练习「数据结构」第 46 题（原站入口）。

图 G 的邻接矩阵见图，行、列顶点顺序均为 v0、v1、v2、v3、v4、v5。第（46）空判断 G 的图类型，第（47）空选择从 v0 开始的一种可能的广度优先遍历顺序。本题回答第（46）空。

A. 无向图
B. 有向图
C. 完全图
D. 强连通图

答案与解析

平台答案：B。

整理解析

矩阵的 v0→v1 位置为 18，而 v1→v0 为 ∞，连接关系不对称，因此是有向图，选 B。v5 没有出边，不能到达其他顶点，故不是强连通图；矩阵中也存在许多未连接的不同顶点对，不是完全图。

题目 047¶

来源：知识点练习「数据结构」第 47 题（原站入口）。

图 G 的邻接矩阵见图，行、列顶点顺序均为 v0、v1、v2、v3、v4、v5。第（46）空判断 G 的图类型，第（47）空选择从 v0 开始的一种可能的广度优先遍历顺序。本题回答第（47）空。

A. v0、v1、v2、v3、v4、v5
B. v0、v2、v4、v5、v1、v3
C. v0、v1、v3、v5、v2、v4
D. v0、v2、v4、v3、v5、v1

答案与解析

平台答案：A。

整理解析

先访问 v0，再发现其邻接点 v1、v2；按编号先处理 v1，可依次发现 v3、v4，之后从 v3 或 v4 发现 v5，得到 A。其余选项都在 v0 的某个直接邻接点尚未访问时就进入了更深一层，不符合 BFS。边权不影响广度优先遍历的层次。

题目 048¶

来源：知识点练习「数据结构」第 48 题（原站入口）。

n 阶三对角矩阵 A 如图，将三条对角线上的元素按行依次存入一维数组 M，且 a_1,1 位于 M[1]。对于 1≤i,j≤n 且位于三条对角线内的 a_i,j，其在 M 中的下标是哪项？

A. i+2j
B. 2i+j
C. i+2j−2
D. 2i+j−2

答案与解析

平台答案：D。

整理解析

对 i≥2，第 i 行前共有首行的 2 项以及 i−2 个完整中间行，即 2+3(i−2)=3i−4 项。本行从列 i−1 开始，a_i,j 是本行第 j−i+2 项，所以一维下标为 3i−4+j−i+2=2i+j−2，选 D。第一行单独代入也得到 a_1,1→M[1]、a_1,2→M[2]。

题目 049¶

来源：知识点练习「数据结构」第 49 题（原站入口）。

已知 3 个结点的二叉树有 5 种形态，按同样的计数规则，4 个结点的二叉树共有多少种？

A. 10
B. 11
C. 14
D. 15

答案与解析

平台答案：C。

整理解析

按区分左右子树、只计形状的规则，固定根后剩余 3 个结点可按 (0,3)、(1,2)、(2,1)、(3,0) 分配。空树、1、2、3 结点树的数量依次为 1、1、2、5，故总数为 1×5+1×2+2×1+5×1=14，选 C。一般式为 T(n)=ΣT(m)T(n−1−m)，m 从 0 到 n−1，T(0)=1。纠错：平台文字说明把乘积首项误写成 A[N]，应为 A[M]；其公式图片本身正确。

题目 050¶

来源：知识点练习「数据结构」第 50 题（原站入口）。

双端队列的 A、B 两端都允许入队和出队，但要求每个元素从哪端进入，就必须从同一端离开。对 4 个元素 a、b、c、d，前 2 个 a、b 按顺序全部从 A 端进入，后 2 个 c、d 按顺序全部从 B 端进入。按这一入队安排，以下哪种出队顺序不可能得到？

A. d、a、b、c
B. d、c、b、a
C. b、a、d、c
D. b、d、c、a

答案与解析

平台答案：A。

整理解析

按题目先全部入队再考察出队的口径，队列由 A 到 B 排列为 b、a、c、d。A 端必须先出 b 后出 a，B 端必须先出 d 后出 c，两组可交错。A 项把 a 排在 b 前面，不可实现；其余三项均保持这两个先后约束，故选 A。

题目 051¶

来源：知识点练习「数据结构」第 51 题（原站入口）。

n 阶对称矩阵 A 的下三角部分（含主对角线）按行存入数组 S。矩阵下标从 0 开始，且 S[1]=A[0][0]。若 A[i][j] 对应 S[k]，在 i≤j 时，k 与 i、j 的关系是哪项？

A. k=i(i+1)/2+j−1
B. k=j(j+1)/2+i+1
C. k=i(i+1)/2+j+1
D. k=j(j+1)/2+i−1

答案与解析

平台答案：B。

整理解析

i≤j 时利用对称性 A[i][j]=A[j][i]，实际访问存储的下三角位置。第 j 行前有 1+2+…+j=j(j+1)/2 项，本行到列 i 共 i+1 项，所以 k=j(j+1)/2+i+1，选 B。纠错：n 阶矩阵从 0 编号时末下标为 n−1，平台示意中写到 A[n] 的额外行列越界；它不应改变上述计数。

题目 052¶

来源：知识点练习「数据结构」第 52 题（原站入口）。

某二叉树的中序序列为 {20,30,10,50,40}，先序序列为 {10,20,30,40,50}。它的后序遍历序列是哪项？

A. 50，40，30，20，10
B. 30，20，10，50，40
C. 30，20，50，40，10
D. 20，30，10，40，50

答案与解析

平台答案：C。

整理解析

先序首项 10 为根。中序将左侧分成 20、30，右侧分成 50、40；左子树根 20 的右孩子为 30，右子树根 40 的左孩子为 50。按左、右、根进行后序遍历，得到 30、20、50、40、10，选 C。

题目 053¶

来源：知识点练习「数据结构」第 53 题（原站入口）。

一棵树有 n 个结点，所有非叶子结点都恰有 k 棵子树，即这些结点的度均为 k。叶子数应如何表示？

A. [n(k+1)−1]/k
B. [n(k+1)+1]/k
C. [n(k−1)+1]/k
D. [n(k−1)−1]/k

答案与解析

平台答案：C。

整理解析

设非叶子数为 I，树的边数既是 n−1，也是 kI，所以 I=(n−1)/k。叶子数为 n−I=[n(k−1)+1]/k，选 C。公式采用 k≥1 的通常情形，且实际树须满足 n−1 能被 k 整除。

题目 054¶

来源：知识点练习「数据结构」第 54 题（原站入口）。

下图是一幅有向图。第（54）空询问其邻接矩阵的行列规模；采用邻接链表时，已知顶点 1 有 2 个边表结点，顶点 5 有 0 个，第（55）空依次询问顶点 2、3 的边表结点数。本题回答第（54）空。

A. 5×5
B. 5×7
C. 7×5
D. 7×7

答案与解析

平台答案：A。

整理解析

原图有 5 个顶点，邻接矩阵每一行、每一列都对应一个顶点，所以规模为 5×5，选 A。图中有多少条弧并不改变矩阵的行列数。

题目 055¶

来源：知识点练习「数据结构」第 55 题（原站入口）。

下图是一幅有向图。第（54）空询问其邻接矩阵的行列规模；采用邻接链表时，已知顶点 1 有 2 个边表结点，顶点 5 有 0 个，第（55）空依次询问顶点 2、3 的边表结点数。本题回答第（55）空，选项中的两个数依次对应顶点 2、3。

A. 2、1
B. 2、2
C. 3、4
D. 4、3

答案与解析

平台答案：B。

整理解析

由顶点 1 的表结点数为 2、顶点 5 为 0，可知这里按出边建立邻接表。原图中 2→4、2→5，3→2、3→4，因此两者出度都是 2，选 B。此处统计边表结点，不把顶点自身的表头算进去。

题目 056¶

来源：知识点练习「数据结构」第 56 题（原站入口）。

某文档使用 5 种字符，字符及出现频率见表：a、b、c、d、e 分别为 40%、10%、20%、16%、14%。采用 Huffman 编码压缩，第（56）空求单词 cade 的编码，第（57）空求文档的“压缩比”。本题回答第（56）空。

A. 1110110101
B. 1100111101
C. 1110110100
D. 1100111100

答案与解析

平台答案：A。

整理解析

按平台解析选择的码表，a=0、b=100、c=111、d=110、e=101，所以 cade 连接为 111|0|110|101，即 A。题面条件不足：仅给频率不能唯一确定每条分支的 0/1，互换 c、d 的左右位置或 b、e 的左右位置不会改变最优码长，四个选项都可对应合法 Huffman 码表。平台 A 依赖其采用的分支约定，不能说原题无条件只有 A。

题目 057¶

来源：知识点练习「数据结构」第 57 题（原站入口）。

某文档使用 5 种字符，字符及出现频率见表：a、b、c、d、e 分别为 40%、10%、20%、16%、14%。采用 Huffman 编码压缩，第（56）空求单词 cade 的编码，第（57）空求文档的“压缩比”。本题回答第（57）空。

A. 20%
B. 25%
C. 27%
D. 30%

答案与解析

平台答案：C。

整理解析

若压缩前用最短定长二进制码表示 5 种字符，每字符需 3 位。Huffman 合并权重为 10+14=24、16+20=36、24+36=60、40+60=100，得到 a 长 1 位、其余长 3 位，平均为 0.4×1+0.6×3=2.2 位。节省率为 (3−2.2)/3≈26.67%，取整约 27%，选 C。纠错与口径：这实际是空间节省率；压缩后/压缩前为约 73.33%，且计算未计码表、文件头等开销。

题目 058¶

来源：知识点练习「数据结构」第 58 题（原站入口）。

以下关于 Huffman 树的说法，哪项错误？

A. 叶子权值越大，离根越近
B. 不存在只有一棵子树的结点
C. 树的结点总数一定为奇数
D. 权值相同的结点到根的路径长度一定相同

答案与解析

平台答案：D。

整理解析

平台选 D：例如 3 个叶子的权重全为 1，Huffman 树的叶深可以是 1、2、2，同权值不保证同深度。标准二叉 Huffman 树每次合并两个结点，没有度为 1 的结点，叶子数为 L 时总数为 2L−1。表述限定：A 的“越近”应理解为较大权重的叶深不更大，可能相等，并非权值一增大就严格更靠近根。

题目 059¶

来源：知识点练习「数据结构」第 59 题（原站入口）。

用数据元素在存储空间中的相对位置表示它们之间的逻辑关系，是哪种存储方式的特征？

A. 顺序存储
B. 链表存储
C. 索引存储
D. 哈希存储

答案与解析

平台答案：A。

整理解析

顺序存储让逻辑上相邻的元素对应连续的存储位置，借位置关系确定前后次序，选 A。链式结构依靠链接，哈希依靠关键字到地址的映射，均不是这里的位置表达方式。

题目 060¶

来源：知识点练习「数据结构」第 60 题（原站入口）。

有向图见下图。从 v1 出发，第（60）空选择可能的深度优先序列，第（61）空选择可能的广度优先序列。候选序列如下：

① v1 v2 v3 v4 v5 ② v1 v3 v4 v5 v2 ③ v1 v3 v2 v4 v5 ④ v1 v2 v4 v5 v3

本题回答第（60）空。

A. ①②③
B. ①③④
C. ①②④
D. ②③④

答案与解析

平台答案：D。

整理解析

若 DFS 先到 v2，就必须先沿其未访问的出边去 v4 或 v5，不能立即回到 v1 再去 v3，所以①不可能。②可先走 v1→v3→v4→v5，回溯后到 v2；③可走 v1→v3→v2→v4→v5；④可先走 v1→v2→v4→v5，回溯后到 v3。因此选 D。

题目 061¶

来源：知识点练习「数据结构」第 61 题（原站入口）。

有向图见下图。从 v1 出发，第（60）空选择可能的深度优先序列，第（61）空选择可能的广度优先序列。候选序列如下：

① v1 v2 v3 v4 v5 ② v1 v3 v4 v5 v2 ③ v1 v3 v2 v4 v5 ④ v1 v2 v4 v5 v3

本题回答第（61）空。

A. ①②
B. ①③
C. ②③
D. ③④

答案与解析

平台答案：B。

整理解析

v2、v3 是 v1 的直接邻接点，BFS 必须先访问完这一层，才访问 v4、v5。按邻接点次序不同，①和③都可实现；②、④在第一层尚未完成时进入了更深一层，故选 B。

题目 062¶

来源：知识点练习「数据结构」第 62 题（原站入口）。

简单无向连通图 G 有 n 个顶点。它最少、最多分别能有多少条边？

A. n，n²/2
B. n−1，n(n−1)/2
C. n，n(n−1)/2
D. n−1，n²/2

答案与解析

平台答案：B。

整理解析

连通图至少含一棵生成树，需要 n−1 条边；简单无向图每对不同顶点至多一条边，最多有组合数 n(n−1)/2 条，选 B。取树和完全图时分别达到两个界限。

题目 063¶

来源：知识点练习「数据结构」第 63 题（原站入口）。

栈 S 和队列 Q 初始均为空，元素 a,b,c,d,e,f 依次进入 S；每次从 S 弹出后立即进入 Q。若最终出队顺序为 b,d,f,e,c,a，S 元素最多时，从栈底到栈顶依次是什么？

A. a,b,c
B. a,c,d
C. a,c,e,f
D. a,d,f,e

答案与解析

平台答案：C。

整理解析

队列保持入队次序，所以出栈顺序也为 b,d,f,e,c,a。先压 a、b 弹 b，再压 c、d 弹 d，此时栈为 a、c；随后压 e、f 才能弹出 f，栈达到最大 4 项：a、c、e、f，选 C。之后连续弹 e、c、a 即可。

题目 064¶

来源：知识点练习「数据结构」第 64 题（原站入口）。

在二叉树结点总数固定时，下列哪一类树一定能达到最小高度？

A. 二叉排序树
B. 完全二叉树
C. 线索二叉树
D. 最优二叉树

答案与解析

平台答案：B。

整理解析

高度为 h 的二叉树最多容纳 2^h−1 个结点。完全二叉树逐层尽量填满，达到给定结点数所允许的最小高度，选 B。它不一定是唯一达到该高度的形状；排序、线索化或最小带权路径长度都不直接保证最小高度。

题目 065¶

来源：知识点练习「数据结构」第 65 题（原站入口）。

以下哪一组是稀疏矩阵常用的压缩存储结构？

A. 二维数组和双向链表
B. 三元组顺序表和十字链表
C. 邻接矩阵和十字链表
D. 索引顺序表和双向链表

答案与解析

平台答案：B。

整理解析

稀疏矩阵只需记录非零元素及其行、列位置。三元组顺序表保存“行、列、值”，十字链表把非零结点同时接入相应行链和列链，因此选 B。

题目 066¶

来源：知识点练习「数据结构」第 66 题（原站入口）。

两个顺序栈共用 V[1..n]，栈 1、栈 2 的栈底分别在 V[1]、V[n]。top[i] 表示第 i 个栈的栈顶位置（i=1,2），两栈都空时 top[1]=1、top[2]=n。共存满 n 个元素时，满足哪个条件？

A. top[1]=top[2]
B. top[1]+top[2]==1
C. top[1]+top[2]==n
D. top[1]−top[2]==1

答案与解析

平台答案：D。

整理解析

按题设初值及平台图示，top 实际指向各栈下一可用位置，而非最后一个元素。两栈的元素数分别为 top[1]−1、n−top[2]，相加等于 n 时，得到 top[1]−top[2]=1，选 D。若 top[1]=top[2]，仍剩一个可用单元，不能直接套用其他栈顶指针约定下的判满公式。

题目 067¶

来源：知识点练习「数据结构」第 67 题（原站入口）。

采用循环队列能带来下列哪项优点？

A. 入队、出队可在同一端点操作
B. 入队、出队均无需移动其他元素
C. 不会出现队列满
D. 不会出现队列空

答案与解析

平台答案：B。

整理解析

循环队列通过首尾下标按容量取模回绕，复用前端释放的空间，无需为入队或出队整体搬移其他元素，选 B。纠错：平台称头部“不为空继续存放”不妥，只有空闲位置才能写入；循环队列仍会真正空或满，可用计数、标志位或预留一格来区分。

题目 068¶

来源：知识点练习「数据结构」第 68 题（原站入口）。

二叉树高度按层数计算：空树为 0，仅根结点为 1。若共有 1024 个结点，高度可以取哪个整数区间中的任一值？

A. (10,1024)
B. [10,1024]
C. (11,1024)
D. [11,1024]

答案与解析

平台答案：D。

整理解析

10 层最多容纳 2¹⁰−1=1023 个结点，因此最小高度是 11；将全部 1024 个结点连成单支树可达到高度 1024，两个端点均可取，中间整数高度也可构造，选 D。纠错：最大高度来自同一棵树的一条长链，不能按平台所说把 1024 棵单结点树的高度相加。

题目 069¶

来源：知识点练习「数据结构」第 69 题（原站入口）。

对有向图 G 得到一条拓扑序列，其中 Vi 排在 Vj 前。由此一定能推出哪项？

A. 一定有弧 ⟨Vi,Vj⟩
B. 一定没有弧 ⟨Vj,Vi⟩
C. 一定有从 Vi 到 Vj 的路径
D. 一定有从 Vj 到 Vi 的路径

答案与解析

平台答案：B。

整理解析

拓扑序列要求每条弧的起点先于终点；若存在 Vj→Vi，就必须把 Vj 放在 Vi 前面，与题设矛盾，故选 B。两个互不依赖的顶点也可按此先后排列，所以不能反推一定存在正向的弧或路径。

题目 070¶

来源：知识点练习「数据结构」第 70 题（原站入口）。

文件中字符 a、b、c、d、e、f 的频率见表，依次为 45%、13%、12%、16%、9%、5%。采用 Huffman 编码，第（70）空求 a、c 的码长；第（71）空给出比特序列 110001001101 并询问其“编码”，选项为字符序列。本题回答第（70）空，两个长度依次对应 a、c。

A. 1 和 3
B. 1 和 4
C. 3 和 3
D. 3 和 4

答案与解析

平台答案：A。

整理解析

依次合并最小权重：5+9=14、12+13=25、14+16=30、25+30=55、45+55=100。a 位于根下一层，c 从权重 12 经 25、55 到根，故码长分别为 1、3，选 A。分支的 0/1 标号可交换，但不改变这里的码长。

题目 071¶

来源：知识点练习「数据结构」第 71 题（原站入口）。

文件中字符 a、b、c、d、e、f 的频率见表，依次为 45%、13%、12%、16%、9%、5%。采用 Huffman 编码，第（70）空求 a、c 的码长；第（71）空给出比特序列 110001001101 并询问其“编码”，选项为字符序列。本题回答第（71）空。

A. face
B. bace
C. acde
D. fade

答案与解析

平台答案：A。

整理解析

按平台解析所采用的码表，f=1100、a=0、c=100、e=1101，故比特串可分为 1100|0|100|1101，译为 face，选 A。纠错：由比特恢复字符是译码，不是题干所称的编码。仅给频率仍不足以固定左右分支的 0/1，这一具体译码依赖平台码表，不能视为未约定码表时的唯一结果。

同材料可参照第 70 题。

题目 072¶

来源：知识点练习「数据结构」第 72 题（原站入口）。

树 T 的度为 4，其中度为 4、3、2、1 的结点数分别为 7、5、8、10。T 有多少个叶子结点？原题注释把“结点的度”描述成树中结点个数，并将结点度的最大值称为树的度。

A. 30
B. 35
C. 40
D. 49

答案与解析

平台答案：C。

整理解析

记叶子数为 n0。树的边数等于各结点孩子数之和，也等于总结点数减 1，因此 n0=1+(4−1)×7+(3−1)×5+(2−1)×8+(1−1)×10=40，选 C。纠错：结点的度是它的孩子或子树数量，不是整棵树的结点数；本题为度最大 4 的一般树，平台也不应称其为二叉树题。

题目 073¶

来源：知识点练习「数据结构」第 73 题（原站入口）。

图 G 的邻接表中，表示边的表结点总数为奇数。按通常的邻接表存储约定，可以判断哪项？

A. 顶点数为奇数
B. 顶点数为偶数
C. 是无向图
D. 是有向图

答案与解析

平台答案：D。

整理解析

通常无向边在两个端点的邻接表中各记录一次，e 条边对应 2e 个边表结点，一定为偶数。现在表结点为奇数，按此约定应是有向图，选 D，与顶点个数的奇偶无关。纠错：平台把无向图的“边表结点数为偶数”误说成“边数为偶数”；无向图本身完全可以有奇数条边。

题目 074¶

来源：知识点练习「数据结构」第 74 题（原站入口）。

栈初始为空，元素按 1,2,3,…,n 的次序入栈，出栈序列记为 p1,p2,p3,…,pn。已知 p3=4，以下哪组数不可能依次作为 p1、p2？

A. 6,5
B. 2,3
C. 3,1
D. 3,5

答案与解析

平台答案：C。

整理解析

若先弹出 3，则 1、2 都已入栈且 2 压在 1 上面，在不先弹 2 的情况下，第二个不可能是 1，所以选 C。其他三项可分别形成前三个输出 6,5,4；2,3,4；3,5,4。条件说明：选项默认 n 至少为 6；若 n 更小，还会出现数字超出入栈序列的额外不可行项。

题目 075¶

来源：知识点练习「数据结构」第 75 题（原站入口）。

m、n 是同一棵二叉树中的两个结点。要使中序遍历时 n 先于 m，下列哪项符合题目对左右位置的描述？

A. m 是 n 的祖先
B. m 是 n 的子孙
C. m 在 n 的左边
D. m 在 n 的右边

答案与解析

平台答案：D。

整理解析

中序按左子树、根、右子树访问，按题目通常的左右位置用语选 D；只有祖先或子孙关系并不能决定顺序。严谨地说，应是 n 在 m 的左子树、m 在 n 的右子树，或两者分别处在最近公共祖先的左、右子树。任意画图坐标中的“右边”本身不是可通用的判据。

题目 076¶

来源：知识点练习「数据结构」第 76 题（原站入口）。

无向图 G 有 n 个顶点、e 条边，用邻接矩阵存储时，矩阵包含多少个元素？

A. n*e
B. n²
C. n²+e²
D. (n+e)²

答案与解析

平台答案：B。

整理解析

矩阵的行、列都按 n 个顶点编号，所以共有 n×n=n² 个元素，选 B，与边数多少无关。纠错：对无自环的普通无向图，一条边对应两个对称的非零项，二值邻接矩阵中应有 2e 个 1，平台写成 e 个不准确。

题目 077¶

来源：知识点练习「数据结构」第 77 题（原站入口）。

对于 m 阶 B-树，以下哪项说法错误？

A. 根最多有 m 棵子树
B. 所有叶子处于同一层
C. 结点内的关键字有序排列
D. 叶子之间通过指针连接成有序表

答案与解析

平台答案：D。

整理解析

标准 B-树不要求把叶子串成链表，叶子链是常见 B+树的特征，故选 D。m 阶 B-树的结点最多有 m 个孩子、m−1 个关键字，叶子处于同层。表述修正：B-树是多路平衡查找树，不是平台开头所称的二叉树。

历年真题：2026年5月（考生回忆版）¶

本节收录本卷归入本模块的 5 题；题号沿用试卷编号；同材料的不同小问分别保留。

2026-05 Q027¶

来源：2026年5月软件设计师综合知识真题（考生回忆版）第 27 题（原站试卷目录）。

按各序列给定的先后次序，将关键字插入一棵初始为空的二叉排序树。哪个序列得到的树结构不同于另外三个？

A. (95,65,85,90,115,100,125)
B. (95,85,65,90,115,125,100)
C. (95,115,100,125,85,65,90)
D. (95,85,90,65,115,100,125)

答案与解析

平台答案：A。

整理解析

四棵树的根都是95，右子树都是115带左孩子100、右孩子125。A的左子树以65为根，再连续向右插入85、90；B/C/D的左子树都以85为根、两侧为65和90，所以不同的是A。

2026-05 Q035¶

来源：2026年5月软件设计师综合知识真题（考生回忆版）第 35 题（原站试卷目录）。

以如下邻接矩阵所表示的图为准，判断四项结论中哪项成立。

A. 无向图，且最小生成树唯一
B. 有向图，且拓扑序列唯一
C. 有向图，且强连通
D. 无向图，且不连通

答案与解析

平台答案：C。

整理解析

矩阵不对称，按题目通常约定应读作有向图。用0～6标记各行、列，可从原矩阵读出环0→1→3→6→5→4→2→0，覆盖全部七个顶点；沿环即可让任意两点互达，所以确实强连通，选C。

补充与纠错

“有环”只能排除拓扑排序，不能直接推出强连通。应检查任意两点可达性；本题可以用覆盖全部顶点的上述有向环完成证明。

2026-05 Q040¶

来源：2026年5月软件设计师综合知识真题（考生回忆版）第 40 题（原站试卷目录）。

一棵二叉树的层序遍历为 ABCDEF，中序遍历为 BDAFEC。下列结点关系正确的是（）。

A. D 是 B 的左孩子，E 是 B 的右孩子
B. E 是 C 的右孩子，F 是 E 的右孩子
C. D 是 C 的右孩子，E 是 B 的左孩子
D. E 是 C 的左孩子，F 是 E 的左孩子

答案与解析

平台答案：D。

整理解析

选 D。层序首结点 A 为根，中序被分成左侧 BD、右侧 FEC。再按层序选各子树根，得到 A 的左右孩子为 B、C，D 为 B 的右孩子，E 为 C 的左孩子，F 为 E 的左孩子。

2026-05 Q057¶

来源：2026年5月软件设计师综合知识真题（考生回忆版）第 57 题（原站试卷目录）。

线性表采用顺序存储时，其优点之一是（）。

A. 按需动态分配存储空间
B. 随机访问表中元素
C. 有效利用地址不连续的零碎空间
D. 插入、删除效率高

答案与解析

平台答案：B。

整理解析

选 B。连续存储时可由首地址、下标和元素大小直接定位元素。一般位置的插入、删除往往需要搬移后续元素。动态数组也可动态申请或扩容，因此不能把 A 解释为“顺序存储绝不支持动态分配”；随机访问才是这里的典型优势。

2026-05 Q063¶

来源：2026年5月软件设计师综合知识真题（考生回忆版）第 63 题（原站试卷目录）。

双向循环链表中，要在结点 p 后插入结点 s，正确的操作顺序是（）。

A. p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B. p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;
C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D. s->next=p->next; s->prior=p; p->next->prior=s; p->next=s;

答案与解析

平台答案：D。

整理解析

选 D。先让 s 连接 p 和原后继，再把原后继的 prior 改为 s，最后更新 p 的 next。A、B 过早更新 p->next，随后把 s 的 next 指向自身；C 最后写成 s->prior=s。此顺序约束针对题中这些语句，若另外保存原后继，也可采用其他正确顺序。

2025年下半年软件设计师考试基础知识真题（考生回忆版）¶

本节已整理 2 条来源记录；题号沿用来源，答案与解析默认收起。

2025-11 Q008¶

来源：第 8 题（原站入口）。

下列哪组序列满足大顶堆的条件（）？

A.

50，38，40，28，43，16，25，19
B.

50，37，45，25，16，40，35，19
C.

45，25，15，16，24，20，7，10
D.

55，43，45，48，52，29，75，15

答案与解析

平台答案：B。

整理解析

选B。按完全二叉树的层序编号，大顶堆须满足每个父结点不小于其孩子。B中50≥37、45；37≥25、16；45≥40、35；25≥19。A有38<43，C有15<20，D有43<48、52以及45<75，均违反条件。

2025-11 Q014¶

来源：第 14 题（原站入口）。

以权值集合{0.10，0.32，0.25，0.08，0.25}构造哈夫曼树H，每个权值对应一个叶结点。下列关于根到叶结点路径长度的说法，正确的是（）？

A.

从H的根结点到权值0.25所表示的两个叶结点路径长度不同
B.

从H的根结点到其所有叶结点的路径长度相同
C.

从H的根结点到权值0.08和0.10对应的叶结点路径长度相同
D.

从H的根结点到权值0.32和0.25的两个叶结点路径长度不同

答案与解析

平台答案：C。

整理解析

选C。先合并0.08与0.10得0.18，再将0.18与一个0.25合并成0.43；剩余0.25与0.32合成0.57，最后0.43与0.57合并为根。0.08、0.10的深度均为3，两个0.25与0.32的深度均为2。这里只能根据本组权值作判断，不能推广为哈夫曼树中相同权值的叶子永远等深。

2025年上半年软件设计师考试基础知识真题（考生回忆版）¶

本节已整理 4 条来源记录；题号沿用来源，答案与解析默认收起。

2025-05 Q001¶

来源：第 1 题（原站入口）。

操作数栈初始为空，利用栈计算表达式 a*(b+c)-e。保存操作数或中间结果的栈最多同时需要存放（）个值。

A.

3
B.

1
C.

2
D.

4

答案与解析

平台答案：A。

整理解析

选A。按通常从左到右的表达式求值过程，先依次压入a、b、c，栈中暂有3个值；求出b+c后变为a及一个和，再做乘法只剩一个积。之后压入e完成减法，不会超过3个值。

补充与纠错

这里统计操作数或结果栈，不是运算符栈，并沿用常见从左到右压栈求值的约定；不能把任意重排表达式后的最优寄存器需求混作本题栈深度。

2025-05 Q003¶

来源：第 3 题（原站入口）。

字符集为 {a,b,c,d,e,f,g,h}，各字符的哈夫曼编码见表。比特串 010101100011001001001111 的译码结果为（）。

A.

daceabdg
B.

dabccabg
C.

dfhbabfg
D.

dfaecbfg

答案与解析

平台答案：C。

整理解析

选C。根据题图从左到右按前缀码分段：0101 | 011 | 0001 | 10 | 0100 | 10 | 011 | 11，依次对应d、f、h、b、a、b、f、g，得到dfhbabfg。哈夫曼码没有一个完整码字是另一个码字的前缀，因此可逐段确定字符。

补充与纠错

已独立查看原题编码表和平台解析树；按左0右1读树，与编码表一致。平台解析图如下，仅应放入答案折叠：

2025-05 Q011¶

来源：第 11 题（原站入口）。

链队列Q由带头结点的循环单链表实现，只保留尾指针rear。若队列含n个元素结点，入队、出队的时间复杂度依次是（）。

A.

O(1)、O(1)
B.

O(1)、O(n)
C.

O(n)、O(1)
D.

O(n)、O(n)

答案与解析

平台答案：A。

整理解析

选A。rear.next指向头结点，其next再指向队首元素。入队在rear后、头结点前插入新结点，再移动rear；出队修改头结点的next即可。两种操作都只改常数个指针，因此均为O(1)。

补充与纠错

队列只有一个元素时，删除后还须把rear恢复为头结点；空队列入队也应维护环。题干明确“带头结点且仅设rear”，不能把这一O(1)结论推广到任意只给头指针的循环单链表。

2025-05 Q030¶

来源：第 30 题（原站入口）。

将n阶上三角矩阵A按行压缩存入数组B。元素A_ij满足 0≤i,j<n 且 i≤j，它存放在 B[k] 中，B的下标从1开始（k≥1）。k应为（）。

A.

-i²/2+(n+½)i+j-n
B.

-i²/2+(n+½)i+j-1
C.

-i²/2+(n-½)i+j
D.

-i²/2+(n-½)i+j+1

答案与解析

平台答案：D。

整理解析

选D。第0至第i−1行依次存n、n−1、…、n−i+1个元素，总数为in−i(i−1)/2。第i行从列i开始，到列j的行内偏移为j−i；再加上B从1起算，得到k=in−i(i−1)/2+(j−i)+1=−i²/2+(n−½)i+j+1。

补充与纠错

首元素A₀₀应对应B[1]，代入D得1，可作边界校验。该公式用于含主对角线的上三角、按行存储、A从0而B从1编号；换成下三角或改变下标起点时不能直接套用。原页已核实四项均以−i²/2开头，余项依次为A：(n+½)i+j−n，B：(n+½)i+j−1，C：(n−½)i+j，D：(n−½)i+j+1；指数按原式以上标表示。

格式整理说明

A：四项均以−i²/2开头，指数2作用于i；其余符号、数值及选项顺序保留原意。

B：四项均以−i²/2开头，指数2作用于i；其余符号、数值及选项顺序保留原意。

C：四项均以−i²/2开头，指数2作用于i；其余符号、数值及选项顺序保留原意。

D：四项均以−i²/2开头，指数2作用于i；其余符号、数值及选项顺序保留原意。

2024年下半年软件设计师基础知识真题（学员版）¶

本节已整理 9 条来源记录；题号沿用来源，答案与解析默认收起。

2024-11-student Q003¶

来源：第 3 题（原站入口）。

若有向图存在拓扑排序序列，其邻接矩阵必定属于哪类矩阵（）？

A.

三角
B.

一般
C.

对称
D.

稀疏

答案与解析

平台答案：A。

整理解析

平台答案为A，但需要先按某个拓扑序对顶点统一排列。在通常令a_ij表示i→j的约定下，边从序号小的顶点指向序号大的顶点，邻接矩阵才呈严格上三角形。若保留任意原编号，有拓扑序并不保证矩阵已经是三角矩阵。

补充与纠错

条件纠错：例如图只有1→3、3→2两条边，是有向无环图，拓扑序可为1、3、2。但按原编号1、2、3排列时，邻接矩阵在(1,3)和(3,2)都有非零项，既非上三角也非下三角。平台A仅在先按拓扑序重排后成立，题干未给该前提。

2024-11-student Q008¶

来源：第 8 题（原站入口）。

关于单链表的存储特征，哪项说法错误（）？

A.

可随机访问表中的任一元素结点
B.

在表中任意位置插入和删除都不用移动其他元素结点
C.

表中结点所占用存储空间的地址不必是连续的
D.

所需空间与结点个数成正比

答案与解析

平台答案：A。

整理解析

选A。单链表必须沿链接逐结点定位，不能像数组那样按下标常数时间随机访问。插入或删除在已定位相关结点后主要修改链接，无须整体移动其余结点；查找前驱等定位工作仍可能耗时。

2024-11-student Q014¶

来源：第 14 题（原站入口）。

平衡二叉树要求每个结点左右子树的高度差不超过1。高度为5时，最少需要多少个结点（）？

A.

15
B.

16
C.

12
D.

11

答案与解析

平台答案：C。

整理解析

选C。按空树高0、单结点高1计，最少结点数满足N(h)=1+N(h−1)+N(h−2)，其中N(0)=0、N(1)=1。依次得到N(2)=2、N(3)=4、N(4)=7、N(5)=12。

补充与纠错

平台解析“每个结点都只有一个子结点”错误：沿单链形成的高树会违反AVL高度差条件。最少结点形态应递归取高度h−1与h−2的两棵最小AVL子树。若采用边数定义高度，数值口径也会改变；本题平台按层数定义高度。

2024-11-student Q019¶

来源：第 19 题（原站入口）。

用初始为空的栈S暂存运算符，将中缀表达式196+(48.5-5*7)/9转换成题中给定的后缀式196 48 5 7*-9/+。转换过程中S最多同时存放多少个元素（）？

A.

3
B.

4
C.

2
D.

5

答案与解析

平台答案：B。

整理解析

选B。中缀转后缀时，把运算符和左括号按优先级规则暂存。在扫描到5*之后，S自底向顶为+、(、−、*，达到4个；读到右括号时依次弹出乘号、减号并移除左括号。后续处理除号时峰值不会超过4。

补充与纠错

平台解析用“首个运算符前有4个操作数”作理由，实际是在说明后缀求值的操作数栈，不能据此证明本题运算符栈容量。原页截图已核实：中缀确为196+(48.5-5*7)/9，给定后缀确为196 48 5 7*-9/+；48.5与48不一致是原题问题。正确对应的后缀应为196 48.5 5 7 * - 9 / +。本题原式、选项和平台B均保留，这一数字差异不改变运算符栈峰值。

2024-11-student Q028¶

来源：第 28 题（原站入口）。

用权值集合{0.30,0.25,0.25,0.12,0.08}构造哈夫曼树，每个权值对应一个叶结点。以下关于根到叶路径长度的说法，正确的是（）？

A.

从根结点到权值0.12和0.08所表示的叶结点路径长度相同
B.

从根结点到权值0.30所表示的叶结点路径最长
C.

从根结点到所有叶结点的路径长度相同
D.

从根结点到权值0.25所表示的两个叶结点路径长度不同

答案与解析

平台答案：A。

整理解析

选A。先合并0.08与0.12得0.20，再与一个0.25合成0.45；另一个0.25与0.30合成0.55，最后合成根。0.08与0.12的深度均为3，两个0.25及0.30的深度均为2。

补充与纠错

在本组给定权值下，0.30和两个0.25的深度都能明确算得2，不能像平台解析那样说两个0.25可能深度不同；一般哈夫曼树中等权叶子未必等深，但不能把一般可能性当成本题计算结果。

2024-11-student Q029¶

来源：第 29 题（原站入口）。

n阶对称矩阵Mt的下三角部分（含主对角线）按行压缩存入数组Sp[N]，Mt[0][0]对应Sp[0]。对0≤i，j<n且i≥j，Mt[i][j]对应哪个数组元素（）？

A.

Sp[j*(j+1)/2+i]
B.

Sp[i*(i+1)/2+j]
C.

Sp[i*(n-1)+j]
D.

Sp[j*(n-1)+i]

答案与解析

平台答案：B。

整理解析

选B。第i行之前共存1+2+⋯+i=i(i+1)/2个元素；本行从列0开始，到第j列再前进j个位置。数组从0编号，因此下标为i(i+1)/2+j，无须再加1。

2024-11-student Q041¶

来源：第 41 题（原站入口）。

无向图G不连通，共有28条边。图G至少需要（）个顶点。

A.

7
B.

9
C.

6
D.

8

答案与解析

平台答案：B。

整理解析

选B。对有v个顶点的非连通简单无向图，最多的边集中在v−1个顶点构成的完全图中，另留一个孤立点，故边数上界为(v−1)(v−2)/2。v=8时最多21条，不够28；v=9时可由K₈加孤立点达到28条，因此最少9个顶点。

补充与纠错

题干未显式写“简单图”，平台答案沿用无重边、无自环的常见教材约定。若允许平行边，顶点数下界会改变，例如两个顶点间放28条重边，再加一个孤立点即可；不能把9推广到任意多重图。

2024-11-student Q044¶

来源：第 44 题（原站入口）。

简单有向图G=(V,E)有n个顶点、m条弧。以下叙述中不正确的是（）。

A.

所有顶点的入度之和等于出度之和
B.

邻接矩阵不一定是对称矩阵
C.

m最大为n*(n-1)
D.

m大于等于n

答案与解析

平台答案：D。

整理解析

选D。简单有向图可以没有弧，例如n=3、m=0，故不存在一般性的m≥n下界。每条弧分别贡献一个入度和一个出度，两者总和都为m；最多可有n(n−1)条弧。有向关系不要求双向同时存在，所以邻接矩阵未必对称。

补充与纠错

这里的简单有向图允许两个不同顶点之间各有一条反向弧，但不允许同方向重弧或自环；若另外要求强连通等条件，边数下界才会改变。

2024-11-student Q053¶

来源：第 53 题（原站入口）。

下面的二叉树表示哪一个算术表达式（）？其中*、/、+依次表示乘法、除法和加法。

A.

a/b+c*d
B.

a/(b+c)*d
C.

a/(b+c*d)
D.

a/((b+c)*d)

答案与解析

平台答案：D。

整理解析

选D。根节点是除法，左操作数为a，右操作数是乘法子树；该乘法的左子树为b+c，右叶子为d，所以整个表达式为a/((b+c)*d)。括号必须保留，才能保持树规定的运算次序。

补充与纠错

中序遍历给出的操作数、运算符顺序必须结合子树括号理解；只写线性序列而去掉必要括号，会改变表达式含义。

2024年上半年软件设计师考试综合知识（专业解析+参考答案）¶

本节已整理 5 条来源记录；题号沿用来源，答案与解析默认收起。

2024-05 Q006¶

来源：第 6 题（原站入口）。

【考生回忆版】树中一个结点的度是它的孩子结点数，树的度是各结点度数的最大值。树T的度为4，其中度为4、3、2、1的结点分别有5、8、6、10个，则叶子结点有（）个。

A.

38
B.

29
C.

66
D.

57

答案与解析

平台答案：A。

整理解析

选A。每个孩子对应一条父子边，故边数为5×4+8×3+6×2+10×1=66。树的结点数比边数多1，共67个；非叶子结点有5+8+6+10=29个，所以叶子数为67−29=38。

2024-05 Q031¶

来源：第 31 题（原站入口）。

【考生回忆版】二维数组A按行优先存储，每个元素占2个存储单元。已知A[0][0]的地址为100，A[3][3]的地址为220，则A[5][5]的地址是（）。

A.

300
B.

310
C.

306
D.

296

答案与解析

平台答案：A。

整理解析

选A。设每行有L列，行优先地址公式为100+2(iL+j)。由100+2(3L+3)=220得L=19，因此A[5][5]地址为100+2(5×19+5)=300。数组下标本身不是地址偏移，必须乘每元素占用的单元数。

2024-05 Q054¶

来源：第 54 题（原站入口）。

图的邻接矩阵如下。从顶点v0开始，下列哪一序列可以是深度优先遍历的结果（）？

A.

v0、v1、v4、v3、v5、v2
B.

v0、v1、v2、v3、v4、v5
C.

v0、v1、v2、v4、v5、v3
D.

v0、v3、v1、v5、v4、v2

答案与解析

平台答案：A。

整理解析

选A。一种合法选择是v0→v1→v4→v3→v5；v5无后继，逐层回退到v1后再访问v2，此时v2的后继v4、v5均已访问。B从v2跳到v3前仍有未访问后继；C到v4后应先访问其后继v3，不能先回退去v5；D从v1不能直接转到v5。

补充与纠错

题干没有规定邻接点的检查次序，应判断选项是否为某种合法DFS。若强制按下标递增选择邻接点，则得到v0、v1、v2、v4、v3、v5；不能擅加该条件后否定A。

2024-05 Q064¶

来源：第 64 题（原站入口）。

把森林F转换成对应的二叉树T后，F的叶子结点数等于T中哪一类结点的数量（）？

A.

T中叶子结点的个数
B.

T中度为1的结点个数
C.

T中右孩子指针为空的结点个数
D.

T中左孩子指针为空的结点个数

答案与解析

平台答案：D。

整理解析

选D。左孩子—右兄弟表示法中，T的左指针表示原树的第一个孩子，右指针表示下一个兄弟。F中的叶子恰好没有孩子，所以对应T中左指针为空的结点；它仍可能有右兄弟，因此不一定是T的叶子。

2024-05 Q070¶

来源：第 70 题（原站入口）。

长度为n且n>1的单链表同时设置了头指针和尾指针。下列哪项操作仍需要遍历链表（）？

A.

删除该单链表的尾结点
B.

在该单链表头部插入一个新结点
C.

删除该单链表的第一个结点
D.

在该单链表尾部插入一个新结点

答案与解析

平台答案：A。

整理解析

选A。删除尾结点需要找到其前驱，单链表无法从尾结点反向到前驱，因此通常要从头遍历，时间为O(n)。头插、头删以及已知尾指针的尾插都可在O(1)时间完成。

补充与纠错

尾插只需令旧尾结点的next指向新结点、新结点的next为空，再更新尾指针。平台所说让新结点指回表头形成循环链表没有必要，并改变了题目给定的普通单链表结构。

2023年下半年软件设计师考试基础知识（专业解析+参考答案）¶

本节已整理 7 条来源记录；题号沿用来源，答案与解析默认收起。

2023-11 Q020¶

来源：第 20 题（原站入口）。

【考生回忆版】线性表用链表存储时，下列哪项不属于这种存储结构的特点（）。

A.

所需空间大小与表长成正比
B.

可随机访问表中的任一元素
C.

插入和删除操作不需要移动元素
D.

无须事先估计存储空间大小

答案与解析

平台答案：B。

整理解析

选B。链表通过链接寻找后续结点，访问第i个元素通常要沿链查找，不能像数组那样按下标直接定位。动态链表按需分配结点，插删通过修改链接完成，无须整体搬移后续元素。

补充与纠错

“插删不搬移元素”不等于任意插删全过程都是O(1)。通常要先寻找位置或前驱，查找可能为O(n)；动态结点也有指针等额外空间开销。

2023-11 Q032¶

来源：第 32 题（原站入口）。

【考生回忆版】给定无向图G=V,E，顶点集V={a,b,c,d e,f}，边集E={(a,b),(a,c),(a,e),(b,e),(c,f),(f,d),(e.d)}。对G进行深度优先遍历，下列哪组顶点序列可得到（）。

A.

a,c,b,d,e,f
B.

a,c,f,d,e,b
C.

a,b,c,d,e,f
D.

a,b,e,c,f,d

答案与解析

平台答案：B。

整理解析

按边集的图示含义，选B。由a访问c，c的未访问邻接点为f，接着可依次走f→d→e→b，得到a,c,f,d,e,b。其余选项都在当前分支尚有可访问邻点时提前转向别处，违反深度优先的推进规则。

补充与纠错

题干中的G=V,E、d e及(e.d)均保留原写法。平台解析图明确连接e与d，可据此理解顶点为a,b,c,d,e,f且最后一边为(e,d)。邻接点选择次序未指定，B只是四个选项中可行的一种DFS结果，并非该图唯一的遍历序列。

2023-11 Q053¶

来源：第 53 题（原站入口）。

对一棵非空二叉树做中序遍历和后序遍历，如果满足下列哪种结构条件，两种遍历会得到相同序列？

A.

每个非叶子结点都只有左子树
B.

每个非叶子结点都只有右子树
C.

每个非叶子结点的度都为1
D.

每个非叶子结点的度都为2

答案与解析

平台答案：A。

整理解析

中序是“左—根—右”，后序是“左—右—根”。当每个非叶结点都只有左子树时，两者都递归退化成“左—根”，所以选A。只有右孩子时两者次序相反；仅限定非叶结点的度为1并不能排除右孩子。

2023-11 Q054¶

来源：第 54 题（原站入口）。

一个队列可以在两端入队，但只能在固定的一端出队。a、b、c、d 按此顺序全部入队，随后才开始出队。以下哪个出队序列无法得到？

A.

dbac
B.

cabd
C.

acdb
D.

bacd

答案与解析

平台答案：C。

整理解析

a先入队，b从任意一端加入后都与a相邻；c、d只能加在两端，无法插到a与b之间，因此出队时a、b必相邻。C的acdb将二者隔开，故不可能。以左端为出队端，后续三次入队取左、右、左可得dbac；取右、左、右可得cabd；取左、右、右可得bacd，另外三项均可实现。

2023-11 Q056¶

来源：第 56 题（原站入口）。

下图给出有向图 G。用邻接矩阵表示该图时，矩阵中有多少个非零元素？

A.

6
B.

12
C.

4
D.

3

答案与解析

平台答案：A。

整理解析

逐条读取箭头可得 V1→V2、V1→V4、V3→V1、V3→V4、V4→V5、V5→V2，共6条有向边。此图无重边，每条边对应邻接矩阵中的一个非零项，所以选A；有向图不需要将每条边按两个方向各计一次。

2023-11 Q057¶

来源：第 57 题（原站入口）。

在 C/C++ 程序中，函数内定义的非静态局部变量，其存储空间分配在哪一区域？

A.

栈区
B.

静态数据区
C.

文本区
D.

自由堆区

答案与解析

平台答案：A。

整理解析

普通自动局部变量通常随函数调用进入栈帧，离开作用域时结束其生存期，本题按典型实现选A。

补充与纠错

实现边界：C/C++规定的是存储期和生存期，并不强制每个局部变量都占物理栈空间，优化后可能使用寄存器或被消除；局部指针指向的动态对象也不因此放在栈上。

2023-11 Q060¶

来源：第 60 题（原站入口）。

一棵用于哈夫曼编码的树共有127个结点，它能为多少个字符生成编码？

A.

64
B.

127
C.

63
D.

126

答案与解析

平台答案：A。

整理解析

二叉哈夫曼树的内部结点都有两个孩子。设叶子数为L，则内部结点数为L−1，总数为2L−1=127，解得L=64。每个字符对应一个叶子，所以选A。

2023年上半年软件设计师考试基础知识（专业解析+参考答案）¶

本节已整理 4 条来源记录；题号沿用来源，答案与解析默认收起。

2023-05 Q057¶

来源：第 57 题（原站入口）。

利用初始为空的操作数栈，对算术表达式 10*(40-30/5)+20 求值。为暂存运算数和中间结果，栈至少要容纳多少个元素？

A.

2
B.

3
C.

4
D.

5

答案与解析

平台答案：C。

整理解析

按通常从左到右读取、依运算优先级求值的方法，后缀次序为 10 40 30 5 / - * 20 +。读入前四个操作数时尚不能归约更靠左的运算，栈中同时有10、40、30、5，共4项；此后每次二元运算使项数减少1，后续入20也不超过该峰值。所以选C。

2023-05 Q058¶

来源：第 58 题（原站入口）。

有5个字符，依据各自使用频率构造哈夫曼编码。以下哪组编码不可能是构造结果？

A.

{111,110,101,100,0}
B.

{0000,0001,001,01,1}
C.

{11,10,01,001,000}
D.

{11,10,011,010,000}

答案与解析

平台答案：D。

整理解析

D中码字000的兄弟分支001缺失，其码树出现只有一个孩子的内部结点，不符合标准二叉哈夫曼树每个内部结点都有两个孩子的结构，故选D。也可算码长的Kraft和：D为2×¼+3×⅛=⅞，而其余三项均为1。

补充与纠错

D仍是合法的前缀码，只是不能作为这5个字符的标准二叉哈夫曼编码结果；不能把“前缀码”与“哈夫曼最优码”混为一谈。将000缩为00仍不产生前缀冲突，也说明原方案有可消除的多余深度。

2023-05 Q059¶

来源：第 59 题（原站入口）。

有向图G包含n个顶点、e条弧，使用邻接表存储。完整进行广度优先遍历的时间复杂度是哪一项？

A.

O(n+e)
B.

O(n²)
C.

O(e²)
D.

O(n*e)

答案与解析

平台答案：A。

整理解析

每个顶点最多入队并处理一次，耗时O(n)；扫描各顶点的邻接链表会把全部e条弧检查一次，耗时O(e)。合计O(n+e)，选A。

补充与纠错

纠错：平台“图的遍历和算法没关系，只和数据结构有关系”过于绝对。这里的结论依赖邻接表、访问标记以及常数时间入队出队等实现条件；邻接矩阵通常需扫描n×n个位置。原页已核实：B、C中的指数均为2，按平方复杂度理解；保留原选项含义和平台A。

格式整理说明

B：仅恢复已核实的上下标或保留原字符的数学排版，未改变选项含义或原顺序。

C：仅恢复已核实的上下标或保留原字符的数学排版，未改变选项含义或原顺序。

2023-05 Q061¶

来源：第 61 题（原站入口）。

一个森林依次包含三棵树，各树结点总数分别为n1、n2、n3。将该森林转换为一棵二叉树后，二叉树根的右子树共有多少个结点？

A.

n1
B.

n1+n2
C.

n3
D.

n2+n3

答案与解析

平台答案：D。

整理解析

按左孩子、右兄弟的转换方法，第一棵树的根作为整棵二叉树的根；其右链从第二棵树的根开始，并继续连接第三棵树的根。整棵二叉树根的右子树因而恰好包含后两棵树的所有结点，共n2+n3，选D。

2022年上半年软件设计师基础知识真题¶

本节新增3道题，沿用本卷原题号；答案与解析默认收起。

2022-05 Q041¶

来源：第41题（原站入口）。

高度为h的满二叉树共有2^h−1个结点。按从上到下、同层从左到右的顺序编号：根为1，其左右孩子为2、3，再下一层为4、5、6、7，依此类推。已知两个结点编号m、n满足n=2m+1，它们是什么关系？

A.

m是n的左孩子
B.

m是n的右孩子
C.

n是m的左孩子
D.

n是m的右孩子

答案与解析

平台答案：D。

整理解析

这种从1开始的层序编号中，编号m的左右孩子分别是2m、2m+1，所以n为m的右孩子，选D。题目已说m、n都是树中存在的结点，不需再假设该编号是否越界。

2022-05 Q065¶

来源：第65题（原站入口）。

对下图用Prim算法求最小生成树。所用算法类别填入（65）。来源关于另一空的原句为“该算法的设计策树的权值是（66。”。

请作答：第65题。

A.

分治法
B.

动态规划法
C.

贪心算法
D.

递归算法

答案与解析

平台答案：C。

整理解析

Prim每次选择跨越“已加入顶点集合”与“尚未加入集合”的最小权边，以扩展生成树，属于贪心，选C。割性质保证这种选择可属于某棵最小生成树。

补充与纠错

原题确写“设计策树”，第66空后也没有右括号，原字样保留。贪心正确性应依据具体问题的贪心选择性质与最优子结构，不能仅用“无后效性”一句作为通用证明。

2022-05 Q066¶

来源：第66题（原站入口）。

对下图用Prim算法求最小生成树。所用算法类别填入（65）。来源关于另一空的原句为“该算法的设计策树的权值是（66。”。

请作答：第66题。

A.

15
B.

18
C.

24
D.

27

答案与解析

平台答案：A。

整理解析

例如从A开始依次取AC(1)、CF(4)、FD(2)、CB(5)、BE(3)，每一步都取跨越当前已选顶点集合的最轻边，5条边连通6个顶点且无环，权值和为15，选A。

补充与纠错

平台列出的AC、DF、BE、CF、BC是一组最小生成树边，但该列举顺序不是从A出发逐步扩展同一连通树的Prim顺序。原题确有“设计策树”和缺失右括号，按原字样保留。