《算法设计与分析》-内上机实验题目及其解答

《算法设计与分析》-内上机实验题目及其解答汇报人：AA2024-01-19实验一：基本数据结构操作实验二：排序算法设计与分析实验三：查找算法设计与分析实验四：图论算法设计与分析实验五：动态规划算法设计与分析实验六：贪心算法设计与分析实验七：分治算法设计与分析01实验一：基本数据结构操作数组创建与初始化数组遍历与访问链表创建与插入链表遍历与访问数组与链表操作使用循环或递归方式创建并初始化一个数组，例如使用for循环遍历数组元素并赋值。定义链表节点结构，并实现链表的创建、插入新节点等操作。通过下标访问数组元素，并使用循环结构遍历数组中的所有元素。使用循环或递归方式遍历链表，并访问链表中的每个节点。栈的基本操作实现栈的初始化、入栈（push）、出栈（pop）、查看栈顶元素等操作。队列的基本操作实现队列的初始化、入队（enqueue）、出队（dequeue）、查看队首和队尾元素等操作。栈与队列的应用利用栈和队列的特性解决一些实际问题，如括号匹配、表达式求值等。栈与队列操作03020103字符串排序与查找使用快速排序、归并排序等算法对字符串进行排序，并实现字符串的查找功能。01字符串基本操作实现字符串的输入、输出、连接、比较等基本操作。02字符串模式匹配使用KMP算法或Boyer-Moore算法等实现字符串的模式匹配功能。字符串操作实验代码提供完整的实验代码，包括数据结构定义、函数实现和主程序等部分。运行结果展示实验代码的运行结果，包括输入数据、输出数据和程序执行过程中的关键信息。同时，对实验结果进行分析和讨论，验证实验的正确性和有效性。实验代码与运行结果02实验二：排序算法设计与分析将未排序的元素插入到已排序的序列中，从而得到一个新的、更长的已排序序列。从第一个元素开始，认为该元素已被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。最好情况下为O(n)，最坏和平均情况下为O(n^2)。原理过程时间复杂度插入排序原理在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。过程首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；重复第二步，直到所有元素均排序完毕。时间复杂度无论最好、最坏和平均情况，时间复杂度均为O(n^2)。选择排序比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。比较相邻的元素。如果第一个比第二个大，就交换他们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。最好情况下为O(n)，最坏和平均情况下为O(n^2)。原理过程时间复杂度冒泡排序通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。选择一个基准元素；重新排列数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。最好情况下为O(nlogn)，最坏情况下为O(n^2)，平均情况下为O(nlogn)。原理过程时间复杂度快速排序【此处应提供具体的实验代码及运行结果截图或描述，因缺少具体信息，故无法给出。】实验代码与运行结果03实验三：查找算法设计与分析时间复杂度线性查找的时间复杂度为O(n)，其中n为数据结构中元素的个数。空间复杂度线性查找的空间复杂度为O(1)，因为它只需要一个变量来存储所查元素的值。算法思想线性查找是一种最简单的查找方法，它从数据结构的一端开始，顺序扫描，直到找到所查元素为止。线性查找算法思想：二分查找是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。时间复杂度：二分查找的时间复杂度为O(logn)，其中n为数据结构中元素的个数。空间复杂度：二分查找的空间复杂度为O(1)，因为它只需要几个变量来存储中间值和索引。二分查找算法思想哈希表查找是一种通过计算关键字的哈希值来快速定位元素位置的查找算法。哈希表是一种数据结构，它使用哈希函数将关键字映射到数组的索引上。在哈希表中查找元素时，只需要计算关键字的哈希值，然后直接定位到数组中相应的位置即可。时间复杂度哈希表查找的时间复杂度为O(1)，因为哈希函数可以在常数时间内计算出关键字的哈希值，并定位到数组中相应的位置。空间复杂度哈希表的空间复杂度取决于哈希函数的选择和哈希表的大小。通常情况下，哈希表的空间复杂度为O(n)，其中n为数据结构中元素的个数。哈希表查找线性查找代码示例（Python）实验代码与运行结果03foriinrange(len(arr))01```python02deflinear_search(arr,x)实验代码与运行结果ifarr[i]==x实验代码与运行结果returnireturn-1实验代码与运行结果```二分查找代码示例（Python）实验代码与运行结果```pythondefbinary_search(arr,low,high,x)实验代码与运行结果实验代码与运行结果ifhigh>=lowmid=(high+low)//2ifarr[mid]==x实验代码与运行结果returnmidreturnbinary_search(arr,low,mid-1,x)elifarr[mid]>x实验代码与运行结果elsereturnbinary_search(arr,mid+1,high,x)实验代码与运行结果elsereturn-1实验代码与运行结果实验代码与运行结果```哈希表查找代码示例（Python）实验代码与运行结果010203classHashTabledef__init__(self)```python123self.size=10000self.table=[None]*self.sizedefhash_function(self,key)实验代码与运行结果01returnkey%self.size02definsert(self,key,value)03hash_index=self.hash_function(key)实验代码与运行结果实验代码与运行结果01self.table[hash_index]=value02defsearch(self,key)hash_index=self.hash_function(key)03VSreturnself.table[hash_index]ifself.table[hash_index]isnotNoneelse-1```实验代码与运行结果04实验四：图论算法设计与分析图可以采用邻接矩阵或邻接表来表示。邻接矩阵适用于稠密图，而邻接表适用于稀疏图。图的遍历可以采用深度优先搜索（DFS）或广度优先搜索（BFS）算法。DFS从某个顶点出发，尽可能深地搜索图的分支，直到达到目标顶点或无法再深入为止。BFS则从某个顶点出发，逐层遍历图中的所有顶点。图的表示图的遍历图的表示与遍历Dijkstra算法01适用于没有负权边的有向图或无向图，可以求出从源点到其余各顶点的最短路径。Floyd算法02适用于任意有向图或无向图，可以求出任意两点之间的最短路径。Bellman-Ford算法03适用于有负权边的有向图，可以判断图中是否存在负权环，并求出从源点到其余各顶点的最短路径。最短路径算法从某个顶点出发，每次选择一条连接已选顶点和未选顶点中权值最小的边，直到所有顶点都被选中为止。每次选择一条权值最小的边，如果该边连接的两个顶点不在同一连通分量中，则将其加入最小生成树中，直到所有顶点都在同一连通分量中为止。最小生成树算法Kruskal算法Prim算法根据具体实验要求编写相应的代码实现上述算法。实验代码展示实验代码的运行结果，包括输入数据、输出数据以及程序运行时间等信息。同时，需要对实验结果进行分析和讨论，验证算法的正确性和有效性。运行结果实验代码与运行结果05实验五：动态规划算法设计与分析给定一组物品，每个物品有一定的重量和价值，背包的总容量有限。如何选择物品放入背包，使得背包内物品的总价值最大。问题描述O(NW)，其中N为物品数量，W为背包容量。时间复杂度背包问题给定两个字符串X和Y，找出它们的最长公共子序列。问题描述定义dp[i][j]为X的前i个字符和Y的前j个字符的最长公共子序列长度。当X[i]=Y[j]时，dp[i][j]=dp[i-1][j-1]+1；否则，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。动态规划思路O(NM)，其中N和M分别为字符串X和Y的长度。时间复杂度最长公共子序列问题矩阵链乘法问题给定一个矩阵链，如何确定乘法运算的次序，使得计算该矩阵链所需的最少数乘次数最少。问题描述O(N^3)，其中N为矩阵链中矩阵的数量。时间复杂度实验代码与运行结果【此处应提供实验代码及运行结果截图或文字描述】06实验六：贪心算法设计与分析活动选择问题问题描述给定一个n个活动的集合S，每个活动都有一个开始时间和一个结束时间，且被允许的活动集合中任意两个活动不能有时间上的交集。要求找到最大的相互兼容的活动子集。贪心策略每次选择结束时间最早的活动，以便为其他活动留下尽可能多的时间。算法实现首先将所有活动按结束时间从小到大排序，然后从第一个活动开始依次选择，如果当前活动与已选择的活动集合中的活动不冲突，则将其加入结果集合。货币找零问题首先将硬币按面值从大到小排序，然后从最大的硬币开始依次选择，如果当前硬币的面值小于等于目标金额，则将其加入结果集合，并更新目标金额为剩余金额。算法实现给定一些面额不同的硬币，以及一个总金额。要求用最少的硬币数量凑出这个总金额。问题描述每次选择面值最大的硬币，以便用最少的硬币数量达到目标金额。贪心策略给定一个字符串和它的字符频率，要求构造一个哈夫曼树，并生成对应的哈夫曼编码。每次选择频率最小的两个节点合并成一个新节点，新节点的频率为两个子节点频率之和。然后将新节点加入优先队列，以便后续继续合并。首先将所有字符按频率从小到大排序，并构建对应的节点和优先队列。然后不断从优先队列中取出频率最小的两个节点合并成新节点，并将新节点加入优先队列。直到优先队列中只剩下一个节点为止，该节点即为哈夫曼树的根节点。最后根据哈夫曼树生成对应的哈夫曼编码。问题描述贪心策略算法实现哈夫曼编码问题010203活动选择问题代码示例```pythondefactivity_selection(activities)实验代码与运行结果实验代码与运行结果实验代码与运行结果n=len(activities)result=[activities[0]]#初始化结果集合k=0#已选择活动的索引实验代码与运行结果01foriinrange(1,n)02ifactivities[i][0]>=result[k][1]:#如果当前活动与已选择的活动不冲突03result.append(activities[i])#将当前活动加入结果集合k+=1returnresult实验代码与运行结果实验代码与运行结果```02货币找零问题代码示例03```python01defcoin_change(coins,amount)coins.sort(reverse=True)#按面值从大到小排序result=[]#初始化结果集合实验代码与运行结果forcoinincoinswhileamount>=coin:#如果当前硬币面值小于等于目标金额amount-=coin#更新目标金额为剩余金额010203实验代码与运行结果result.append(coin)#将当前硬币加入结果集合returnresultifamount==0elseNone#如果目标金额为0则返回结果集合，否则返回None表示无法凑出目标金额实验代码与运行结果哈夫曼编码问题代码示例```python```实验代码与运行结果importheapqclassNodedef__init__(self,freq,char=None,left=None,right=None)010203实验代码与运行结果实验代码与运行结果030201self.freq=freqself.char=charself.left=left实验代码与运行结果010203self.right=rightdef__lt__(self,other)returnself.freq<other.freq实验代码与运行结果defhuffman_encoding(freqs)heap=[Node(freq,char)forchar,freqinfreqs.items()]#构建初始节点和优先队列heapq.heapify(heap)#堆化优先队列实验代码与运行结果whilelen(heap)>1:#当优先队列中至少有两个节点时node1=heapq.heappop(heap)#取出频率最小的节点node2=heapq.heappop(heap)#取出频率次小的节点merged=Node(node1.freq+node2.freq,left=node1,right=node2)#合并节点heapq.heappush(heap,merged)#将新节点加入优先队列huffman_tree=heap[0]#哈夫曼树的根节点实验代码与运行结果实验代码与运行结果defbuild_codes(node,prefix,codes):#构建哈夫曼编码的递归函数codes={}#哈夫曼编码字典ifnode.char:#叶节点，将字符和对应编码加入字典codes[node.char]=prefixelse:#非叶节点，递归处理左右子树build_codes(node.left,prefix实验代码与运行结果07实验七：分治算法设计与分析算法思想二分搜索算法是一种在有序数组中查找特