2026年数据结构与算法经典题解集

2026年数据结构与算法经典题解集一、选择题（共5题，每题2分）1.题目：在下列数据结构中，哪个结构是先进先出（FIFO）的？A.栈B.队列C.链表D.树2.题目：快速排序的平均时间复杂度是多少？A.O(n²)B.O(nlogn)C.O(logn)D.O(n)3.题目：以下哪个不是图的常用表示方法？A.邻接矩阵B.邻接表C.顶点数组D.边列表4.题目：二分查找的时间复杂度是多少？A.O(n)B.O(logn)C.O(n²)D.O(nlogn)5.题目：哈希表的主要冲突解决方法不包括？A.开放定址法B.链地址法C.二分法D.双重散列法二、填空题（共5题，每题2分）1.题目：在深度优先搜索（DFS）中，用来记录顶点访问状态的数据结构通常是______。2.题目：堆排序的时间复杂度是______。3.题目：在二叉树中，一个节点的度为______时，称为叶子节点。4.题目：动态规划算法通常用于解决______问题。5.题目：冒泡排序的平均时间复杂度是______。三、简答题（共5题，每题4分）1.题目：简述栈和队列的区别。2.题目：解释什么是二叉搜索树（BST），并说明其性质。3.题目：什么是图的拓扑排序？适用于哪些情况？4.题目：描述哈希表的工作原理，并说明常见的冲突解决方法。5.题目：什么是动态规划？请举例说明其适用场景。四、算法设计题（共3题，每题10分）1.题目：设计一个算法，判断一个无向图是否为连通图。要求说明算法思路，并给出伪代码。2.题目：给定一个字符串，请编写算法找出其中不重复的最长子串，并说明时间复杂度。3.题目：设计一个算法，将一个数组调整为一个最大堆（堆排序的初始步骤），并说明如何利用堆实现TopK问题。五、编程题（共2题，每题15分）1.题目：编写一个函数，实现二分查找算法，输入为一个有序数组和一个目标值，输出目标值的索引或-1（未找到）。要求说明边界条件处理。2.题目：给定一个链表，请编写算法反转链表，并画出反转前后的链表结构。答案与解析一、选择题答案与解析1.答案：B解析：队列是先进先出的数据结构，而栈是先进后出的。链表和树不是特定的FIFO结构。2.答案：B解析：快速排序的平均时间复杂度为O(nlogn)，最坏情况为O(n²)。3.答案：C解析：图的常用表示方法包括邻接矩阵、邻接表和边列表，顶点数组不是图的表示方法。4.答案：B解析：二分查找的时间复杂度为O(logn)，每次将搜索区间减半。5.答案：C解析：二分法是查找算法，不是哈希表的冲突解决方法。其他选项都是常见方法。二、填空题答案与解析1.答案：布尔数组（或哈希集合）解析：DFS通常使用布尔数组或哈希集合记录顶点是否已访问。2.答案：O(nlogn)解析：堆排序对数组进行建堆和调整，时间复杂度为O(nlogn)。3.答案：0解析：度为0的节点称为叶子节点，即没有子节点。4.答案：最优子结构解析：动态规划适用于具有最优子结构的问题，如斐波那契数列。5.答案：O(n²)解析：冒泡排序平均需要两重循环，时间复杂度为O(n²)。三、简答题答案与解析1.答案：-栈：后进先出（LIFO），只允许在一端（栈顶）进行插入和删除操作。-队列：先进先出（FIFO），两端均可操作，但插入在队尾，删除在队头。2.答案：-二叉搜索树：左子树所有节点小于根节点，右子树所有节点大于根节点，左右子树均为BST。性质：1.节点值唯一（或允许重复时，左子树有等于根的节点）。2.搜索效率高（O(logn)）。3.答案：-拓扑排序：将有向无环图（DAG）的顶点排成线性序列，满足每条边的前后关系。适用情况：任务调度、依赖关系问题（如课程安排、工程依赖）。4.答案：-工作原理：通过散列函数将键值映射到数组索引，冲突时通过链地址法或开放定址法解决。冲突解决方法：-链地址法：相同索引的键值存储在链表中。-开放定址法：探测下一个可用位置（如线性探测、二次探测）。-双重散列法：使用多个散列函数解决冲突。5.答案：-动态规划：通过将问题分解为子问题并存储结果（备忘录或数组）避免重复计算。适用场景：最优子结构问题（如背包问题、最长公共子序列）。四、算法设计题答案与解析1.答案：思路：使用DFS或BFS遍历图，若所有顶点都被访问，则图连通。伪代码：DFS(start):visited[start]=trueforeachneighboringraph[start]:ifnotvisited[neighbor]:DFS(neighbor)判断连通：遍历所有顶点，若某个顶点未访问且可达，则图不连通。2.答案：思路：滑动窗口法，维护一个窗口，扩展右边界时检查是否重复，收缩左边界时更新最长子串。伪代码：max_len=0,left=0,char_set=newHashSet()forrightin0ton-1:ifchar_set.contains(s[right]):whiles[left]!=s[right]:char_set.remove(s[left++])char_set.add(s[right])max_len=max(max_len,right-left+1)3.答案：思路：将数组调整为大根堆，堆顶是最大值。TopK问题可利用堆维护当前最大的K个值。建堆伪代码：forifromn/2downto0:heapify(arr,i,n)TopK：初始化大根堆，遍历数组，若当前值小于堆顶则忽略，否则替换堆顶并调整。五、编程题答案与解析1.答案：pythondefbinary_search(arr,target):left,right=0,len(arr)-1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:returnmidelifarr[mid]<target:left=mid+1else:right=mid-1return-1边界处理：检查left和right是否越界，mid计算避免溢出（使用(left+right)//2）。2.答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=curr