数据结构与算法面试题精解与刷题

2026年数据结构与算法面试题精解与刷题一、单选题（共10题，每题2分）考察点：基础概念与常见数据结构1.在有序数组中查找一个不存在的元素，最有效的方法是？A.二分查找B.线性查找C.哈希查找D.二叉搜索树查找2.以下哪种数据结构适合实现LRU（最近最少使用）缓存？A.哈希表B.链表C.堆D.树3.快速排序的平均时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)4.在稀疏矩阵中，存储非零元素及其索引最常用的方法是？A.二维数组B.哈希表C.三元组表D.链表5.以下哪个不是图的常用表示方法？A.邻接矩阵B.邻接表C.十六进制表示D.拓扑排序6.平衡二叉搜索树的定义是？A.左右子树高度差不超过1B.所有节点值唯一C.节点度数为2或0D.所有左子节点小于根节点，所有右子节点大于根节点7.深度优先搜索（DFS）的时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(mlogn)8.以下哪种算法适用于最小生成树问题？A.Dijkstra算法B.Floyd-Warshall算法C.Prim算法D.快速排序9.哈希表冲突解决的最常用方法之一是？A.重新哈希B.链地址法C.二分查找D.堆排序10.在多路归并排序中，"多路"指的是？A.子数组数量少B.子数组数量多C.基数小D.时间复杂度高二、多选题（共5题，每题3分）考察点：综合应用与算法分析1.以下哪些属于时间复杂度为O(n²)的算法？A.冒泡排序B.快速排序C.插入排序D.二分查找2.哈希表的主要缺点包括？A.空间换时间B.冲突处理复杂C.无序性D.哈希函数设计困难3.图的遍历方法包括？A.深度优先搜索B.广度优先搜索C.Dijkstra算法D.快速排序4.以下哪些数据结构支持动态扩容？A.链表B.数组C.堆D.栈5.动态规划适用于解决什么类型的问题？A.最优子结构B.重叠子问题C.无后效性D.线性关系三、填空题（共5题，每题2分）考察点：基础概念与术语1.在二叉搜索树中，任意节点的左子树所有值________该节点的值，右子树所有值________该节点的值。（答案：小于；大于）2.快速排序的枢纽元素选择方法有________、________和随机选择。（答案：首元素；尾元素）3.堆是一种特殊的________树，分为________堆和________堆。（答案：二叉；最大；最小）4.在图的邻接表中，每个顶点对应一个链表，链表中的节点表示________和其对应的边权重。（答案：邻接顶点）5.动态规划的状态转移方程通常表示为________=min/max(________)，其中第一项表示当前状态，第二项表示子状态。（答案：dp[i]；dp[i-1]+cost）四、简答题（共5题，每题5分）考察点：算法原理与实现细节1.解释二分查找的适用条件及其时间复杂度。答案：二分查找适用于________的有序数组。其时间复杂度为________，因为每次比较后搜索区间减半。2.如何优化快速排序的枢轴选择，避免最坏情况？答案：可采用________（如首尾中值法）或________（随机选择枢轴）来减少不平衡概率。3.解释哈希表的冲突解决方法“链地址法”的原理。答案：当冲突发生时，将具有相同哈希值的键值对存储在________中，通过________来遍历冲突链表。4.为什么Dijkstra算法不适用于负权边图？答案：因为Dijkstra假设已经访问的节点不会再被更新，但负权边可能导致________。5.解释动态规划的核心思想及其两个关键要素。答案：动态规划通过________来避免重复计算，关键要素包括________和________。五、编程题（共5题，每题10分）考察点：代码实现与算法设计1.实现一个简单的LRU缓存，支持get和put操作。要求：使用哈希表+双向链表实现，get操作返回值并移动节点，put操作若存在则更新，否则插入。2.给定一个无序数组，实现快速排序，要求原地排序。示例：输入`[3,1,4,1,5]`，输出`[1,1,3,4,5]`。3.实现一个函数，判断二叉树是否为完全二叉树。提示：层序遍历时，若遇到非满节点，后续节点必须为叶子节点。4.给定一个图的邻接表，实现拓扑排序。要求：使用DFS或BFS，处理环需返回false。5.实现一个函数，计算字符串的最长回文子串长度。示例：输入`"babad"`，输出`3`（"bab"或"aba"）。答案与解析一、单选题答案1.A2.C3.B4.C5.C6.A7.A8.C9.B10.B解析：-1.二分查找在有序数组中时间复杂度为O(logn)，优于线性查找的O(n)。-4.三元组表能有效存储稀疏矩阵的非零元素，空间利用率高。-6.平衡二叉树的定义是左右子树高度差不超过1（如AVL树、红黑树）。二、多选题答案1.AC2.BD3.AB4.AC5.ABC解析：-2.哈希表缺点是冲突处理复杂（BD），无序性（C）是其特点而非缺点。-5.动态规划需满足最优子结构和重叠子问题（ABC），线性关系（D）不相关。三、填空题答案1.小于；大于2.首元素；尾元素3.二叉；最大；最小4.邻接顶点5.dp[i]；dp[i-1]+cost四、简答题答案1.适用条件：有序数组；时间复杂度：O(logn)。2.优化方法：首尾中值法；随机选择枢轴。3.链地址法原理：相同哈希值存储在链表中；通过头指针遍历。4.不适用原因：负权边可能导致已访问节点权重被误更新。5.核心思想：空间换时间；关键要素：最优子结构；重叠子问题。五、编程题参考实现（Python）1.LRU缓存：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head4.拓扑排序：pythondeftopological_sort(num_nodes,edges):in_degree=[0]num_nodesgraph=[[]for_inrange(num_nodes)]foru,vinedges:graph[u].append(v)in_degree[v]+=1queue=[iforiinrange(num_nodes)ifin_degree[i]==0]result=[]whilequeue:node=queue.pop(0)result.append(node)forneighbo