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

2026年程序员算法与数据结构练习题一、选择题（共10题，每题2分，合计20分）1.题目：在下列数据结构中，插入和删除操作最方便的是（）。A.链表B.数组C.栈D.队列2.题目：下列哪个不是树的特性？（）A.有且只有一个根节点B.每个节点有且只有一个父节点C.可以有多个根节点D.没有循环引用3.题目：快速排序的平均时间复杂度是（）。A.O(n)B.O(nlogn)C.O(n²)D.O(logn)4.题目：下列哪个数据结构适合实现LRU（最近最少使用）缓存？（）A.哈希表B.堆C.双向链表+哈希表D.栈5.题目：二叉搜索树中，任意节点的左子树中的所有节点值都小于该节点的值，右子树中的所有节点值都大于该节点的值，这个性质称为（）。A.完全性B.平衡性C.对称性D.二分性6.题目：下列哪个算法的时间复杂度与输入数据的初始顺序无关？（）A.冒泡排序B.选择排序C.快速排序D.插入排序7.题目：图的邻接矩阵表示法适用于稠密图，其时间复杂度为（）。A.O(n)B.O(n²)C.O(nlogn)D.O(logn)8.题目：下列哪个数据结构是先进先出（FIFO）的？（）A.栈B.队列C.链表D.堆9.题目：在哈希表中，解决哈希冲突的常见方法不包括（）。A.开放寻址法B.链地址法C.二叉搜索树法D.哈希函数优化10.题目：下列哪个算法可以用于查找无序数组中的第k小（或大）的元素？（）A.快速排序B.堆排序C.希尔排序D.二分查找二、填空题（共5题，每题2分，合计10分）1.题目：在二叉树中，节点的深度是从根节点到该节点的路径上的边数，而节点的高度是根节点的高度为0，其他节点的高度是其子树的高度中的最大值加1。2.题目：堆是一种特殊的完全二叉树，分为最大堆和最小堆。在最大堆中，父节点的值总是大于或等于其子节点的值；在最小堆中，父节点的值总是小于或等于其子节点的值。3.题目：哈希表的平均查找时间为O(1)，但在最坏情况下（如哈希冲突严重）会退化到O(n)。常见的哈希冲突解决方法有链地址法和开放寻址法。4.题目：图的深度优先搜索（DFS）是一种遍历图的方法，其基本思想是：从根节点出发，先访问该节点，然后递归地访问其未访问过的邻接节点。广度优先搜索（BFS）则按层次遍历图。5.题目：二分查找要求数据必须是有序的。其基本思想是：比较中间元素与目标值，若中间元素等于目标值则查找成功，否则根据大小关系缩小查找范围，重复上述过程。三、简答题（共5题，每题4分，合计20分）1.题目：简述栈和队列的主要区别，并举例说明它们在实际应用中的场景。2.题目：解释二叉搜索树（BST）的中序遍历结果是什么？并给出一个二叉搜索树的中序遍历示例。3.题目：什么是图的拓扑排序？适用于哪些场景？4.题目：哈希表的负载因子是什么？为什么负载因子不宜过高或过低？5.题目：快速排序的基本步骤是什么？为什么它被称为“分治”算法？四、算法设计题（共3题，每题10分，合计30分）1.题目：设计一个算法，判断一个无向图是否是二分图（即可以将图的节点分成两个集合，使得每条边的两个端点分别属于不同的集合）。要求：-输入：邻接矩阵表示的无向图。-输出：是或否，以及可能的划分方案（如果存在）。2.题目：给定一个包含重复数字的数组，设计一个算法找出所有不重复的组合，且组合中的数字按升序排列。例如，输入`[1,2,2]`，输出`[[1],[2],[1,2],[1,2]]`。3.题目：设计一个算法，实现LRU缓存。要求：-支持`get(key)`和`put(key,value)`操作。-`get(key)`：若存在，返回值并更新访问顺序；若不存在，返回-1。-`put(key,value)`：若已存在，更新值并调整顺序；若不存在，插入键值对，若缓存已满则删除最久未使用的键值对。五、代码实现题（共2题，每题15分，合计30分）1.题目：实现一个二叉搜索树，支持以下操作：-`insert(key)`：插入一个键值对。-`search(key)`：查找一个键值对。-`delete(key)`：删除一个键值对。-要求：`delete`操作需保持二叉搜索树的性质。2.题目：实现一个最小堆，支持以下操作：-`insert(val)`：插入一个元素。-`extract_min()`：弹出并返回最小元素。-`get_min()`：返回最小元素但不删除。-要求：使用数组实现，并保持堆的性质。答案与解析一、选择题答案1.A-解析：链表支持在任意位置进行插入和删除操作，时间复杂度为O(1)；数组插入和删除操作需要移动元素，时间复杂度为O(n)。2.C-解析：树的特点是有且只有一个根节点，每个节点有且只有一个父节点（除根节点），且没有循环引用。可以有多个根节点的结构称为森林。3.B-解析：快速排序的平均时间复杂度为O(nlogn)，但最坏情况下为O(n²)（如已排序数组）。4.C-解析：LRU缓存需要快速访问和删除最久未使用的元素，双向链表支持O(1)的删除操作，结合哈希表实现O(1)的查找。5.D-解析：二叉搜索树的性质是“二分性”，即左子树和右子树分别包含小于和大于该节点的值。6.C-解析：快速排序的平均时间复杂度为O(nlogn)且与输入顺序无关；其他排序算法的时间复杂度与输入顺序相关。7.B-解析：图的邻接矩阵表示法中，每个元素表示两个节点之间是否有边，共有n²个元素，时间复杂度为O(n²)。8.B-解析：队列是先进先出（FIFO）的结构，栈是先进后出（LIFO）。9.C-解析：二叉搜索树法不是哈希表的冲突解决方法，其他三种都是。10.A-解析：快速排序的分治思想可以找到第k小元素；其他算法不直接支持。二、填空题答案1.高度-解析：二叉树的高度是节点深度的最大值加1，用于衡量树的“伸展”程度。2.堆-解析：堆是一种特殊的完全二叉树，分为最大堆和最小堆，常用于优先队列。3.O(1)/O(n)-解析：哈希表的平均查找时间为O(1)，但冲突严重时退化到O(n)。4.深度优先搜索（DFS）/广度优先搜索（BFS）-解析：DFS和BFS是图遍历的两种基本方法，分别按深度和广度顺序访问节点。5.二分查找-解析：二分查找是一种高效的查找算法，适用于有序数据，时间复杂度为O(logn)。三、简答题答案1.栈和队列的主要区别及应用场景-区别：-栈是LIFO（后进先出），队列是FIFO（先进先出）。-栈的操作限制在栈顶，队列的操作限制在队首和队尾。-应用场景：-栈：函数调用栈、表达式求值、括号匹配、深度优先搜索。-队列：广度优先搜索、消息队列、任务调度。2.二叉搜索树的中序遍历-中序遍历结果：按升序排列所有节点值。-示例：给定BST`[5,3,7,2,4,6,8]`，中序遍历为`[2,3,4,5,6,7,8]`。3.图的拓扑排序-定义：对有向无环图（DAG）的节点进行线性排序，使得对于每条有向边`(u,v)`，节点`u`在排序中位于`v`之前。-应用场景：任务调度、依赖关系处理（如课程安排、工程依赖）。4.哈希表的负载因子-定义：负载因子`λ=n/m`，其中n是哈希表中的元素数量，m是哈希表的大小。-原因：-过高：冲突增多，查找时间退化到O(n)。-过低：空间利用率低，浪费内存。5.快速排序的步骤及分治思想-步骤：1.选择一个基准（pivot）。2.分区：将数组分成两部分，左边的元素都小于基准，右边的都大于基准。3.递归：对左右两部分分别进行快速排序。-分治思想：将大问题分解为小问题，逐个解决，最终合并结果。四、算法设计题答案1.二分图判断算法-方法：使用染色法，将节点分为两种颜色（如红色和蓝色），依次遍历每个节点，若发现相邻节点颜色相同则不是二分图。-伪代码：pythondefis_bipartite(graph):color={}fornodeingraph:ifnodenotincolor:color[node]=0#0:uncolored,1:red,-1:bluequeue=[node]whilequeue:current=queue.pop(0)forneighboringraph[current]:ifneighbornotincolor:color[neighbor]=-color[current]queue.append(neighbor)elifcolor[neighbor]==color[current]:returnFalsereturnTruereturnTrue2.不重复组合算法-方法：回溯法，先排序数组，避免重复，使用标记数组记录已访问的元素。-伪代码：pythondeffind_combinations(nums):nums.sort()result=[]path=[]used=[False]len(nums)defbacktrack():result.append(path.copy())foriinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continuepath.append(nums[i])used[i]=Truebacktrack()path.pop()used[i]=Falsebacktrack()returnresult3.LRU缓存实现-方法：使用双向链表记录访问顺序，哈希表记录键值对。-伪代码：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key):ifkeyinself.cache:node=self.cache[key]self._move_to_front(node)returnnode.valuereturn-1defput(self,key,value):ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_front(node)else:iflen(self.cache)==self.capacity:self._remove_LRU()new_node=Node(key,value)self.cache[key]=new_nodeself._add_to_front(new_node)def_move_to_front(self,node):self._remove_node(node)self._add_to_front(node)def_add_to_front(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_remove_LRU(self):lru=self.tail.prevself._remove_node(lru)delself.cache[lru.key]五、代码实现题答案1.二叉搜索树实现-代码：pythonclassTreeNode:def__init__(self,key):self.key=keyself.left=Noneself.right=NoneclassBST:def__init__(self):self.root=Nonedefinsert(self,key):ifnotself.root:self.root=TreeNode(key)else:self._insert(self.root,key)def_insert(self,node,key):ifkey<node.key:ifnode.left:self._insert(node.left,key)else:node.left=TreeNode(key)else:ifnode.right:self._insert(node.right,key)else:node.right=TreeNode(key)defsearch(self,key):returnself._search(self.root,key)def_search(self,node,key):ifnotnode:returnNoneifkey==node.key:returnnodeelifkey<node.key:returnself._search(node.left,key)else:returnself._search(node.right,key)defdelete(self,key):self.root=self._delete(self.root,key)def_delete(self,node,key):ifnotnode:returnnodeifkey<node.key:node.left=self._delete(node.left,key)elifkey>node.key:node.right=self._delete(node.right,key)else:ifnotnode.left:returnnode.rightelifnotnode.right:returnnode.leftelse:min_larger_node=self._find_min(node.right)node.key=min_larger_node.keynode.right=self._delete(node.right,min_larger_node.key)returnnodedef_find_min(self,node):whilenode.left:node=node.leftreturnnode2.最小堆实现-代码：pythonclassMinHeap:def__init__(self):self.heap=[]definsert(self,val):self.heap.append(val)self._heapify_up(len(self.heap)-1)defextract_min(self):ifnotself.heap:returnNoneiflen(self.heap)==1:returnself.heap.pop()min_val=self.heap[0]self.heap[0]=self.he