2026年程序员面试数据结构与算法习题

2026年程序员面试：数据结构与算法习题一、选择题（共5题，每题2分）说明：下列每题只有一个正确答案。1.题目：在以下数据结构中，最适合进行快速插入和删除操作的是？A.数组B.链表C.栈D.堆2.题目：快速排序的平均时间复杂度是？A.O(n²)B.O(nlogn)C.O(n)D.O(logn)3.题目：以下哪个不是图的遍历算法？A.深度优先搜索（DFS）B.广度优先搜索（BFS）C.插入排序D.Dijkstra算法4.题目：哈希表解决冲突的常用方法不包括？A.开放地址法B.链地址法C.二分查找法D.哈希函数改进5.题目：二叉搜索树中，删除一个节点后，可能需要进行的调整不包括？A.节点旋转B.重新计算树的平衡因子C.节点合并D.哈希映射二、填空题（共5题，每题2分）说明：请将答案填写在横线上。1.题目：在栈中，最后被插入的元素通常是_______。____________2.题目：二分查找算法适用于_______的数据结构。____________3.题目：平衡二叉树（如AVL树）要求任意节点的左右子树高度差不超过_______。____________4.题目：图的邻接矩阵适用于表示_______的图。____________5.题目：在链表中，删除一个节点需要修改其前驱节点的_______指针。____________三、简答题（共4题，每题5分）说明：请简要回答下列问题。1.题目：简述快速排序和归并排序的优缺点，并说明在什么情况下选择哪种算法。2.题目：解释哈希表的时间复杂度为什么通常接近O(1)，以及可能导致时间复杂度下降到O(n)的情况。3.题目：什么是二叉搜索树（BST）？它和普通二叉树有什么区别？4.题目：为什么链表适合用于实现栈和队列？与数组实现相比，优缺点是什么？四、编程题（共3题，每题15分）说明：请根据要求实现代码或逻辑描述。1.题目：设计一个函数，实现二分查找的递归版本。输入为一个有序数组和一个目标值，输出目标值的索引（若不存在则返回-1）。2.题目：实现一个简单的LRU（最近最少使用）缓存，使用双向链表和哈希表存储键值对，支持`get`和`put`操作。3.题目：给定一个无向图，用邻接表表示，编写DFS算法遍历该图，并打印遍历顺序。假设图用字典表示，键为节点，值为邻接节点列表。五、算法设计题（共2题，每题20分）说明：请详细描述算法逻辑，并分析时间复杂度。1.题目：假设你有一个包含重复元素的数组，请设计一个算法找出所有重复次数超过一半的元素，要求时间复杂度为O(n)，空间复杂度为O(1)。2.题目：给定一个字符串，判断它是否是另一个字符串的子序列。例如，"abc"是"ahbgdc"的子序列，但"axc"不是。请实现一个函数，时间复杂度尽可能低。答案与解析一、选择题答案1.B（链表允许快速插入删除，数组需要移动元素）2.B（快速排序平均时间复杂度为O(nlogn)，最坏为O(n²)）3.C（插入排序是排序算法，非图遍历）4.C（二分查找法用于有序数组，非哈希表冲突解决）5.D（哈希映射与二叉搜索树无关）二、填空题答案1.栈底（LIFO原则）2.有序数组3.14.稠密图5.next（或尾指针，取决于单向/双向链表）三、简答题解析1.快速排序与归并排序的优缺点-快速排序：优点：平均时间复杂度O(nlogn)，空间复杂度O(logn)（递归栈），不稳定排序。缺点：最坏情况O(n²)，对小型数据集效率低于插入排序。适用场景：大数据集，内存足够时。-归并排序：优点：稳定排序，时间复杂度O(nlogn)，最坏情况下仍保持稳定。缺点：需要额外内存空间O(n)，适合链表排序。适用场景：需要稳定排序或链表数据时。2.哈希表时间复杂度分析-理想情况下，哈希函数均匀分布，每次查找、插入、删除时间复杂度为O(1)。-冲突解决导致时间复杂度下降到O(n)：-开放地址法：当大量冲突时，可能需要遍历整个哈希表。-链地址法：冲突节点链表过长时，时间复杂度接近O(n)。3.二叉搜索树（BST）及其与普通二叉树的区别-BST定义：左子树所有节点值小于根节点，右子树所有节点值大于根节点，且无重复值。-区别：BST具有排序性质，而普通二叉树无顺序性。4.链表实现栈/队列的优缺点-栈（LIFO）：链表支持尾插尾删（栈操作），数组需要移动元素。优点：快速操作，空间灵活。缺点：无随机访问能力。-队列（FIFO）：链表头插头删（队列操作），数组需要移动元素。优点：高效操作。缺点：相比数组实现，缓存友好性较低。四、编程题参考实现1.二分查找递归版pythondefbinary_search(arr,left,right,target):ifleft>right:return-1mid=(left+right)//2ifarr[mid]==target:returnmidelifarr[mid]>target:returnbinary_search(arr,left,mid-1,target)else:returnbinary_search(arr,mid+1,right,target)2.LRU缓存实现pythonclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):self._remove_node(node)self._add_node(node)defget(self,key):node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key,value):node=self.cache.get(key)ifnotnode:newNode=Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self.tail.prevself._remove_node(tail)delself.cache[tail.key]else:node.value=valueself._move_to_head(node)3.DFS遍历图pythondefdfs(graph,start,visited=None):ifvisitedisNone:visited=set()visited.add(start)print(start,end='')forneighboringraph[start]:ifneighbornotinvisited:dfs(graph,neighbor,visited)示例输入：`graph={'A':['B','C'],'B':['A','D'],'C':['A'],'D':['B']}`五、算法设计题解析1.重复次数超过一半的元素-思路：摩尔投票算法-初始化候选值和计数器，遍历数组：-若计数器为0，设当前元素为候选值，计数器设为1。-否则，若当前元素等于候选值，计数器加1；否则减1。-最后验证候选值是否满足条件。-时间复杂度O(n)，空间复杂度O(1)。2.子序列判断-思路：双指针法-初始化两个指针，分别指向两个字符串的开始。-遍历较长字符串，若字符匹配，移动较短字符串指针。-若较短字