(2025年)数据结构练习题(带答案)

(2025年)数据结构练习题(带答案)一、顺序表操作题已知顺序表L存储递增整数序列（无重复元素），长度为n（n≥2）。请设计算法，将L中所有奇数移动到偶数前面，且奇数和偶数各自保持原有相对顺序（例如：原序列[2,4,1,3,5,6]处理后为[1,3,5,2,4,6]）。要求时间复杂度为O(n)，空间复杂度为O(1)。答案：采用双指针法。定义两个指针i和j，初始时i=0，j=0。遍历顺序表：1.当L[j]为奇数时，交换L[i]和L[j]，i自增1；2.无论L[j]是否为奇数，j自增1，直到j遍历完整个顺序表。此方法通过i指针记录奇数应放置的位置，j指针遍历寻找奇数，每次交换仅移动奇数到前半部分，偶数自然留在后半部分，且奇数和偶数的相对顺序保持不变。时间复杂度为O(n)，空间复杂度为O(1)。二、链表综合题设有一个带头结点的单链表L，结点结构为（data,next），其中data为整型。请设计算法，将L中值为x的结点全部删除，并将删除的结点按原顺序链接成一个新链表Lx（Lx也带头结点）。要求不允许额外申请结点空间（即只能调整指针）。答案：步骤如下：1.初始化Lx的头结点，定义指针pre_L（指向L当前结点的前驱）、curr_L（指向L当前结点）、tail_Lx（指向Lx的尾结点）。2.pre_L初始化为L，curr_L初始化为L->next，tail_Lx初始化为Lx。3.遍历L：a.若curr_L->data==x，则：i.pre_L->next=curr_L->next（从L中删除该结点）；ii.tail_Lx->next=curr_L（将该结点添加到Lx尾部）；iii.tail_Lx=curr_L（更新Lx尾指针）；iv.curr_L=pre_L->next（继续检查下一个结点）；b.否则，pre_L=curr_L，curr_L=curr_L->next（继续遍历）。4.最后将tail_Lx->next置为NULL。此算法仅通过调整指针完成操作，时间复杂度O(n)，空间复杂度O(1)。三、栈应用题给定一个字符串s，包含括号（()、[]、{}）和其他字符。请设计算法判断括号是否正确匹配（要求：空字符串视为匹配；嵌套和并列括号均需正确匹配；其他字符不影响判断）。若匹配，返回true；否则返回false。答案：使用辅助栈实现：1.遍历字符串s的每个字符c：a.若c是左括号（'(','[','{'），将其压入栈；b.若c是右括号（')',']','}'）：i.若栈为空，说明无对应左括号，返回false；ii.弹出栈顶元素top，检查top与c是否匹配（'('与')'，'['与']'，'{'与'}'），不匹配则返回false；c.其他字符跳过。2.遍历结束后，若栈非空，说明有未匹配的左括号，返回false；否则返回true。示例：s="([)]"，遍历到')'时栈顶是'['，不匹配，返回false；s="{[]}"，遍历结束栈为空，返回true。四、二叉树操作题已知二叉树采用二叉链表存储，结点结构为（data,lchild,rchild）。请设计算法，计算二叉树中所有结点的“权值和”，其中叶结点的权值为其data值，非叶结点的权值为其左子树权值和与右子树权值和的乘积。（例如：叶结点权值=自身值；若某非叶结点左子树权值和为a，右子树为b，则该结点权值=ab，整棵树的权值和为根结点的权值）答案：采用后序遍历递归计算：定义递归函数intcalcWeight(BiTNodeT)：1.若T为空，返回0（空树权值和为0）；2.若T是叶结点（lchild和rchild均为空），返回T->data；3.否则，计算左子树权值和left=calcWeight(T->lchild)，右子树权值和right=calcWeight(T->rchild)；4.返回leftright。整棵树的权值和即为calcWeight(root)。示例：二叉树结构为根结点A（非叶），左孩子B（叶，data=2），右孩子C（非叶）；C的左孩子D（叶，data=3），右孩子E（叶，data=4）。则：D权值=3，E权值=4→C权值=34=12；B权值=2→A权值=212=24，整棵树权值和为24。五、图算法题某城市有n个地铁站（编号0~n-1），地铁线路构成无向图G，边权表示两站之间的距离（正整数）。请设计算法，找到从起点s到终点t的所有最短路径（路径长度等于边权之和，多条路径长度相同则均视为最短）。要求输出路径数量及所有路径（路径用站点编号序列表示）。答案：步骤如下：1.使用Dijkstra算法计算s到所有结点的最短距离d数组；2.构建反向图：遍历原图所有边(u,v,w)，若d[u]+w==d[v]，则在反向图中添加边v→u；同理，若d[v]+w==d[u]，添加边u→v（因无向图，边是双向的）；3.在反向图中从t出发进行深度优先搜索（DFS），回溯所有到s的路径，即为s到t的最短路径。示例：n=4，边为(0-1,1),(0-2,2),(1-3,1),(2-3,1)，s=0，t=3。d[3]=2（路径0-1-3或0-2-3）。反向图中3的前驱是1和2，1的前驱是0，2的前驱是0。DFS从3出发，得到路径3-1-0和3-2-0，反转后为0-1-3和0-2-3，共2条。六、排序算法分析题已知待排序序列为[5,3,8,1,9,2,7,4,6]，回答以下问题：（1）若采用快速排序（以第一个元素为枢轴），写出第一趟排序后的序列；（2）若采用堆排序（小根堆），写出初始建堆后的序列（数组表示）；（3）若采用归并排序（2路归并），写出第二趟归并后的序列（每趟归并指将所有长度为k的子序列两两归并为长度为2k的子序列）。答案：（1）快速排序第一趟（枢轴5）：初始化low=0（元素5），high=8（元素6）。从high向左找比5小的元素：4（索引7），交换low和high位置→[4,3,8,1,9,2,7,5,6]；low=1，high=7。从low向右找比5大的元素：8（索引2），交换→[4,3,5,1,9,2,7,8,6]；low=2，high=7。此时low=high，枢轴归位，第一趟结果：[4,3,2,1,5,9,7,8,6]。（2）小根堆初始建堆（数组下标0~8）：原始数组：[5,3,8,1,9,2,7,4,6]从最后一个非叶结点（索引3，元素1）开始调整：索引3的子结点为7（索引7，元素4）和8（索引8，元素6），1是最小，无需调整；索引2（元素8）的子结点为5（索引5，元素2）和6（索引6，元素7），最小是2，交换8和2→[5,3,2,1,9,8,7,4,6]；索引1（元素3）的子结点为3（索引3，元素1）和4（索引4，元素9），最小是1，交换3和1→[5,1,2,3,9,8,7,4,6]；索引0（元素5）的子结点为1（索引1，元素1）和2（索引2，元素2），最小是1，交换5和1→[1,5,2,3,9,8,7,4,6]；继续调整索引1（元素5），其子结点为3（索引3，元素3）和4（索引4，元素9），最小是3，交换5和3→[1,3,2,5,9,8,7,4,6]。最终初始小根堆数组：[1,3,2,5,9,8,7,4,6]。（3）2路归并排序第二趟：初始序列（长度1）：[5],[3],[8],[1],[9],[2],[7],[4],[6]第一趟归并（长度2）：[3,5],[1,8],[2,9],[4,7],[6]（最后一个单独）；第二趟归并（长度4）：将前四个长度为2的子序列两两归并：归并[3,5]和[1,8]→[1,3,5,8]；归并[2,9]和[4,7]→[2,4,7,9]；剩余[6]单独，第二趟结果：[1,3,5,8,2,4,7,9,6]。七、综合设计题设计一个数据结构“双端优先队列”，支持以下操作：insert(intx)：在队列的任意一端（前端或后端）插入元素x；getMin()：获取队列中的最小元素；getMax()：获取队列中的最大元素；deleteMin()：删除队列中的最小元素；deleteMax()：删除队列中的最大元素。要求各操作的时间复杂度不超过O(logn)（n为队列元素个数）。答案：使用两个平衡二叉搜索树（如红黑树或AVL树）和两个双向链表实现：1.维护一个最小堆结构的平衡树minTree（按值排序）和一个最大堆结构的平衡树maxTree（按值排序），两棵树存储相同元素，用于快速获取和删除最小/最大值（O(logn)）；2.维护一个双向链表list，记录元素的插入顺序，链表头为前端，尾为后端，用于支持任意端插入（O(1)）；3.每个元素在minTree和maxTree中存储其在链表中的结点指针，链表结点存储元素值及在两棵树中的位置信息（如迭代器）。操作实现：insert(x)：将x插入链表前端或后端（用户选择），同时将x插入minTree和maxTree（O(logn)）；getMin()：返回minTree的最小元素值（O(1)）；getMax()：返回maxTree的最