2026年数据结构算法学习笔记及代码实践解析

2026年数据结构算法学习笔记及代码实践解析一、选择题（每题2分，共20题）1题：在线性表的三种存储结构（顺序存储、链式存储、索引存储）中，最适合进行插入和删除操作的是？A.顺序存储B.链式存储C.索引存储D.哈希存储2题：下列数据结构中，哪一个不是非线性结构？A.树B.图C.队列D.双向链表3题：在快速排序算法中，选择枢轴元素的不同方法可能会影响算法的效率，以下哪种方法通常会导致最坏情况下的性能？A.随机选择枢轴B.选择第一个元素作为枢轴C.选择最后一个元素作为枢轴D.三数取中法4题：在二叉搜索树中，删除一个节点后，为了保持树的性质，可能需要进行哪些操作？A.旋转B.重新平衡C.重新排序D.以上都是5题：下列哪种数据结构适合实现LRU（最近最少使用）缓存算法？A.哈希表B.链表C.二叉树D.堆6题：在图的遍历中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别是什么？A.DFS使用栈，BFS使用队列B.DFS适合稀疏图，BFS适合稠密图C.DFS能找到最短路径，BFS不能D.DFS适用于无权图，BFS适用于有权图7题：下列哪种算法的时间复杂度为O(nlogn)？A.冒泡排序B.插入排序C.快速排序D.选择排序8题：在堆排序算法中，堆的性质是什么？A.最大堆：父节点>=子节点；最小堆：父节点<=子节点B.最大堆：父节点<=子节点；最小堆：父节点>=子节点C.所有节点值相等D.没有性质9题：在平衡二叉树中，AVL树和红黑树的主要区别是什么？A.AVL树更严格平衡，红黑树更灵活B.AVL树适用于静态数据，红黑树适用于动态数据C.AVL树节点数更少，红黑树节点数更多D.AVL树插入时间更快，红黑树删除时间更快10题：在哈希表中，解决冲突的两种主要方法是什么？A.开放寻址法和链表法B.二分查找法和线性探测法C.堆排序法和快速排序法D.DFS和BFS二、填空题（每空1分，共10空）1.在链表结构中，插入一个节点需要O(1)时间，前提是已经找到了插入位置。2.二叉树的深度是指从根节点到叶节点的最长路径上的边数。3.在快速排序中，枢轴的选择会影响算法的平衡性，选择枢轴的常用方法包括随机选择、三数取中法等。4.图的邻接矩阵表示法适用于稠密图，但空间复杂度较高。5.堆排序是一种基于堆结构的排序算法，堆分为最大堆和最小堆两种。6.在平衡二叉树中，AVL树和红黑树都是自平衡二叉搜索树，用于保持树的平衡。7.哈希表通过哈希函数将键映射到数组索引，解决冲突的常用方法包括开放寻址法和链表法。8.在B树中，每个节点的孩子数量与该节点的键数量有关，B树的性质保证了树的平衡性。9.在图的遍历中，深度优先搜索（DFS）使用栈实现，广度优先搜索（BFS）使用队列实现。10.在动态规划中，通过将问题分解为子问题并存储子问题的解，避免重复计算，提高效率。三、简答题（每题5分，共5题）1题：简述顺序存储和链式存储的优缺点。2题：解释二叉搜索树的性质，并说明如何插入一个节点。3题：描述快速排序算法的基本思想，并说明其时间复杂度。4题：解释图的三种存储结构（邻接矩阵、邻接表、邻接多重表）的优缺点。5题：说明哈希表的工作原理，并解释如何解决哈希冲突。四、代码题（每题15分，共2题）1题：实现一个单链表，包含插入、删除和查找操作。要求：-插入操作在链表头部插入新节点。-删除操作删除指定值的节点。-查找操作返回指定值的节点，如果不存在则返回None。pythonclassListNode:def__init__(self,value=0,next=None):self.value=valueself.next=nextclassLinkedList:def__init__(self):self.head=Nonedefinsert(self,value):实现代码passdefdelete(self,value):实现代码passdefsearch(self,value):实现代码pass测试代码ll=LinkedList()ll.insert(1)ll.insert(2)print(ll.search(1))#输出1ll.delete(1)print(ll.search(1))#输出None2题：实现一个哈希表，使用链表法解决冲突。要求：-哈希表大小为10。-使用简单的哈希函数：`hash(key)=key%10`。-插入和查找操作。pythonclassHashTable:def__init__(self,size=10):self.size=sizeself.table=[[]for_inrange(size)]defhash(self,key):实现代码passdefinsert(self,key):实现代码passdefsearch(self,key):实现代码pass测试代码ht=HashTable()ht.insert(15)ht.insert(25)print(ht.search(15))#输出15print(ht.search(20))#输出None答案及解析一、选择题答案1.B-链式存储通过指针直接修改相邻节点的链接，插入和删除操作只需修改头尾节点的指针，时间复杂度为O(1)。顺序存储需要移动大量元素，时间复杂度为O(n)。2.C-线性结构：队列、栈、线性链表。非线性结构：树、图、多维数组。3.B-选择第一个或最后一个元素作为枢轴，在已排序或逆序数组中会导致最坏情况O(n^2)时间复杂度。随机选择或三数取中法可以改善性能。4.D-删除节点后可能需要旋转或重新平衡，以保持二叉搜索树的性质。5.D-堆可以维护元素的优先级，结合哈希表可以实现LRU缓存。6.A-DFS使用栈，BFS使用队列。这是两种算法的基本实现方式。7.C-快速排序、归并排序的时间复杂度为O(nlogn)。8.A-最大堆：父节点值>=子节点值；最小堆：父节点值<=子节点值。9.A-AVL树更严格平衡（平衡因子不超过1），红黑树更灵活（平衡因子不超过2）。10.A-开放寻址法（线性探测、二次探测）和链表法（每个槽位存储链表）。二、填空题答案1.链表2.二叉树3.枢轴选择4.邻接矩阵5.堆排序6.自平衡二叉搜索树7.哈希函数8.B树9.栈和队列10.动态规划三、简答题答案1题：-顺序存储：优点是连续内存空间，访问速度快（O(1)）。缺点是插入删除慢（O(n)），空间浪费可能。-链式存储：优点是插入删除快（O(1)），空间灵活。缺点是随机访问慢（O(n)），需要额外存储指针。2题：-二叉搜索树性质：左子树所有节点<根节点<右子树所有节点。插入节点时，从根节点开始比较，递归找到合适位置插入。3题：-快速排序思想：选择枢轴，分区操作，递归对左右子区间排序。平均时间复杂度O(nlogn)，最坏O(n^2)。4题：-邻接矩阵：优点是表示简单，方便判断边是否存在。缺点是空间复杂度高（O(n^2)），稀疏图浪费空间。-邻接表：优点是空间效率高（O(n+m)），适合稀疏图。缺点是查找边慢（O(n)）。-邻接多重表：适用于无向图，每个边存储两次，方便遍历。5题：-哈希表原理：通过哈希函数将键映射到数组索引。冲突解决方法：开放寻址（线性探测、二次探测）或链表法。四、代码题答案1题：pythonclassListNode:def__init__(self,value=0,next=None):self.value=valueself.next=nextclassLinkedList:def__init__(self):self.head=Nonedefinsert(self,value):new_node=ListNode(value)new_node.next=self.headself.head=new_nodedefdelete(self,value):current=self.headprev=Nonewhilecurrent:ifcurrent.value==value:ifprev:prev.next=current.nextelse:self.head=current.nextreturnprev=currentcurrent=current.nextdefsearch(self,value):current=self.headwhilecurrent:ifcurrent.value==value:returncurrent.valuecurrent=current.nextreturnNone测试代码ll=LinkedList()ll.insert(1)ll.insert(2)print(ll.search(1))#输出1ll.delete(1)print(ll.search(1))#输出None2题：pythonclassHashTable:def__init__(self,size=10):self.size=sizeself.table=[[]for_inrange(size)]defhash(self,key):returnkey%self.sizedefinsert(self,key):index=self.hash(key)self.table[index].append(key)defsearch(self,key):