2026年计算机科学数据结构试题及答案

2026年计算机科学数据结构试题及答案一、选择题（40分）1.在数据结构中，以下哪种数据结构是非线性的？A.栈B.队列C.树D.数组参考答案：C解析：树是一种非线性数据结构，因为它具有层次关系，元素之间不是简单的一对一或一对多关系。栈、队列和数组都是线性数据结构，元素之间是一对一或一对多的简单关系。2.以下哪种排序算法的平均时间复杂度为O(n²)？A.快速排序B.归并排序C.堆排序D.冒泡排序参考答案：D解析：冒泡排序是一种简单的排序算法，其平均时间复杂度和最坏时间复杂度均为O(n²)。而快速排序的平均时间复杂度为O(nlogn)，最坏情况下为O(n²)；归并排序和堆排序的时间复杂度在所有情况下都是O(nlogn)。3.在二叉搜索树中，以下哪种操作的时间复杂度可能达到O(n)？A.查找最小元素B.插入元素C.删除元素D.查找最大元素参考答案：C解析：在二叉搜索树中，查找最小元素、查找最大元素和插入元素的平均时间复杂度都是O(logn)，但在最坏情况下（例如树退化为链表时）可能达到O(n)。删除操作在最坏情况下也需要O(n)的时间复杂度，因为可能需要查找前驱或后继节点。4.以下哪种数据结构适合实现函数调用栈？A.队列B.栈C.双向链表D.数组参考答案：B解析：栈是一种后进先出（LIFO）的数据结构，非常适合实现函数调用栈，因为后调用的函数应该先执行完毕并返回。队列是先进先出（FIFO）的结构，不适合实现函数调用栈。5.在哈希表中，处理冲突的方法不包括以下哪种？A.开放地址法B.链地址法C.二次探测法D.顺序查找法参考答案：D解析：开放地址法、链地址法和二次探测法都是处理哈希表中冲突的常用方法。顺序查找法是一种基本的查找方法，不是专门用于处理哈希冲突的方法。6.以下哪种图遍历算法可以找到从起点到所有其他顶点的最短路径（假设边权均为1）？A.深度优先搜索B.广度优先搜索C.拓扑排序D.Dijkstra算法参考答案：B解析：广度优先搜索（BFS）可以找到从起点到所有其他顶点的最短路径（当边权均为1时）。深度优先搜索（DFS）不适合寻找最短路径，因为它可能会先探索更远的路径。拓扑排序用于有向无环图的排序，Dijkstra算法用于带权图的最短路径查找。7.在平衡二叉树（AVL树）中，任何节点的左右子树高度差的最大值是多少？A.0B.1C.2D.3参考答案：B解析：在AVL树中，任何节点的左右子树高度差（平衡因子）的最大值是1。这是AVL树保持平衡的关键条件，如果某个节点的平衡因子超过1，就需要进行旋转操作来恢复平衡。8.以下哪种排序算法是稳定的？A.快速排序B.堆排序C.归并排序D.选择排序参考答案：C解析：稳定排序算法是指相等的元素在排序后的相对顺序保持不变。归并排序是一种稳定的排序算法。快速排序和堆排序通常是不稳定的，选择排序也是不稳定的。9.在邻接矩阵表示的图中，判断两个顶点之间是否有边相连的时间复杂度是？A.O(1)B.O(logn)C.O(n)D.O(n²)参考答案：A解析：在邻接矩阵中，判断两个顶点之间是否有边相连只需要直接访问矩阵中对应的元素，因此时间复杂度为O(1)。而在邻接表中，这个操作需要遍历链表，时间复杂度为O(n)。10.以下哪种数据结构适合实现LRU（最近最少使用）缓存？A.队列B.栈C.哈希表和双向链表D.二叉搜索树参考答案：C解析：LRU缓存需要快速查找元素、快速更新元素的使用顺序以及快速淘汰最久未使用的元素。哈希表可以实现O(1)时间复杂度的查找，双向链表可以维护元素的访问顺序，因此哈希表和双向链表的组合非常适合实现LRU缓存。11.在二叉树的先序遍历中，访问节点的顺序是？A.根节点、左子树、右子树B.左子树、根节点、右子树C.左子树、右子树、根节点D.根节点、右子树、左子树参考答案：A解析：二叉树的先序遍历顺序是：先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。12.以下哪种数据结构可以实现双端队列（Deque）的所有操作？A.单向链表B.数组C.循环数组D.栈参考答案：C解析：循环数组可以实现双端队列的所有操作，包括在两端插入和删除元素，且这些操作的时间复杂度都是O(1)。单向链表实现的双端队列在头端删除元素的时间复杂度为O(1)，但在尾端删除元素需要O(n)时间。13.在B树中，以下说法正确的是？A.所有叶子节点都在同一层B.每个节点最多有两个子节点C.适用于内存中的数据存储D.不支持范围查询参考答案：A解析：B树的一个重要特性是所有叶子节点都在同一层，这使得B树保持了平衡。B树的节点可以有多个子节点（不仅仅是两个），因此它不是二叉树。B树主要设计用于磁盘等外部存储设备，而不是内存。B树支持高效的范围查询。14.以下哪种算法用于求解无向图的最小生成树？A.Dijkstra算法B.Prim算法C.Kruskal算法D.Bellman-Ford算法参考答案：B和C解析：Prim算法和Kruskal算法都是用于求解无向图最小生成树的经典算法。Dijkstra算法用于求解单源最短路径问题，Bellman-Ford算法用于求解单源最短路径问题，可以处理负权边。15.在红黑树中，以下哪个性质是正确的？A.每个节点要么是红色，要么是黑色B.根节点必须是红色C.所有叶子节点都是黑色D.红色节点的子节点必须是黑色参考答案：A和D解析：红黑树有以下性质：1）每个节点要么是红色，要么是黑色；2）根节点是黑色；3）所有叶子节点都是黑色（NIL节点）；4）如果一个节点是红色，则它的两个子节点都是黑色；5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。因此，选项A和D是正确的，选项B和C是错误的。16.以下哪种排序算法是原地排序算法？A.归并排序B.快速排序C.基数排序D.计数排序参考答案：B解析：原地排序算法是指不需要额外存储空间的排序算法，或者只需要常数级别的额外空间。快速排序是一种原地排序算法，而归并排序、基数排序和计数排序都需要额外的存储空间。17.在哈希表中，负载因子（loadfactor）是指？A.表中元素数量与表大小的比值B.表中冲突元素的数量C.表中已删除元素的数量D.表中已插入元素的数量参考答案：A解析：负载因子是哈希表的一个重要参数，定义为表中元素数量与表大小的比值。负载因子影响哈希表的性能，当负载因子过大时，哈希表的查找效率会下降，需要扩容和重新哈希。18.以下哪种数据结构适合实现优先队列？A.队列B.栈C.堆D.链表参考答案：C解析：堆是一种非常适合实现优先队列的数据结构，因为它可以在O(logn)时间内完成插入和删除最大（或最小）元素的操作。队列和栈不能满足优先队列的需求，链表实现优先队列的效率较低。19.在图的广度优先搜索中，使用的数据结构是？A.栈B.队列C.优先队列D.哈希表参考答案：B解析：广度优先搜索（BFS）使用队列来存储待访问的节点，确保先访问距离起点较近的节点。深度优先搜索（DFS）使用栈来存储待访问的节点。20.以下哪种算法用于字符串匹配？A.KMP算法B.Dijkstra算法C.Prim算法D.快速排序参考答案：A解析：KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，可以在O(n+m)时间内完成模式串在文本串中的查找。Dijkstra算法用于单源最短路径问题，Prim算法用于最小生成树，快速排序是一种排序算法。二、填空题（20分）1.在数据结构中，栈的特点是______，队列的特点是______。参考答案：后进先出（LIFO），先进先出（FIFO）解析：栈是一种后进先出（LastInFirstOut，LIFO）的数据结构，最后入栈的元素最先出栈。队列是一种先进先出（FirstInFirstOut，FIFO）的数据结构，最先入队的元素最先出队。2.二叉树的遍历方式有______、______和______三种基本方式。参考答案：先序遍历，中序遍历，后序遍历解析：二叉树的遍历是指按照一定顺序访问二叉树中的所有节点。三种基本的遍历方式是：先序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。3.在哈希表中，处理冲突的方法主要有______和______两种。参考答案：开放地址法，链地址法解析：哈希冲突是指不同的关键字通过哈希函数计算得到相同的哈希地址。处理冲突的主要方法有两种：开放地址法（寻找另一个空的哈希地址）和链地址法（将所有哈希到同一地址的关键字存储在同一个链表中）。4.排序算法中，快速排序的平均时间复杂度是______，最坏时间复杂度是______。参考答案：O(nlogn)，O(n²)解析：快速排序的平均时间复杂度是O(nlogn)，但在最坏情况下（例如数组已经有序或逆序时）时间复杂度为O(n²)。通过随机选择枢轴或三数取中等方法可以降低最坏情况发生的概率。5.图的存储方式主要有______和______两种。参考答案：邻接矩阵，邻接表解析：图的存储方式主要有两种：邻接矩阵和邻接表。邻接矩阵使用二维数组表示图，适合稠密图；邻接表使用链表数组表示图，适合稀疏图。6.在平衡二叉树（AVL树）中，任何节点的左右子树高度差的最大值是______。参考答案：1解析：在AVL树中，任何节点的左右子树高度差（平衡因子）的最大值是1。如果某个节点的平衡因子超过1，就需要进行旋转操作来恢复平衡。7.堆排序的时间复杂度是______，空间复杂度是______。参考答案：O(nlogn)，O(1)解析：堆排序的时间复杂度是O(nlogn)，因为建堆需要O(n)时间，每次调整堆需要O(logn)时间，共进行n次调整。堆排序的空间复杂度是O(1)，因为它是一种原地排序算法。8.在二叉搜索树中，查找操作的平均时间复杂度是______，最坏时间复杂度是______。参考答案：O(logn)，O(n)解析：在平衡的二叉搜索树中，查找操作的平均时间复杂度是O(logn)。但在最坏情况下（例如树退化为链表时），查找操作的时间复杂度为O(n)。9.以下算法中，______算法用于求解单源最短路径问题，______算法用于求解所有顶点对之间的最短路径问题。参考答案：Dijkstra，Floyd-Warshall解析：Dijkstra算法用于求解单源最短路径问题，假设图中没有负权边。Floyd-Warshall算法用于求解所有顶点对之间的最短路径问题，可以处理负权边但不能有负权回路。10.以下数据结构中，______适合实现LRU缓存，______适合实现并查集。参考答案：哈希表和双向链表，数组或森林解析：LRU缓存需要快速查找元素、快速更新元素的使用顺序以及快速淘汰最久未使用的元素，因此哈希表和双向链表的组合非常适合实现LRU缓存。并查集是一种用于处理不相交集合的数据结构，通常使用数组或森林（树的集合）来实现。三、判断题（10分）1.在二叉树的先序遍历中，根节点最先被访问。参考答案：正确解析：二叉树的先序遍历顺序是：先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。因此，根节点最先被访问。2.快速排序是一种稳定的排序算法。参考答案：错误解析：快速排序通常是不稳定的排序算法，因为在分区过程中，相等元素的相对顺序可能会改变。例如，对于数组[3,2,2,1]，如果选择第一个3作为枢轴，分区后两个2的相对顺序可能会改变。3.在哈希表中，负载因子越大，查找效率越高。参考答案：错误解析：负载因子是哈希表中元素数量与表大小的比值。负载因子越大，意味着哈希冲突的概率越高，查找效率越低。因此，通常当负载因子超过某个阈值（如0.7）时，需要扩容哈希表以降低负载因子。4.在邻接矩阵表示的图中，判断两个顶点之间是否有边相连的时间复杂度是O(1)。参考答案：正确解析：在邻接矩阵中，判断两个顶点之间是否有边相连只需要直接访问矩阵中对应的元素，因此时间复杂度为O(1)。5.在B树中，每个节点最多有两个子节点。参考答案：错误解析：B树的节点可以有多个子节点，而不仅仅是两个。B树是一种多路搜索树，每个节点可以有多个关键字和多个子节点。6.在红黑树中，根节点必须是红色。参考答案：错误解析：在红黑树中，根节点必须是黑色。这是红黑树的一个基本性质，确保树的平衡性。7.在图的深度优先搜索中，使用的数据结构是队列。参考答案：错误解析：在图的深度优先搜索（DFS）中，使用的数据结构是栈（或递归调用栈）。广度优先搜索（BFS）使用队列作为数据结构。8.归并排序是一种原地排序算法。参考答案：错误解析：归并排序不是原地排序算法，因为它需要额外的O(n)空间来合并两个已排序的子数组。而快速排序、堆排序等是原地排序算法。9.在AVL树中，插入或删除节点后，可能需要进行多次旋转来恢复平衡。参考答案：正确解析：在AVL树中，插入或删除节点后，可能需要从插入或删除点向上回溯，进行多次旋转来恢复平衡。这是因为一次旋转可能无法恢复所有受影响节点的平衡。10.在二叉搜索树中，中序遍历可以得到有序的序列。参考答案：正确解析：在二叉搜索树中，中序遍历（左-根-右）可以得到有序的序列。这是因为二叉搜索树的性质是：左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。四、简答题（30分）1.请简述栈和队列的区别，并分别给出一个应用场景。参考答案：栈和队列的主要区别在于它们的操作顺序和特性：栈（Stack）：-特性：后进先出（LastInFirstOut，LIFO）-操作：主要在栈顶进行插入（入栈）和删除（出栈）操作-访问：只能访问栈顶元素队列（Queue）：-特性：先进先出（FirstInFirstOut，FIFO）-操作：在队尾插入元素（入队），在队头删除元素（出队）-访问：可以访问队头和队尾元素应用场景：-栈的应用：函数调用栈、表达式求值、括号匹配、浏览器的前进后退功能-队列的应用：任务调度、消息队列、广度优先搜索、打印任务队列2.请解释什么是哈希冲突，以及常见的处理哈希冲突的方法。参考答案：哈希冲突（HashCollision）是指不同的关键字通过哈希函数计算得到相同的哈希地址的现象。由于哈希函数通常将较大的关键字空间映射到较小的地址空间，冲突是不可避免的。常见的处理哈希冲突的方法有：1.开放地址法（OpenAddressing）：-当发生冲突时，按照一定的规则寻找下一个可用的位置-常用的探测方法有：a.线性探测：顺序查找下一个位置b.二次探测：按照二次函数的步长查找c.双重哈希：使用第二个哈希函数计算步长2.链地址法（SeparateChaining）：-将哈希到同一地址的所有关键字存储在同一个链表中-查找时需要遍历链表-适合冲突较多的情况3.再哈希法（Rehashing）：-当冲突发生时，使用另一个哈希函数重新计算地址4.建立公共溢出区：-将所有冲突的关键字存储在单独的溢出区选择哪种处理方法取决于具体的应用场景、哈希函数的设计以及对性能的要求。3.请解释什么是平衡二叉树（AVL树），以及它如何保持平衡。参考答案：平衡二叉树（BalancedBinaryTree），特别是AVL树（以发明者Adelson-Velsky和Landis命名），是一种特殊的二叉搜索树，它通过保持树的平衡来确保各种操作的时间复杂度为O(logn)。AVL树的主要特点：1.它首先是一棵二叉搜索树，满足二叉搜索树的性质2.对于树中的任意节点，其左右子树的高度差（平衡因子）的绝对值不超过13.所有叶子节点到根节点的路径长度最多相差1AVL树通过以下机制保持平衡：1.平衡因子：每个节点存储一个平衡因子，其左子树高度减去右子树高度。平衡因子只能是-1、0或1。2.旋转操作：当插入或删除节点导致某个节点的平衡因子超出[-1,1]范围时，需要进行旋转操作来恢复平衡。主要有四种旋转情况：-左旋（LeftRotation）：当右子树过高时-右旋（RightRotation）：当左子树过高时-左-右旋（Left-RightRotation）：左子树的右子树过高时-右-左旋（Right-LeftRotation）：右子树的左子树过高时3.插入和删除后的调整：在插入或删除节点后，从该节点向上回溯，检查每个祖先节点的平衡因子，必要时进行旋转，直到恢复平衡或到达根节点。通过这些机制，AVL树确保了树的高度始终保持在O(logn)级别，从而保证了查找、插入和删除操作的时间复杂度为O(logn)。4.请解释什么是图的遍历，以及深度优先搜索和广度优先搜索的区别。参考答案：图的遍历是指按照一定的顺序访问图中的所有顶点，每个顶点恰好被访问一次。图的遍历是许多图算法的基础，如寻找路径、连通性检测、拓扑排序等。深度优先搜索（Depth-FirstSearch,DFS）：-基本思想：从一个顶点开始，尽可能深地探索图的分支，直到不能再继续前进时回溯，然后选择另一个未访问的分支继续探索。-实现方式：通常使用递归或栈来实现。-访问顺序：类似于树的先序遍历。-时间复杂度：O(V+E)，其中V是顶点数，E是边数。-空间复杂度：O(V)，用于存储访问标记和递归栈。-应用场景：检测环、寻找路径、连通分量检测、拓扑排序等。广度优先搜索（Breadth-FirstSearch,BFS）：-基本思想：从一个顶点开始，先访问所有直接相邻的顶点，然后依次访问这些相邻顶点的未访问邻居，逐层向外扩展。-实现方式：通常使用队列来实现。-访问顺序：按照距离起点的远近逐层访问。-时间复杂度：O(V+E)，其中V是顶点数，E是边数。-空间复杂度：O(V)，用于存储访问标记和队列。-应用场景：寻找最短路径（无权图）、连通分量检测、层次遍历等。深度优先搜索和广度优先搜索的主要区别：1.探索顺序：DFS深入探索一条路径后再回溯，BFS逐层向外扩展。2.数据结构：DFS使用栈（或递归），BFS使用队列。3.应用场景：DFS更适合寻找路径和检测环，BFS更适合寻找最短路径（无权图）。4.空间复杂度：在稀疏图中，DFS的空间复杂度通常低于BFS。5.请解释什么是堆排序，并描述堆排序的基本步骤。参考答案：堆排序（HeapSort）是一种基于堆数据结构的排序算法，它利用了堆的特性（父节点的值总是大于或小于其子节点的值）来进行排序。堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，是一种高效的原地排序算法。堆排序的基本步骤如下：1.构建最大堆（或最小堆）：-将待排序数组看作一个完全二叉树-从最后一个非叶子节点开始，自底向上、自右向左调整每个子树，使其满足堆的性质-最后得到一个最大堆（或最小堆）2.排序过程：-将堆顶元素（最大值或最小值）与堆的最后一个元素交换-将堆的大小减1（相当于移除了堆顶元素）-对新的堆顶元素进行向下调整，使其重新满足堆的性质-重复上述步骤，直到堆的大小为13.完成排序：-当堆的大小为1时，排序完成-如果构建的是最大堆，则数组按升序排列；如果构建的是最小堆，则数组按降序排列堆排序的关键在于堆的调整操作：-向上调整：当插入一个元素时，如果该元素比其父节点大（在最大堆中），则交换它们，直到满足堆的性质。-向下调整：当删除堆顶元素或调整堆时，将堆顶元素与较小的子节点交换，直到满足堆的性质。堆排序的优点是不需要额外的存储空间，且在最坏情况下也能保持O(nlogn)的时间复杂度。缺点是不稳定排序，且在实际应用中通常比快速排序慢。五、算法设计题（30分）1.设计一个算法，判断一个二叉树是否是二叉搜索树（BST）。参考答案：要判断一个二叉树是否是二叉搜索树（BST），我们需要验证它是否满足BST的定义：对于树中的任意节点，其左子树的所有节点值都小于该节点值，右子树的所有节点值都大于该节点值。以下是判断二叉树是否是BST的算法实现（使用Python）：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_valid_bst(root):"""判断一个二叉树是否是二叉搜索树（BST）参数:root:二叉树的根节点返回:bool:如果是BST返回True，否则返回False"""defhelper(node,lower=float('-inf'),upper=float('inf')):"""辅助函数，递归检查每个节点是否满足BST的条件参数:node:当前节点lower:当前节点允许的最小值upper:当前节点允许的最大值返回:bool:如果子树满足BST条件返回True，否则返回False"""空树是BSTifnotnode:returnTrue当前节点的值必须在(lower,upper)范围内ifnode.val<=lowerornode.val>=upper:returnFalse递归检查左子树和右子树左子树的值必须小于当前节点值，所以上界更新为当前节点值右子树的值必须大于当前节点值，所以下界更新为当前节点值returnhelper(node.left,lower,node.val)andhelper(node.right,node.val,upper)returnhelper(root)```算法思路：1.使用递归方法遍历二叉树2.对于每个节点，维护一个允许的值范围(lower,upper)3.初始时，根节点的值范围是(-∞,+∞)4.对于左子节点，上界更新为父节点的值，下界保持不变5.对于右子节点，下界更新为父节点的值，上界保持不变6.如果任何节点的值不在允许的范围内，则不是BST7.如果所有节点都满足条件，则是BST时间复杂度：O(n)，其中n是二叉树中的节点数，因为每个节点只被访问一次。空间复杂度：O(h)，其中h是二叉树的高度，这是由于递归调用栈的空间。在最坏情况下（树退化为链表），空间复杂度为O(n)。另一种方法是进行中序遍历，检查遍历结果是否是严格递增的序列。如果中序遍历的结果是递增的，则是BST，否则不是。这种方法的时间复杂度也是O(n)，空间复杂度也是O(h)。2.设计一个算法，实现LRU（最近最少使用）缓存机制，要求get和put操作的时间复杂度均为O(1)。参考答案：LRU（LeastRecentlyUsed）缓存是一种缓存淘汰策略，当缓存满时，淘汰最近最少使用的数据。要实现LRU缓存，我们需要支持以下操作：-get(key):获取数据项的值，如果存在则返回值，并更新该项为最近使用；如果不存在则返回-1-put(key,value):向缓存中添加或更新数据项，如果添加后缓存满，则淘汰最近最少使用的数据项要实现O(1)时间复杂度的get和put操作，我们可以使用哈希表和双向链表的组合：-哈希表：用于快速查找数据项，key为数据项的键，value为指向双向链表中对应节点的指针-双向链表：维护数据项的使用顺序，最近使用的项放在链表头部，最久未使用的项放在链表尾部以下是LRU缓存的实现（使用Python）：```pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity):"""初始化LRU缓存参数:capacity:缓存的容量"""self.capacity=capacityself.cache={}哈希表，key为数据项的键，value为双向链表节点self.head=DLinkedNode()双向链表的头节点（最近使用）self.tail=DLinkedNode()双向链表的尾节点（最久未使用）self.head.next=self.tail初始化链表self.tail.prev=self.headdef_add_node(self,node):"""将节点添加到链表头部（最近使用）参数:node:要添加的节点"""node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):"""从链表中移除节点参数:node:要移除的节点"""prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):"""将节点移动到链表头部（最近使用）参数:node:要移动的节点"""self._remove_node(node)self._add_node(node)def_pop_tail(self):"""移除链表尾部节点（最久未使用）并返回该节点返回:被移除的节点"""node=self.tail.prevself._remove_node(node)returnnodedefget(self,key):"""获取数据项的值参数:key:数据项的键返回:数据项的值，如果不存在则返回-1"""node=self.cache.get(key,None)ifnotnode:return-1将访问的节点移到链表头部（最近使用）self._move_to_head(node)returnnode.valuedefput(self,key,value):"""向缓存中添加或更新数据项参数:key:数据项的键value:数据项的值"""node=self.cache.get(key,None)ifnode:如果数据项已存在，更新值并将节点移到链表头部node.value=valueself._move_to_head(node)else:如果数据项不存在，创建新节点new_node=DLinkedNode(key,value)self.cache[key]=new_nodeself._add_node(new_node)如果缓存已满，移除最久未使用的节点iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]```算法思路：1.使用哈希表实现O(1)时间复杂度的查找2.使用双向链表维护数据项的使用顺序3.get操作：-如果数据项存在，将其移到链表头部（表示最近使用）并返回值-如果数据项不存在，返回-14.put操作：-如果数据项已存在，更新值并将其移到链表头部-如果数据项不存在，创建新节点并添加到链表头部-如果缓存已满，移除链表尾部节点（最久未使用）并从哈希表中删除对应的键值对时间复杂度：-get操作：O(1)，哈希表查找和链表操作都是O(1)-put操作：O(1)，哈希表插入/更新和链表操作都是O(1)空间复杂度：O(capacity)，其中capacity是缓存的容量，用于存储最多capacity个数据项。六、综合应用题（50分）1.设计一个算法，实现一个支持以下操作的数据结构：-insert(word):向数据结构中插入一个单词-search(word):检查单词是否在数据结构中-startsWith(prefix):检查是否存在以prefix开头的单词要求所有操作的时间复杂度均为O(m)，其中m是单词或前缀的长度。参考答案：这个问题要求实现一个前缀树（Trie树，也称为字典树）数据结构。前缀树是一种树形数据结构，专门用于处理字符串集合，特别适合实现前缀匹配功能。以下是前缀树的实现（使用Python）：```pythonclassTrieNode:def__init__(self):self.children={}子节点字典，key是字符，value是TrieNodeself.is_end=False标记是否是单词的结尾classTrie:def__init__(self):"""初始化前缀树"""self.root=TrieNode()definsert(self,word):"""向前缀树中插入一个单词参数:word:要插入的单词"""node=self.rootforcharinword:如果字符不在当前节点的子节点中，创建新节点ifcharnotinnode.children:node.children[char]=TrieNode()移动到子节点node=node.children[char]标记单词结尾node.is_end=Truedefsearch(self,word):"""检查单词是否在前缀树中参数:word:要查找的单词返回:bool:如果单词存在返回True，否则返回False"""node=self.rootforcharinword:如果字符不在当前节点的子节点中，单词不存在ifcharnotinnode.children:returnFalse移动到子节点node=node.children[char]检查是否是完整单词（不是前缀）returnnode.is_enddefstartsWith(self,prefix):"""检查是否存在以prefix开头的单词参数:prefix:要查找的前缀返回:bool:如果存在以prefix开头的单词返回True，否则返回False"""node=self.rootforcharinprefix:如果字符不在当前节点的子节点中，不存在以prefix开头的单词ifcharnotinnode.children:returnFalse移动到子节点node=node.children[char]只要能遍历完prefix，就存在以prefix开头的单词returnTrue```算法思路：1.前缀树的每个节点包含一个子节点字典和一个is_end标记2.插入操作（insert）：-从根节点开始，逐个字符检查单词-如果字符不在当前节点的子节点中，创建新节点-移动到对应子节点，继续处理下一个字符-处理完所有字符后，标记最后一个节点为单词结尾3.搜索操作（search）：-从根节点开始，逐个字符检查单词-如果字符不在当前节点的子节点中，单词不存在-移动到对应子节点，继续处理下一个字符-处理完所有字符后，检查最后一个节点是否被标记为单词结尾4.前缀匹配操作（startsWith）：-从根节点开始，逐个字符检查前缀-如果字符不在当前节点的子节点中，不存在以该前缀开头的单词-移动到对应子节点，继续处理下一个字符-只要能遍历完前缀，就存在以该前缀开头的单词时间复杂度：-insert:O(m)，其中m是单词的长度，需要遍历单词的所有字符-search:O(m)，其中m是单词的长度，需要遍历单词的所有字符-startsWith:O(m)，其中m是前缀的长度，需要遍历前缀的所有字符空间复杂度：O(nm)，其中n是单词的数量，m是单词的平均长度。在最坏情况下，前缀树需要存储所有单词的所有字符。2.设计一个算法，实现一个支持以下操作的数据结构：-addNum(num):添加一个整数到数据结构中-findMedian():返回所有已添加数字的中位数要求addNum的时间复杂度为O(logn)，findMedian的时间复杂度为O(1)，其中n是已添加数字的数量。参考答案：要实现一个支持高效添加数字和快速查找中位数的数据结构，我们可以使用两个堆：-最大堆：存储较小的一半数字，堆顶是这半部分数字的最大值-最小堆：存储较大的一半数字，堆顶是这半部分数字的最小值通过维护这两个