数据结构真题大题¶
线性表¶
【2010-42】¶
（13分）设将 \(n(n>1)\)个整数存放到一维数组 R中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R中保存的序列循环左移p(0 个位置，即将 R 中的数据由 \(⟨X_0,X_1,…,X_{n−1}⟩\)变换为 \(⟨X_p,X_{p+1},…,X_{n−1},X_0,X_1,…,X_{p−1}⟩\) 。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++或Java语言描述，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
【2011-42】¶
一个长度为 \(L(L≥1)\)的升序序列 S ，处在第 \(⌈L/2⌉\)个位置的数称为 S 的中位数。例如，若序列\(S1=⟨11,13,15,17,19⟩\) ，则 S1 的中位数是 15 。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列 \(S2=⟨2,4,6,8,20⟩\) ，则 S1 和 S2 的中位数是 11 。现有两个等长的升序序列 A 和 B ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++或Java语言描述，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
【2013-41】¶
（13分）已知一个整数序列\(A=(a_0,a_1,…,a_{n−1})\) ，其中 \(0≤a_i\) 。若存在 \(a_{p1}=a_{p2}=⋯=a_{pm}=x 且 m>n/2(0≤p_k\<n,1≤k≤m)\) ，则称 x 为 A 的主元素。例如 A=(0,5,5,3,5,7,5,5) ，则 5 为主元素；又如 A=(0,5,5,3,5,1,5,7) ，则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A 的主元素。若存在主元素，则输出该元素；否则输出 −1 。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
【2018-41】¶
（13分）给定一个含 n(n≥1) 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
【2020-41】¶
（13分）定义三元组\((a,b,c)\)（ a,b,c 均为正数）的距离 \(D=|a−b|+|b−c|+|c−a|\) 。给定 3 个非空整数集合 S1 、 S2 和 S3 ，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，让算并输出所有可能的三元组 (a,b,c) （其中 a∈S1,b∈S2,c∈S3 ）中的最小距离。例如 S1={−1,0,9} ， S2={−25,−10,10,11} ， S3={2,9,17,30,41} ，则最小距离为 2 ，相应的三元组为 (9,10,9) 。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
【2009-42】¶
（15分）已知一个带有表头结点的单链表，结点结构为|data| link| ，假设该链表只给出了头指针 list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（ k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1 ；否则，只返回 0 。要求：
⑴ 描述算法的基本设计思想。
⑵ 描述算法的详细实现步骤。
⑶ 根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或Java语言实现），关键之处请给出简要注释。
【2012-42】¶
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，’loading’和’being’的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为 datanext ，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在的结点位置p）。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度。
【2015-41】¶
（15分）用单链表保存 m 个整数，结点的结构为data link，且 |data|≤n （ n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：
则删除结点后的 head 为：
要求：
⑴ 给出算法的基本设计思想。
⑵ 使用C或C++语言，给出单链表结点的数据类型定义。
⑶ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑷ 说明你所设计算法的时间复杂度和空间复杂度。
【2019-41】¶
（13分）设线性表\(L=(a_1,a_2,a_3,…,a_{n−2},a_{n−1},a_n)\) 采用带头结点的单链表保存，链表中的结点定义如下：
请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 \(L′=(a_1,a_n,a_2,a_{n−1},a_3,a_{n−2},…)\)。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度。
栈与队列¶
【2019-42】¶
（13分）请设计一个队列，要求满足:
① 初始时队列为空；
② 入队时，允许增加队列占用空间；
③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；
④ 入队操作和出队操作的时间复杂度始终保持为 O(1) 。
请回答下列问题：
⑴ 该队列是应选择链式存储结构，还是应选择顺序存储结构？
⑵ 画出队列的初始状态，并给出判断队空和队满的条件。
⑶ 画出第一个元素入队后的队列状态。
⑷ 给出入队操作和出队操作的基本过程。
树与二叉树¶
【2016-42】¶
（8分）如果一棵非空 k(k≥2) 叉树 T 中每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。
⑴ 若 T 有 m 个非叶结点，则 T 中的叶结点有多少个？
⑵ 若 T 的高度为 h （单结点的树 h=1 ），则 T 的结点数最多为多少个？最少为多少个？
【2017-41】¶
（15分）请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法输入时：
输出的中缀表达式分别为 (a+b)∗(c∗(−d)) 和 (a∗b)+(−(c−d)) 。
二叉树结点的定义如下：
要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
【2012-41】¶
（13分）设有 6 个有序表A、B、C、D、E，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列.要求通过 5 次两两合并，将 5 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。
⑴ 给出完整的合并过程，并求出最坏情况下比较的总次数。
⑵ 根据你的合并过程，描述 N(N≥2) 个不等长升序表的合并策略，并说明理由。
【2014-41】¶
（13分）二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：
$\begin{array}{|c|c|c|} \hline \text{left}& \text{weight}& \text{right} \ \hline \end{array}$
其中叶结点的weight域保存该结点的非负值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：
⑴ 给出算法的基本设计思想；
⑵ 使用C或C++语言，给出二叉树结点的数据类型定义；
⑶ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
【2020-42】¶
若任一个字符的编码都不是其它字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数≥2）的不等长编码，每个字符的编码均为二进制的0、1序列，最长为L位，且具有前缀特性。请回答下列问题：
⑴ 哪种数据结构适宜保存上述具有前缀特性的不等长编码？
⑵ 基于你所设计的数据结构，简述从0/1串到字符串的译码过程。
⑶ 简述判定某字符集的不等长编码是否具有前缀特性的过程。
图¶
【2015-42】¶
（8分）已知含有5个顶点的图G如下图所示。
请回答下列问题：
⑴ 写出图G的邻接矩阵 A （行、列下标均从0开始）。
⑵ 求 \(A^2\)，矩阵 \(A^2\) 中位于0行3列元素值的含义是什么?
⑶ 若已知具有 n(n≥2) 个顶点的图的邻接矩阵为 B ，则 \(B^m(2≤m≤n)\)中非零元素的含义是什么?
【2018-42】¶
（12 分）拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市，题 42 图中无向边上的权值表示两个城市间备选光缆的铺设费用。
题 42 图
请回答下列问题。
(1) 仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。（8 分）
(2) 题 42 图可采用图的哪一种存储结构？给出求解问题 (1) 所使用的算法名称。（2 分）
(3) 假设每个城市采用一个路由器按 (1) 中得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL = 5 的 IP 分组，则 H2 是否可以收到该 IP 分组？（2 分）
【2021-41】¶
（15分）已知无向连通图G由顶点集V和边集E组成，|E| > 0，当G中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为|E|的路径（称为EL路径）。设图G采用邻接矩阵存储，类型定义如下:
typedef struct { // 图的定义
int numVertices, numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
请设计算法int IsExistEL(MGraph G)，判断G是否存在EL路径，若存在，则返回1 ，否则返回0。要求:
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
【2017-42】¶
（8 分）使用 Prim（普里姆）算法求带权连通图的最小（代价）生成树 (MST)。请回答下列问题。
(1) 对下列图 ，从顶点 A 开始求 的 MST，依次给出按算法选出的边。
(2) 图 的 MST 是唯一的吗？
(3) 对任意的带权连通图，满足什么条件时，其 MST 是唯一的？
【2023-41】¶
（13分）已知有向图 G 采用邻接矩阵存储，类型定义如下：
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
将图中出度大于入度的顶点称为 K 顶点。例如在题41图中，顶点 a 和 b 都是 K 顶点。
请设计算法： int printVertices(MGraph G)，对给定的任意非空有向图 G，输出 G 中所有 K 顶点，并返回 K 顶点的个数。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
【2009-41】¶
（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
① 设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点；
② 选择离 u 最近且尚未在最短路径中的一个顶点 v ，加入到最短路径中，修改当前顶点 u=v ；
③ 重复步骤②，直到 u 是目标顶点时为止。
请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。
【2014-42】¶
（10分）某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息（LSI），题42图是根据题42表的接口名构造出来的网络拓扑。
请回答下列问题。
⑴ 本题中的网络可抽象为数据结构中的哪种结构？
⑵ 针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息（LSI）。要求给出链式存储结构的数据定义，并画出对应题42表的链式存储结构示意图（示意图中仅以ID标识结点）。
⑶ 按照迪杰斯特拉（Dijkstra）算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。
【2024-41】¶
（本题 13 分）2023 年 10 月 26 日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序展开，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G采用邻接矩阵存储，类型定义如下：
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图的顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
请设计算法：int uniquely(MGraph G)，判定G是否存在唯一的拓扑序列。若是，则返回1，否则返回0。
要求如下。
(1) 给出算法的基本设计思想。（4 分）
(2) 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（9 分）
【2011-41】¶
（8分）已知有6个顶点（顶点编号为0～5）的有向带权图 G ，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
⑴ 写出图 G 的邻接矩阵 A 。
⑵ 画出有向带权图 G 。
⑶ 求图 G 的关键路径，并计算该关键路径的长度。
查找¶
【2013-42】¶
（10分）设包含 4 个数据元素的集合 S={“do”, “for”, “repeat”, “while”}，各元素的查找概率依次为： \(p_1=0.35,p_2=0.15,p_3=0.15,p_4=0.35\) 。将 S 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2 。请回答：
⑴ 若采用顺序存储结构保存 S ，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
⑵ 若采用链式存储结构保存 S ，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
【2022-41】¶
（13分）已知非空二叉树T的结点值均为正数，采用顺序存储方式保存，数据结构定义如下：
typedef struct { // MAX_SIZE为已定义常量
Elemtype SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
T中不存在的结点在数组SqBiTNode中用-1表示。例如，对于下图所示的两棵非空二叉树T1和T2：
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回true，否则，返回false，要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
【2024-42】¶
（本题 10 分）将关键字数列 20, 3, 11, 18, 9, 14, 7 依次存储到初始值为空、长度为11的散列表HT中，散列函数 H(key)=(key×3)%11 ， H(key) 计算出的初始散列地址为 \(H_0\) ，发生冲突时探查地址序列是 \(H_1,H_2,H_3,…\) ，其中， \(H_k=(H_0+k^2)\%11\) ， k=1,2,3,… 。
请回答下列问题。
(1) 画出所构造的HT，并计算HT的填装因子。（6 分）
(2) 给出在HT中查找关键字14的关键字比较序列。
(3) 在HT中查找关键字8，确认查找失败时散列地址是多少？
【2010-41】¶
（10分）将关键字序列 \(⟨7,8,30,11,18,9,14⟩\)散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 \(H(key)=(key×3)\ mod\ 7\)，处理冲突采用线性探测再散列法，要求装填（载）因子为 0.7 。
⑴ 请画出所构造的散列表。
⑵ 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
排序¶
【2016-43】¶
（15分）已知由 n(n≥2) 个正整数构成的集合 \(A={a_k|0≤k\<n}\)，将其划分为两个不相交的子集 A1 和 A2 ，元素个数分别是 n1 和 n2 ， A1 和 A2 中元素之和分别为 S1 和 S2 。设计一个尽可能高效的划分算法，满足 |n1−n2| 最小且 |S1−S2| 最大。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
【2022-42】¶
（10分）现有 n(n>100000) 个数保存在一维数组 M 中，需要查找 M 中最小的10个数，请回答下列问题。
⑴ 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不需要程序实现。
⑵ 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
【2023-42】¶
（10分）对含有 n(n>0) 个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作区，工作区中能保存 m 个记录，请回答下列问题。
⑴ 若文件中含有 19 个记录，其关键字是 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100；当 m=4 时，可以生成几个初始归并段？各是什么？
⑵ 对任意的 m(n≫m>0) ，生成的第一个初始归并段的长度最大值和最小值分别是多少？
【2021-42】¶
（8分）已知某排序算法如下：
void cmpCountSort(int a[],int b[],int n) {
int i, j, *count;
count = (int *)malloc(sizeof(int) * n); //C++语言: count = new int[n];
for (i = 0; i < n; i++) count[i] = 0;
for (i = 0; i < n - 1; i++)
for (j = i + 1; j < n; j++)
if (a[i] < a[j]) count[j]++;
else count[i]++;
for (i = 0; i < n; i++) b[count[i]]= a[i];
free(count); // C++语言: delete count;
}
请回答下列问题。
⑴ 若有int a[] = {25, -10, 25, 10, 11, 19}, b[6]; ，则调用cmpCountSort(a, b, 6)后数组b中的内容是什么?
⑵ 若a中含有n个元素，则算法执行过程中，元素之间的比较次数是多少?
⑶ 该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。