考研算法试题及答案

考研算法试题及答案一、选择题（总分40分）1.下列数据结构中，非顺序存储的是（）A.顺序表B.哈希表C.栈D.队列2.在长度为n的顺序表中，删除第i个元素的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(n²)3.下列排序算法中，平均时间复杂度为O(nlogn)的是（）A.冒泡排序B.选择排序C.快速排序D.插入排序4.二叉树的前序遍历序列为ABDEC，中序遍历序列为DBEAC，后序遍历序列为（）A.DEBCAB.DBECAC.DEABCD.DBEAC5.在包含n个节点的二叉树中，度为2的节点数为n2，度为1的节点数为n1，叶子节点数为n0，则下列关系正确的是（）A.n0=n2+1B.n0=n2C.n1=n2+1D.n0=n1+16.下列算法中，不适用于查找无序序列的是（）A.顺序查找B.二分查找C.哈希查找D.分块查找7.下列哪种数据结构是非线性结构？（）A.栈B.队列C.树D.数组8.在图G中，从顶点v到顶点w的路径长度定义为（）A.路径上边的数目B.路径上顶点的数目C.路径上边权重的和D.路径上顶点权重的和9.下列哪种排序算法是不稳定的？（）A.插入排序B.冒泡排序C.快速排序D.归并排序10.动态规划方法适用于求解具有（）性质的问题A.最优子结构B.贪心选择C.回溯D.分治11.哈希表中处理冲突的方法不包括（）A.开放地址法B.链地址法C.二次探测法D.二分查找法12.下列哪种数据结构可以实现高效的插入和删除操作？（）A.数组B.链表C.栈D.队列13.在平衡二叉树中，任意节点的左右子树高度差不超过（）A.0B.1C.2D.314.下列算法中，时间复杂度与初始排列无关的是（）A.插入排序B.选择排序C.冒泡排序D.快速排序15.下列哪种图遍历算法可以用于检测图中是否存在环？（）A.深度优先搜索B.广度优先搜索C.普里姆算法D.克鲁斯卡尔算法16.在字符串匹配中，KMP算法的主要优点是（）A.时间复杂度为O(n)B.空间复杂度为O(1)C.不需要预处理模式串D.可以处理任意字符集17.下列哪种排序算法最不适合大数据量的排序？（）A.快速排序B.归并排序C.堆排序D.冒泡排序18.在二叉搜索树中，查找操作的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(n²)19.下列哪种数据结构可以实现快速查找第k小的元素？（）A.数组B.链表C.堆D.栈20.下列哪种算法不是贪心算法？（）A.Dijkstra算法B.Kruskal算法C.Prim算法D.回溯算法答案：1.答案：B解释：哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构，通常采用链地址法或开放地址法解决冲突，不是顺序存储结构。顺序表、栈和队列都是基于顺序存储或链接存储的线性结构，可以视为顺序存储的变体。2.答案：C解释：在顺序表中删除第i个元素，需要将i之后的所有元素向前移动一位，平均需要移动(n-i)/2个元素，因此时间复杂度为O(n)。3.答案：C解释：冒泡排序、选择排序和插入排序的平均时间复杂度都是O(n²)，而快速排序的平均时间复杂度为O(nlogn)。4.答案：A解释：根据前序遍历序列ABDEC和中序遍历序列DBEAC，可以确定二叉树的结构：-前序遍历的第一个节点A是根节点-在中序遍历中，A左边的是D、B、E，右边的是C-所以A的左子树包含D、B、E，右子树包含C-在左子树的前序遍历BDE中，B是根节点-在中序遍历DBE中，B左边是D，右边是E-所以B的左子树是D，右子树是E因此，二叉树的结构为：A的左子树是B，B的左子树是D，B的右子树是E，A的右子树是C后序遍历的顺序是左右根，所以后序遍历序列为DEBCA。5.答案：A解释：在二叉树中，设n为总节点数，n0为叶子节点数，n1为度为1的节点数，n2为度为2的节点数。根据二叉树的性质，有n=n0+n1+n2，且n=n1+2n2+1（根节点计数）。两式相减可得：n0=n2+1。6.答案：B解释：二分查找要求数据是有序的，因此不适用于查找无序序列。顺序查找、哈希查找和分块查找都可以用于无序序列。7.答案：C解释：树是非线性结构，因为节点之间存在一对多的关系。栈、队列和数组都是线性结构，节点之间是一对一的关系。8.答案：A解释：在图中，路径长度定义为路径上边的数目，而不是顶点数目或权重和。9.答案：C解释：快速排序是不稳定的排序算法，因为交换操作可能改变相同元素的相对顺序。插入排序、冒泡排序和归并排序都是稳定的排序算法。10.答案：A解释：动态规划方法适用于求解具有最优子结构性质的问题，即问题的最优解包含其子问题的最优解。贪心选择、回溯和分治是其他算法设计方法。11.答案：D解释：二分查找法不是哈希表中处理冲突的方法。开放地址法、链地址法和二次探测法都是处理哈希冲突的方法。12.答案：B解释：链表可以在O(1)时间内完成插入和删除操作（已知位置的情况下），而数组需要O(n)时间。栈和队列的插入和删除操作也有特定的限制。13.答案：B解释：在平衡二叉树（如AVL树）中，任意节点的左右子树高度差不超过1，这样可以保证树的高度保持在O(logn)，从而保证查找、插入和删除操作的时间复杂度为O(logn)。14.答案：B解释：选择排序的时间复杂度与初始排列无关，总是O(n²)。插入排序、冒泡排序和快速排序的时间复杂度都与初始排列有关。15.答案：A解释：深度优先搜索可以用于检测图中是否存在环，如果在DFS过程中发现一个已经被访问但不在当前DFS路径上的节点，则图中存在环。广度优先搜索也可以用于检测环，但不如DFS直观。普里姆算法和克鲁斯卡尔算法是求最小生成树的算法。16.答案：A解释：KMP算法的主要优点是时间复杂度为O(n+m)，其中n是文本串长度，m是模式串长度。空间复杂度为O(m)，因为需要构建部分匹配表。KMP算法需要预处理模式串，可以处理任意字符集。17.答案：D解释：冒泡排序的时间复杂度为O(n²)，不适合大数据量的排序。快速排序、归并排序和堆排序的平均时间复杂度都是O(nlogn)，适合大数据量的排序。18.答案：C解释：在二叉搜索树中，查找操作的平均时间复杂度为O(logn)，最坏情况下（树退化为链表）时间复杂度为O(n)。19.答案：C解释：堆可以实现快速查找第k小的元素，可以在O(1)时间内访问堆顶元素，并通过调整堆可以在O(logn)时间内找到第k小的元素。数组需要O(n)时间，链表需要O(n)时间，栈不支持这种操作。20.答案：D解释：回溯算法不是贪心算法。Dijkstra算法、Kruskal算法和Prim算法都是贪心算法的例子。二、填空题（总分30分）1.在长度为n的有序表中，使用二分查找法查找一个元素，平均比较次数为______。2.一个包含n个节点的完全二叉树，其深度为______。3.在快速排序中，每次划分操作的平均时间复杂度为______。4.图的邻接矩阵表示法中，无向图的邻接矩阵是一个______矩阵。5.在哈希表中，装填因子α的定义为______。6.二叉树的前序遍历、中序遍历和后序遍历都是______遍历。7.在堆排序中，建堆的时间复杂度为______。8.在字符串匹配中，KMP算法的时间复杂度为______。9.在动态规划中，最优子结构是指问题的最优解包含其子问题的______。10.在图的最小生成树算法中，Prim算法的时间复杂度为______，Kruskal算法的时间复杂度为______。11.在二叉搜索树中，中序遍历可以得到一个______序列。12.在排序算法中，稳定的排序是指______。13.在二叉树的存储结构中，链式存储比顺序存储更节省______。14.在图的遍历中，深度优先搜索使用______数据结构，广度优先搜索使用______数据结构。15.在哈希查找中，解决冲突的方法有______和______两种基本方法。答案：1.答案：log₂(n)解释：在长度为n的有序表中，使用二分查找法查找一个元素，每次比较都将搜索范围减半，平均比较次数为log₂(n)。2.答案：⌊log₂n⌋+1解释：一个包含n个节点的完全二叉树，其深度为⌊log₂n⌋+1。例如，n=1时深度为1，n=2~3时深度为2，n=4~7时深度为3，以此类推。3.答案：O(n)解释：在快速排序中，每次划分操作需要遍历整个数组，时间复杂度为O(n)。平均情况下，快速排序需要进行O(logn)次划分，因此总时间复杂度为O(nlogn)。4.答案：对称解释：在图的邻接矩阵表示法中，无向图的邻接矩阵是一个对称矩阵，因为边(i,j)和边(j,i)是同一条边。5.答案：表中元素个数/表长解释：在哈希表中，装填因子α的定义为表中元素个数与表长的比值，它反映了哈希表的装填程度，直接影响哈希冲突的概率。6.答案：深度解释：二叉树的前序遍历、中序遍历和后序遍历都是深度优先遍历，它们都沿着树的深度方向遍历节点。7.答案：O(n)解释：在堆排序中，建堆的过程是从最后一个非叶子节点开始，依次向上调整每个节点，直到根节点。每个节点的调整时间为O(logn)，但只有大约n/2个节点需要调整，因此建堆的时间复杂度为O(n)。8.答案：O(n+m)解释：在字符串匹配中，KMP算法的时间复杂度为O(n+m)，其中n是文本串长度，m是模式串长度。预处理模式串的时间复杂度为O(m)，匹配过程的时间复杂度为O(n)。9.答案：最优解解释：在动态规划中，最优子结构是指问题的最优解包含其子问题的最优解。这是动态规划能够有效解决问题的基础。10.答案：O(|V|²)或O(|E|log|V|)解释：在图的最小生成树算法中，Prim算法的时间复杂度为O(|V|²)（使用邻接矩阵）或O(|E|log|V|)（使用优先队列），Kruskal算法的时间复杂度为O(|E|log|E|)。11.答案：有序解释：在二叉搜索树中，中序遍历可以得到一个有序序列，这是二叉搜索树的一个重要性质。12.答案：相等元素的相对顺序保持不变解释：在排序算法中，稳定的排序是指相等元素的相对顺序在排序后保持不变。例如，在排序前a在b前面且a=b，排序后a仍然在b前面。13.答案：空间解释：在二叉树的存储结构中，链式存储比顺序存储更节省空间，因为顺序存储需要预留足够的空间来容纳可能的最大节点数，而链式存储只存储实际存在的节点。14.答案：栈、队列解释：在图的遍历中，深度优先搜索使用栈数据结构来记录待访问的节点，广度优先搜索使用队列数据结构来记录待访问的节点。15.答案：开放地址法、链地址法解释：在哈希查找中，解决冲突的方法有开放地址法和链地址法两种基本方法。开放地址法是通过寻找下一个空位置来解决冲突，链地址法是通过将冲突的元素存储在链表中来解决冲突。三、判断题（总分20分）1.栈和队列都是线性结构，但栈是先进后出，队列是先进先出。（）2.在二叉树中，度为2的节点数一定比度为1的节点数多1。（）3.快速排序在最坏情况下的时间复杂度为O(n²)。（）4.哈希表的查找时间与表中元素的数量无关。（）5.在无向图中，所有顶点的度数之和等于边数的两倍。（）6.归并排序是稳定的排序算法。（）7.在平衡二叉树中，任意节点的左右子树的高度差不超过1。（）8.二分查找只能用于有序表。（）9.动态规划算法通常比贪心算法效率更高。（）10.在有向无环图中，拓扑排序是唯一的。（）答案：1.答案：√解释：栈和队列都是线性结构，但栈是先进后出（FILO），队列是先进先出（FIFO）。这是它们最根本的区别。2.答案：×解释：在二叉树中，度为2的节点数不一定比度为1的节点数多1。正确的说法是：在二叉树中，度为0的节点数（叶子节点）比度为2的节点数多1，即n0=n2+1。3.答案：√解释：快速排序在最坏情况下（如数组已经有序或逆序），每次划分只能将问题规模减少1，时间复杂度为O(n²)。4.答案：×解释：哈希表的查找时间与表中元素的数量有关。装填因子α越大，冲突的概率越大，查找时间越长。理想情况下，哈希表的查找时间接近O(1)，但最坏情况下可能退化为O(n)。5.答案：√解释：在无向图中，每条边连接两个顶点，因此所有顶点的度数之和等于边数的两倍。6.答案：√解释：归并排序是稳定的排序算法，因为在合并过程中，相等元素的相对顺序保持不变。7.答案：√解释：在平衡二叉树（如AVL树）中，任意节点的左右子树高度差不超过1，这是平衡二叉树的定义。8.答案：√解释：二分查找要求数据是有序的，因此只能用于有序表。对于无序表，二分查找无法正确工作。9.答案：×解释：动态规划算法通常比贪心算法效率低，因为动态规划需要存储子问题的解，空间复杂度较高。贪心算法通常空间复杂度为O(1)，时间复杂度也可能较低。10.答案：×解释：在有向无环图中，拓扑排序不一定是唯一的。如果图中存在多个没有前驱的节点，可以选择任意一个作为起点，因此可能存在多种拓扑排序序列。四、简答题（总分50分）1.简述栈和队列的异同点。2.解释什么是平衡二叉树，并说明其重要性。3.简述二分查找的基本思想，并写出其时间复杂度。4.解释什么是哈希冲突，并列举三种解决哈希冲突的方法。5.简述深度优先搜索和广度优先搜索的基本思想及区别。6.解释什么是动态规划，并说明其适用的问题类型。7.简述快速排序的基本思想，并分析其时间复杂度。8.解释什么是二叉搜索树，并说明其基本操作的时间复杂度。9.简述KMP算法的基本思想。10.解释什么是图的最小生成树，并列举两种求最小生成树的算法。答案：1.答案：栈和队列的相同点：-都是线性数据结构-都只能在端点进行插入和删除操作-都可以用数组或链表实现栈和队列的不同点：-栈是后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作-队列是先进先出（FIFO）的数据结构，只能在队尾插入，在队头删除-栈的应用包括函数调用、表达式求值、括号匹配等-队列的应用包括任务调度、消息传递、广度优先搜索等2.答案：平衡二叉树是一种特殊的二叉搜索树，其中任意节点的左右子树高度差不超过1。常见的平衡二叉树有AVL树、红黑树等。平衡二叉树的重要性：-保证树的高度保持在O(logn)，从而保证查找、插入和删除操作的时间复杂度为O(logn)-避免了普通二叉搜索树在插入有序数据时退化为链表的情况-在需要频繁进行查找、插入和删除操作的场景中，平衡二叉树能够提供稳定的性能-在数据库索引、文件系统等实际应用中有广泛的应用3.答案：二分查找的基本思想：-在有序表中，首先将中间元素与目标值比较-如果中间元素等于目标值，则查找成功-如果中间元素大于目标值，则在左半部分继续查找-如果中间元素小于目标值，则在右半部分继续查找-重复上述过程，直到找到目标值或查找范围为空时间复杂度：-每次比较都将查找范围减半，因此时间复杂度为O(logn)-最坏情况下需要比较log₂n次，平均情况下也需要比较约log₂n次4.答案：哈希冲突是指不同的关键字通过哈希函数计算得到相同的哈希地址的现象。解决哈希冲突的三种方法：-开放地址法：当发生冲突时，按照一定的规则寻找下一个可用的位置。常见的有线性探测法（顺序查找下一个位置）、二次探测法（按平方顺序查找下一个位置）等。-链地址法：将所有哈希地址相同的元素存储在一个链表中，发生冲突时将新元素插入到链表中。-再哈希法：使用多个哈希函数，当一个哈希函数发生冲突时，使用另一个哈希函数计算新的地址。5.答案：深度优先搜索（DFS）的基本思想：-从起始节点开始，访问一个节点后，继续深度优先访问其未访问的邻接节点-当一个节点的所有邻接节点都被访问后，回溯到前一个节点，继续深度优先访问其他邻接节点-使用栈来记录待访问的节点广度优先搜索（BFS）的基本思想：-从起始节点开始，先访问所有直接邻接节点-然后依次访问这些邻接节点的未访问邻接节点-使用队列来记录待访问的节点区别：-DFS沿着深度方向遍历，BFS沿着广度方向遍历-DFS使用栈，BFS使用队列-DFS适合寻找路径、检测环等，BFS适合寻找最短路径、连通分量等6.答案：动态规划是一种通过将问题分解为子问题，并存储子问题的解来避免重复计算，从而解决问题的算法设计方法。动态规划适用的问题类型：-具有最优子结构性质：问题的最优解包含其子问题的最优解-具有重叠子问题性质：问题可以被分解为若干个子问题，且这些子问题会被重复计算-无后效性：当前状态只与前一状态有关，与到达当前状态的路径无关动态规划的步骤：-定义状态-状态转移方程-确定初始条件-计算顺序（自底向上或自顶向下）7.答案：快速排序的基本思想：-选择一个基准元素（pivot）-将数组分为两部分，左边部分小于等于基准元素，右边部分大于基准元素-对左右两部分递归地进行快速排序时间复杂度分析：-平均情况：O(nlogn)-每次划分平均将问题规模减半-递归深度为log₂n-每层递归需要O(n)时间-最坏情况：O(n²)-当数组已经有序或逆序时，每次划分只能将问题规模减少1-递归深度为n-每层递归需要O(n)时间-最好情况：O(nlogn)-每次划分都能将问题均匀地分为两部分8.答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于其左子树中所有节点的值，小于其右子树中所有节点的值。二叉搜索树的基本操作：-查找：从根节点开始，比较目标值与当前节点的值，如果相等则查找成功，如果目标值小于当前节点的值则在左子树中查找，否则在右子树中查找-插入：查找插入位置，将新节点插入到适当的位置-删除：找到要删除的节点，根据其子节点情况执行不同操作：如果没有子节点，直接删除如果有一个子节点，用子节点替换被删除节点如果有两个子节点，找到其前驱或后继节点，用该节点替换被删除节点，然后递归删除前驱或后继节点时间复杂度：-平均情况：O(logn)-在平衡的二叉搜索树中，树的高度为O(logn)-最坏情况：O(n)-当树退化为链表时，树的高度为O(n)9.答案：KMP算法是一种高效的字符串匹配算法，其基本思想是利用模式串的特征来避免不必要的比较。KMP算法的基本步骤：-预处理模式串，构建部分匹配表（next数组）next[i]表示模式串的前i个字符组成的子串的最长相同前后缀的长度（不包括整个子串）-使用部分匹配表进行匹配当文本串和模式串的当前字符不匹配时，根据部分匹配表确定模式串应该向右移动的距离移动距离为已匹配长度减去next[已匹配长度]KMP算法的优点：-时间复杂度为O(n+m)，其中n是文本串长度，m是模式串长度-不需要回溯文本串，只需要回溯模式串-避免了朴素匹配算法中的重复比较10.答案：图的最小生成树是一个包含图中所有顶点的连通子图，且边的权重之和最小，且不包含环。两种求最小生成树的算法：-Prim算法：从任意一个顶点开始，逐步将顶点加入最小生成树每次选择与已加入顶点相连的权值最小的边使用优先队列来选择最小权值的边时间复杂度为O(|E|log|V|)（使用优先队列）-Kruskal算法：将所有边按权值从小到大排序依次选择边，如果加入该边不会形成环，则将该边加入最小生成树使用并查集来检测环时间复杂度为O(|E|log|E|)五、算法分析题（总分40分）1.分析以下算法的时间复杂度和空间复杂度：```pythondeffunc1(n):sum=0foriinrange(n):forjinrange(i):sum+=1returnsum```2.分析以下算法的时间复杂度和空间复杂度：```pythondeffunc2(n):ifn<=1:return1returnfunc2(n-1)+func2(n-2)```3.分析以下算法的时间复杂度和空间复杂度：```pythondeffunc3(arr):n=len(arr)foriinrange(n):min_idx=iforjinrange(i+1,n):ifarr[j]<arr[min_idx]:min_idx=jarr[i],arr[min_idx]=arr[min_idx],arr[i]returnarr```4.分析以下算法的时间复杂度和空间复杂度：```pythondeffunc4(graph,start):visited=[False]len(graph)queue=[start]visited[start]=Truewhilequeue:node=queue.pop(0)print(node,end='')forneighboringraph[node]:ifnotvisited[neighbor]:visited[neighbor]=Truequeue.append(neighbor)```5.分析以下算法的时间复杂度和空间复杂度：```pythondeffunc5(s,p):m,n=len(s),len(p)dp=[[False](n+1)for_inrange(m+1)]dp[0][0]=Trueforjinrange(1,n+1):ifp[j-1]=='':dp[0][j]=dp[0][j-2]foriinrange(1,m+1):forjinrange(1,n+1):ifp[j-1]==s[i-1]orp[j-1]=='.':dp[i][j]=dp[i-1][j-1]elifp[j-1]=='':dp[i][j]=dp[i][j-2]ifp[j-2]==s[i-1]orp[j-2]=='.':dp[i][j]=dp[i][j]ordp[i-1][j]returndp[m][n]```答案：1.答案：时间复杂度分析：-外层循环执行n次-内层循环执行i次，i从0到n-1-总的执行次数为0+1+2+...+(n-1)=n(n-1)/2-因此，时间复杂度为O(n²)空间复杂度分析：-只使用了常数个变量（sum,i,j）-因此，空间复杂度为O(1)2.答案：时间复杂度分析：-这是一个递归实现的斐波那契数列计算-函数func2(n)会调用func2(n-1)和func2(n-2)-递归树的高度为n，每个节点有两个分支-总的递归调用次数约为2^n-因此，时间复杂度为O(2^n)空间复杂度分析：-递归调用的深度为n-每次递归调用都需要在栈上保存状态-因此，空间复杂度为O(n)3.答案：时间复杂度分析：-这是一个选择排序算法-外层循环执行n次-内层循环执行n-i-1次，i从0到n-1-总的执行次数约为n(n-1)/2-因此，时间复杂度为O(n²)空间复杂度分析：-只使用了常数个变量（n,i,j,min_idx）-原地排序，不需要额外的空间-因此，空间复杂度为O(1)4.答案：时间复杂度分析：-这是一个广度优先搜索算法-每个节点和每条边都会被访问一次-如果图的节点数为|V|，边数为|E|，则时间复杂度为O(|V|+|E|)空间复杂度分析：-visited数组需要O(|V|)空间-queue队列在最坏情况下需要O(|V|)空间（当图为完全图时）-因此，空间复杂度为O(|V|)5.答案：时间复杂度分析：-这是一个正则表达式匹配的动态规划解法-使用了一个二维数组dp，大小为(m+1)×(n+1)-填充dp数组需要双重循环，外层循环执行m次，内层循环执行n次-因此，时间复杂度为O(m×n)，其中m是字符串s的长度，n是模式串p的长度空间复杂度分析：-使用了一个二维数组dp，大小为(m+1)×(n+1)-因此，空间复杂度为O(m×n)六、算法设计题（总分60分）1.设计一个算法，实现两个有序链表的合并。2.设计一个算法，实现二叉树的层序遍历。3.设计一个算法，实现字符串匹配的KMP算法。4.设计一个算法，实现图的深度优先搜索。5.设计一个算法，实现快速排序。6.设计一个算法，实现二叉搜索树的查找、插入和删除操作。7.设计一个算法，实现0-1背包问题的动态规划解法。8.设计一个算法，实现Dijkstra最短路径算法。答案：1.答案：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1,l2):创建一个哑节点作为合并后的链表的头dummy=ListNode()current=dummy遍历两个链表，比较节点值，将较小的节点加入合并后的链表whilel1andl2:ifl1.val<=l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.next将剩余的链表直接连接到合并后的链表ifl1:current.next=l1else:current.next=l2返回合并后的链表（跳过哑节点）returndummy.next```2.答案：```pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevelOrder(root):ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult```3.答案：```pythondefkmp_search(s,p):ifnotp:return0构建部分匹配表next_arr=[0]len(p)j=0foriinrange(1,len(p)):whilej>0andp[i]!=p[j]:j=next_arr[j-1]ifp[i]==p[j]:j+=1next_arr[i]=j使用部分匹配表进行匹配j=0foriinrange(len(s)):whilej>0ands[i]!=p[j]:j=next_arr[j-1]ifs[i]==p[j]:j+=1ifj==len(p):returni-j+1return-1```4.答案：```pythonfromcollectionsimportdequedefdfs(graph,start):visited=[False]len(graph)stack=[start]result=[]whilestack:node=stack.pop()ifnotvisited[node]:visited[node]=Trueresult.append(node)将未访问的邻接节点加入栈forneighborinreversed(graph[node]):ifnotvisited[neighbor]:stack.append(neighbor)returnresult递归实现defdfs_recursive(graph,start,visited=None):ifvisitedisNone:visited=[False]len(graph)visited[start]=Trueresult=[start]forneighboringraph[start]:ifnotvisited[neighbor]:result.extend(dfs_recursive(graph,neighbor,visited))returnresult```5.答案：```pythondefquick_sort(arr):iflen(arr)<=1:returnarr选择基准元素（这里选择第一个元素作为基准）pivot=arr[0]将数组分为两部分：小于等于基准的元素和大于基准的元素left=[xforxinarr[1:]ifx<=pivot]right=[xforxinarr[1:]ifx>pivot]递归排序并合并结果returnquick_sort(left)+[pivot]+quick_sort(right)原地排序实现defquick_sort_inplace(arr,low=0,high=None):ifhighisNone:high=len(arr)-1iflow<high:分区操作，返回基准元素的索引pivot_idx=partition(arr,low,high)递归排序左半部分和右半部分quick_sort_inplace(arr,low,pivot_idx-1)quick_sort_inplace(arr,pivot_idx+1,high)defpartition(arr,low,high):选择基准元素（这里选择最后一个元素作为基准）pivot=arr[high]i=low-1forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]将基准元素放到正确的位置arr[i+1],arr[high]=arr[high],arr[i+1]returni+1```6.答案：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightclassBST:def__init__(self):self.root=Nonedefsearch(self,val):returnself._search(self.root,val)def_search(self,node,val):ifnotnode:returnFalseifval==node.val:returnTrueelifval<node.val:returnself._search(node.left,val)else:returnself._search(node.right,val)definsert(self,val):self.root=self._insert(self.root,val)def_insert(self,node,val):ifnotnode:returnTreeNode(val)ifval<node.val:node.left=self._insert(node.left,val)elifval>node.val:node.right=self._insert(node.right,val)returnnodedefdelete(self,val):self.root=self._delete(self.root,val)def_delete(self,node,val):ifnotnode:returnNoneifval<node.val:node.left=self._delete(node.left,val)elifval>node.val:node.right=self._delete(node.right,val)else:找到要删除的节点ifnotnode.left:returnnode.rightelifnotnode.right:returnnode.leftelse:有两个子节点的情况找到右子树的最小节点min_node=self._find_min(node.right)复制最小节点的值node.val=min_node.val删除最小节点node.right=self._delete(node.right,min_node.val)returnnodedef_find_min(self,node):whilenode.left:node=node.leftreturnnode```7.答案：```pythondefknapsack(weights,values,capacity):n=len(weights)创建一个二维数组dp，dp[i][j]表示前i个物品在容量为j的背包中的最大价值dp=[[0](capacity+1)for_inrange(n+1)]填充dp数组foriinrange(1,n+1):forjinrange(1,capacity+1):ifweights[i-1]<=j:可以选择放入或不放入第i个物品dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i-1]]+values[i-1])else:不能放入第i个物品dp[i][j]=dp[i-1][j]