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

2026年数据结构与算法练习题一、选择题（每题2分，共20分）说明：下列每小题只有一个正确答案。1.在下列数据结构中，最适合用来表示稀疏矩阵的是（）。A.顺序表B.链表C.矩阵链D.二维数组2.下列关于二叉树的说法中，错误的是（）。A.完全二叉树中，若一个节点没有左子节点，则它一定没有右子节点B.满二叉树中，所有内部节点的度均为2C.二叉树的遍历方式包括前序遍历、中序遍历和后序遍历D.堆是一种特殊的二叉树，可以是任意形状3.在快速排序算法中，当输入数据已经接近有序时，其时间复杂度会退化到（）。A.O(n)B.O(nlogn)C.O(n²)D.O(logn)4.下列数据结构中，最适合用于实现栈的是（）。A.链表B.队列C.哈希表D.堆5.在图的遍历算法中，深度优先搜索（DFS）的时间复杂度与广度优先搜索（BFS）的时间复杂度相比（）。A.DFS更慢B.BFS更慢C.两者相同D.取决于具体实现6.哈希表解决冲突的两种主要方法是（）。A.开放定址法和链地址法B.二叉查找树法和堆法C.哈希函数法和中缀法D.插入法和删除法7.在下列算法中，属于分治法的是（）。A.冒泡排序B.快速排序C.选择排序D.插入排序8.在B树中，每个节点的关键字数量与其子节点的数量之间存在什么关系？（）A.关键字数量是子节点数量的2倍B.关键字数量是子节点数量的1倍C.关键字数量比子节点数量多1D.关键字数量比子节点数量少19.在下列数据结构中，最适合实现LRU（最近最少使用）缓存淘汰算法的是（）。A.哈希表B.链表C.堆D.双向链表10.在归并排序中，递归的终止条件是（）。A.子数组长度为0B.子数组长度为1C.子数组长度为nD.子数组无法再分二、填空题（每空1分，共20分）说明：请将答案填写在横线上。1.在线性表中，插入一个元素的最坏时间复杂度为______。2.二叉树的深度为h，则其最多有多少个节点？______。3.快速排序的平均时间复杂度为______。4.栈是一种______结构，遵循______原则。5.在图的邻接矩阵表示中，如果两个顶点之间没有边，通常用______表示。6.哈希表的冲突解决方法中，链地址法的主要缺点是______。7.B树的平衡性体现在每个节点的子节点数量相等（除叶节点外），其关键字数量范围为______。8.在堆排序中，堆的调整过程称为______。9.LRU缓存淘汰算法的核心思想是______。10.归并排序的空间复杂度为______。三、简答题（每题5分，共25分）说明：请简要回答下列问题。1.简述线性表和链表的优缺点。2.解释什么是二叉树的完全二叉树，并举例说明。3.描述快速排序的基本思想和实现步骤。4.解释哈希表的工作原理，并说明常见的冲突解决方法。5.简述图的三种基本遍历方式（DFS、BFS、Dijkstra算法）及其适用场景。四、编程题（每题10分，共30分）说明：请用C++或Java实现下列功能。1.实现一个简单的栈，支持push、pop和peek操作。要求：使用数组实现栈，并处理栈满和栈空的情况。2.编写一个函数，判断二叉树是否为平衡二叉树。要求：平衡二叉树定义为任意节点的左右子树高度差不超过1。3.实现一个哈希表，支持插入和查找操作，使用链地址法解决冲突。要求：哈希函数为`hash(key)=key%10`，链表节点包含`key`和`next`字段。五、算法设计题（15分）说明：请设计一个算法解决下列问题，并分析其时间复杂度。问题描述：给定一个包含重复元素的数组，请设计一个算法找出数组中所有重复至少三次的元素，并输出它们的顺序。例如，输入`[1,2,3,1,2,1,4,5,3,3]`，输出`[1,3]`。答案与解析一、选择题答案1.B2.D3.C4.A5.C6.A7.B8.C9.D10.B解析：1.稀疏矩阵适合用链表表示，因为稀疏矩阵中大部分元素为0，链表可以节省空间。2.D错误，堆是特殊的完全二叉树，要求除了叶节点外，所有节点的度数均为2。3.快速排序在近乎有序时，会退化到O(n²)。4.栈是后进先出结构，最适合用链表实现。5.DFS和BFS的时间复杂度均为O(V+E)，但实现方式不同。6.开放定址法和链地址法是常见冲突解决方法。7.快速排序是典型的分治算法。8.B树中，每个节点的关键字数量比子节点数量多1。9.LRU缓存适合用双向链表实现。10.归并排序递归终止条件是子数组长度为1。二、填空题答案1.O(n)2.2^h-13.O(nlogn)4.后进先出；后进先出5.∞（表示无穷大）6.空间复杂度高7.[ceil(m/2),floor((m-1)/2)]8.堆化9.替换最久未使用的元素10.O(nlogn)解析：1.插入元素最坏情况是每次插入都需要遍历整个线性表。2.二叉树深度为h时，最多有2^h-1个节点。3.快速排序平均时间复杂度为O(nlogn)。4.栈是后进先出结构，遵循LIFO原则。5.邻接矩阵用无穷大表示无直接边。6.链地址法冲突解决会占用更多空间。7.B树节点关键字范围取决于节点度数。8.堆调整是堆化过程。9.LRU核心是替换最久未使用元素。10.归并排序需要额外空间。三、简答题答案1.线性表与链表优缺点：-线性表：顺序存储，随机访问快（O(1)），但插入删除慢（O(n)）；链表插入删除快（O(1)），但随机访问慢（O(n)）。2.完全二叉树：除最后一层外，其他层节点数满，最后一层节点从左到右连续。例如：[1,2,3,4,5,6]。3.快速排序思想：分治思想，选择基准元素，将数组分为小于和大于基准的两部分，递归排序。4.哈希表原理与冲突解决：通过哈希函数将键映射到数组索引，冲突用开放定址法或链地址法解决。5.图遍历方式：-DFS：深度优先，适合求连通分量；-BFS：广度优先，适合求最短路径；-Dijkstra：贪心算法，求单源最短路径。四、编程题答案1.栈实现（C++）：cppinclude<vector>include<stdexcept>classStack{private:std::vector<int>data;intcapacity;public:Stack(intsize):capacity(size),data(size){}voidpush(intx){if(size()==capacity)throwstd::overflow_error("Stackfull");data.push_back(x);}intpop(){if(empty())throwstd::underflow_error("Stackempty");intx=data.back();data.pop_back();returnx;}intpeek()const{if(empty())throwstd::underflow_error("Stackempty");returndata.back();}boolempty()const{returndata.empty();}intsize()const{returndata.size();}};2.判断平衡二叉树（Java）：javaclassTreeNode{intval;TreeNodeleft,right;TreeNode(intx){val=x;}}publicclassSolution{publicbooleanisBalanced(TreeNoderoot){returnmaxDepth(root)!=-1;}privateintmaxDepth(TreeNodenode){if(node==null)return0;intleft=maxDepth(node.left);if(left==-1)return-1;intright=maxDepth(node.right);if(right==-1||Math.abs(left-right)>1)return-1;returnMath.max(left,right)+1;}}3.哈希表实现（C++）：cppinclude<vector>include<list>classHashTable{private:std::vector<std::list<int>>table;intcapacity;public:HashTable(intsize):capacity(size),table(size){}voidinsert(intkey){intidx=key%capacity;table[idx].push_back(key);}boolfind(intkey){intidx=key%capacity;for(intk:table[idx]){if(k==key)returntrue;}returnfalse;}};五、算法设计题答案算法思路：1.使用哈希表记录每个元素的出现次数；2.遍历哈希表，找出出现至少三次的元素，按顺序输出。代码（C++）：cppinclude<vector>include<unordered_map>std::vector<int>findDuplicates(std::vector<int>&nums){std::unordered_ma