《算法設(shè)計(jì)與分析》-內(nèi)上機(jī)實(shí)驗(yàn)題目及其解答匯報(bào)人：AA2024-01-19實(shí)驗(yàn)一：基本數(shù)據(jù)結(jié)構(gòu)操作實(shí)驗(yàn)二：排序算法設(shè)計(jì)與分析實(shí)驗(yàn)三：查找算法設(shè)計(jì)與分析實(shí)驗(yàn)四：圖論算法設(shè)計(jì)與分析實(shí)驗(yàn)五：動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)與分析實(shí)驗(yàn)六：貪心算法設(shè)計(jì)與分析實(shí)驗(yàn)七：分治算法設(shè)計(jì)與分析01實(shí)驗(yàn)一：基本數(shù)據(jù)結(jié)構(gòu)操作數(shù)組創(chuàng)建與初始化數(shù)組遍歷與訪問(wèn)鏈表創(chuàng)建與插入鏈表遍歷與訪問(wèn)數(shù)組與鏈表操作使用循環(huán)或遞歸方式創(chuàng)建并初始化一個(gè)數(shù)組，例如使用for循環(huán)遍歷數(shù)組元素并賦值。定義鏈表節(jié)點(diǎn)結(jié)構(gòu)，并實(shí)現(xiàn)鏈表的創(chuàng)建、插入新節(jié)點(diǎn)等操作。通過(guò)下標(biāo)訪問(wèn)數(shù)組元素，并使用循環(huán)結(jié)構(gòu)遍歷數(shù)組中的所有元素。使用循環(huán)或遞歸方式遍歷鏈表，并訪問(wèn)鏈表中的每個(gè)節(jié)點(diǎn)。棧的基本操作實(shí)現(xiàn)棧的初始化、入棧（push）、出棧（pop）、查看棧頂元素等操作。隊(duì)列的基本操作實(shí)現(xiàn)隊(duì)列的初始化、入隊(duì)（enqueue）、出隊(duì)（dequeue）、查看隊(duì)首和隊(duì)尾元素等操作。棧與隊(duì)列的應(yīng)用利用棧和隊(duì)列的特性解決一些實(shí)際問(wèn)題，如括號(hào)匹配、表達(dá)式求值等。棧與隊(duì)列操作03020103字符串排序與查找使用快速排序、歸并排序等算法對(duì)字符串進(jìn)行排序，并實(shí)現(xiàn)字符串的查找功能。01字符串基本操作實(shí)現(xiàn)字符串的輸入、輸出、連接、比較等基本操作。02字符串模式匹配使用KMP算法或Boyer-Moore算法等實(shí)現(xiàn)字符串的模式匹配功能。字符串操作實(shí)驗(yàn)代碼提供完整的實(shí)驗(yàn)代碼，包括數(shù)據(jù)結(jié)構(gòu)定義、函數(shù)實(shí)現(xiàn)和主程序等部分。運(yùn)行結(jié)果展示實(shí)驗(yàn)代碼的運(yùn)行結(jié)果，包括輸入數(shù)據(jù)、輸出數(shù)據(jù)和程序執(zhí)行過(guò)程中的關(guān)鍵信息。同時(shí)，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析和討論，驗(yàn)證實(shí)驗(yàn)的正確性和有效性。實(shí)驗(yàn)代碼與運(yùn)行結(jié)果02實(shí)驗(yàn)二：排序算法設(shè)計(jì)與分析將未排序的元素插入到已排序的序列中，從而得到一個(gè)新的、更長(zhǎng)的已排序序列。從第一個(gè)元素開始，認(rèn)為該元素已被排序；取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；如果該元素（已排序）大于新元素，將該元素移到下一位置；重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；將新元素插入到該位置后；重復(fù)步驟2~5。最好情況下為O(n)，最壞和平均情況下為O(n^2)。原理過(guò)程時(shí)間復(fù)雜度插入排序原理在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ɑ蜃畲螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。過(guò)程首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾；重復(fù)第二步，直到所有元素均排序完畢。時(shí)間復(fù)雜度無(wú)論最好、最壞和平均情況，時(shí)間復(fù)雜度均為O(n^2)。選擇排序比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)；對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)；針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。最好情況下為O(n)，最壞和平均情況下為O(n^2)。原理過(guò)程時(shí)間復(fù)雜度冒泡排序通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。選擇一個(gè)基準(zhǔn)元素；重新排列數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)操作；遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。最好情況下為O(nlogn)，最壞情況下為O(n^2)，平均情況下為O(nlogn)。原理過(guò)程時(shí)間復(fù)雜度快速排序【此處應(yīng)提供具體的實(shí)驗(yàn)代碼及運(yùn)行結(jié)果截圖或描述，因缺少具體信息，故無(wú)法給出?！繉?shí)驗(yàn)代碼與運(yùn)行結(jié)果03實(shí)驗(yàn)三：查找算法設(shè)計(jì)與分析時(shí)間復(fù)雜度線性查找的時(shí)間復(fù)雜度為O(n)，其中n為數(shù)據(jù)結(jié)構(gòu)中元素的個(gè)數(shù)?？臻g復(fù)雜度線性查找的空間復(fù)雜度為O(1)，因?yàn)樗恍枰粋€(gè)變量來(lái)存儲(chǔ)所查元素的值。算法思想線性查找是一種最簡(jiǎn)單的查找方法，它從數(shù)據(jù)結(jié)構(gòu)的一端開始，順序掃描，直到找到所查元素為止。線性查找算法思想：二分查找是一種在有序數(shù)組中查找某一特定元素的查找算法。查找過(guò)程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則查找過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。時(shí)間復(fù)雜度：二分查找的時(shí)間復(fù)雜度為O(logn)，其中n為數(shù)據(jù)結(jié)構(gòu)中元素的個(gè)數(shù)?？臻g復(fù)雜度：二分查找的空間復(fù)雜度為O(1)，因?yàn)樗恍枰獛讉€(gè)變量來(lái)存儲(chǔ)中間值和索引。二分查找算法思想哈希表查找是一種通過(guò)計(jì)算關(guān)鍵字的哈希值來(lái)快速定位元素位置的查找算法。哈希表是一種數(shù)據(jù)結(jié)構(gòu)，它使用哈希函數(shù)將關(guān)鍵字映射到數(shù)組的索引上。在哈希表中查找元素時(shí)，只需要計(jì)算關(guān)鍵字的哈希值，然后直接定位到數(shù)組中相應(yīng)的位置即可。時(shí)間復(fù)雜度哈希表查找的時(shí)間復(fù)雜度為O(1)，因?yàn)楣：瘮?shù)可以在常數(shù)時(shí)間內(nèi)計(jì)算出關(guān)鍵字的哈希值，并定位到數(shù)組中相應(yīng)的位置?？臻g復(fù)雜度哈希表的空間復(fù)雜度取決于哈希函數(shù)的選擇和哈希表的大小。通常情況下，哈希表的空間復(fù)雜度為O(n)，其中n為數(shù)據(jù)結(jié)構(gòu)中元素的個(gè)數(shù)。哈希表查找線性查找代碼示例（Python）實(shí)驗(yàn)代碼與運(yùn)行結(jié)果03foriinrange(len(arr))01```python02deflinear_search(arr,x)實(shí)驗(yàn)代碼與運(yùn)行結(jié)果ifarr[i]==x實(shí)驗(yàn)代碼與運(yùn)行結(jié)果returnireturn-1實(shí)驗(yàn)代碼與運(yùn)行結(jié)果```二分查找代碼示例（Python）實(shí)驗(yàn)代碼與運(yùn)行結(jié)果```pythondefbinary_search(arr,low,high,x)實(shí)驗(yàn)代碼與運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果ifhigh>=lowmid=(high+low)//2ifarr[mid]==x實(shí)驗(yàn)代碼與運(yùn)行結(jié)果returnmidreturnbinary_search(arr,low,mid-1,x)elifarr[mid]>x實(shí)驗(yàn)代碼與運(yùn)行結(jié)果elsereturnbinary_search(arr,mid+1,high,x)實(shí)驗(yàn)代碼與運(yùn)行結(jié)果elsereturn-1實(shí)驗(yàn)代碼與運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果```哈希表查找代碼示例（Python）實(shí)驗(yàn)代碼與運(yùn)行結(jié)果010203classHashTabledef__init__(self)```python123self.size=10000self.table=[None]*self.sizedefhash_function(self,key)實(shí)驗(yàn)代碼與運(yùn)行結(jié)果01returnkey%self.size02definsert(self,key,value)03hash_index=self.hash_function(key)實(shí)驗(yàn)代碼與運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果01self.table[hash_index]=value02defsearch(self,key)hash_index=self.hash_function(key)03VSreturnself.table[hash_index]ifself.table[hash_index]isnotNoneelse-1```實(shí)驗(yàn)代碼與運(yùn)行結(jié)果04實(shí)驗(yàn)四：圖論算法設(shè)計(jì)與分析圖可以采用鄰接矩陣或鄰接表來(lái)表示。鄰接矩陣適用于稠密圖，而鄰接表適用于稀疏圖。圖的遍歷可以采用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）算法。DFS從某個(gè)頂點(diǎn)出發(fā)，盡可能深地搜索圖的分支，直到達(dá)到目標(biāo)頂點(diǎn)或無(wú)法再深入為止。BFS則從某個(gè)頂點(diǎn)出發(fā)，逐層遍歷圖中的所有頂點(diǎn)。圖的表示圖的遍歷圖的表示與遍歷Dijkstra算法01適用于沒有負(fù)權(quán)邊的有向圖或無(wú)向圖，可以求出從源點(diǎn)到其余各頂點(diǎn)的最短路徑。Floyd算法02適用于任意有向圖或無(wú)向圖，可以求出任意兩點(diǎn)之間的最短路徑。Bellman-Ford算法03適用于有負(fù)權(quán)邊的有向圖，可以判斷圖中是否存在負(fù)權(quán)環(huán)，并求出從源點(diǎn)到其余各頂點(diǎn)的最短路徑。最短路徑算法從某個(gè)頂點(diǎn)出發(fā)，每次選擇一條連接已選頂點(diǎn)和未選頂點(diǎn)中權(quán)值最小的邊，直到所有頂點(diǎn)都被選中為止。每次選擇一條權(quán)值最小的邊，如果該邊連接的兩個(gè)頂點(diǎn)不在同一連通分量中，則將其加入最小生成樹中，直到所有頂點(diǎn)都在同一連通分量中為止。最小生成樹算法Kruskal算法Prim算法根據(jù)具體實(shí)驗(yàn)要求編寫相應(yīng)的代碼實(shí)現(xiàn)上述算法。實(shí)驗(yàn)代碼展示實(shí)驗(yàn)代碼的運(yùn)行結(jié)果，包括輸入數(shù)據(jù)、輸出數(shù)據(jù)以及程序運(yùn)行時(shí)間等信息。同時(shí)，需要對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析和討論，驗(yàn)證算法的正確性和有效性。運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果05實(shí)驗(yàn)五：動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)與分析給定一組物品，每個(gè)物品有一定的重量和價(jià)值，背包的總?cè)萘坑邢?。如何選擇物品放入背包，使得背包內(nèi)物品的總價(jià)值最大。問(wèn)題描述O(NW)，其中N為物品數(shù)量，W為背包容量。時(shí)間復(fù)雜度背包問(wèn)題給定兩個(gè)字符串X和Y，找出它們的最長(zhǎng)公共子序列。問(wèn)題描述定義dp[i][j]為X的前i個(gè)字符和Y的前j個(gè)字符的最長(zhǎng)公共子序列長(zhǎng)度。當(dāng)X[i]=Y[j]時(shí)，dp[i][j]=dp[i-1][j-1]+1；否則，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。動(dòng)態(tài)規(guī)劃思路O(NM)，其中N和M分別為字符串X和Y的長(zhǎng)度。時(shí)間復(fù)雜度最長(zhǎng)公共子序列問(wèn)題矩陣鏈乘法問(wèn)題給定一個(gè)矩陣鏈，如何確定乘法運(yùn)算的次序，使得計(jì)算該矩陣鏈所需的最少數(shù)乘次數(shù)最少。問(wèn)題描述O(N^3)，其中N為矩陣鏈中矩陣的數(shù)量。時(shí)間復(fù)雜度實(shí)驗(yàn)代碼與運(yùn)行結(jié)果【此處應(yīng)提供實(shí)驗(yàn)代碼及運(yùn)行結(jié)果截圖或文字描述】06實(shí)驗(yàn)六：貪心算法設(shè)計(jì)與分析活動(dòng)選擇問(wèn)題問(wèn)題描述給定一個(gè)n個(gè)活動(dòng)的集合S，每個(gè)活動(dòng)都有一個(gè)開始時(shí)間和一個(gè)結(jié)束時(shí)間，且被允許的活動(dòng)集合中任意兩個(gè)活動(dòng)不能有時(shí)間上的交集。要求找到最大的相互兼容的活動(dòng)子集。貪心策略每次選擇結(jié)束時(shí)間最早的活動(dòng)，以便為其他活動(dòng)留下盡可能多的時(shí)間。算法實(shí)現(xiàn)首先將所有活動(dòng)按結(jié)束時(shí)間從小到大排序，然后從第一個(gè)活動(dòng)開始依次選擇，如果當(dāng)前活動(dòng)與已選擇的活動(dòng)集合中的活動(dòng)不沖突，則將其加入結(jié)果集合。貨幣找零問(wèn)題首先將硬幣按面值從大到小排序，然后從最大的硬幣開始依次選擇，如果當(dāng)前硬幣的面值小于等于目標(biāo)金額，則將其加入結(jié)果集合，并更新目標(biāo)金額為剩余金額。算法實(shí)現(xiàn)給定一些面額不同的硬幣，以及一個(gè)總金額。要求用最少的硬幣數(shù)量湊出這個(gè)總金額。問(wèn)題描述每次選擇面值最大的硬幣，以便用最少的硬幣數(shù)量達(dá)到目標(biāo)金額。貪心策略給定一個(gè)字符串和它的字符頻率，要求構(gòu)造一個(gè)哈夫曼樹，并生成對(duì)應(yīng)的哈夫曼編碼。每次選擇頻率最小的兩個(gè)節(jié)點(diǎn)合并成一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)的頻率為兩個(gè)子節(jié)點(diǎn)頻率之和。然后將新節(jié)點(diǎn)加入優(yōu)先隊(duì)列，以便后續(xù)繼續(xù)合并。首先將所有字符按頻率從小到大排序，并構(gòu)建對(duì)應(yīng)的節(jié)點(diǎn)和優(yōu)先隊(duì)列。然后不斷從優(yōu)先隊(duì)列中取出頻率最小的兩個(gè)節(jié)點(diǎn)合并成新節(jié)點(diǎn)，并將新節(jié)點(diǎn)加入優(yōu)先隊(duì)列。直到優(yōu)先隊(duì)列中只剩下一個(gè)節(jié)點(diǎn)為止，該節(jié)點(diǎn)即為哈夫曼樹的根節(jié)點(diǎn)。最后根據(jù)哈夫曼樹生成對(duì)應(yīng)的哈夫曼編碼。問(wèn)題描述貪心策略算法實(shí)現(xiàn)哈夫曼編碼問(wèn)題010203活動(dòng)選擇問(wèn)題代碼示例```pythondefactivity_selection(activities)實(shí)驗(yàn)代碼與運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果n=len(activities)result=[activities[0]]#初始化結(jié)果集合k=0#已選擇活動(dòng)的索引實(shí)驗(yàn)代碼與運(yùn)行結(jié)果01foriinrange(1,n)02ifactivities[i][0]>=result[k][1]:#如果當(dāng)前活動(dòng)與已選擇的活動(dòng)不沖突03result.append(activities[i])#將當(dāng)前活動(dòng)加入結(jié)果集合k+=1returnresult實(shí)驗(yàn)代碼與運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果```02貨幣找零問(wèn)題代碼示例03```python01defcoin_change(coins,amount)coins.sort(reverse=True)#按面值從大到小排序result=[]#初始化結(jié)果集合實(shí)驗(yàn)代碼與運(yùn)行結(jié)果forcoinincoinswhileamount>=coin:#如果當(dāng)前硬幣面值小于等于目標(biāo)金額amount-=coin#更新目標(biāo)金額為剩余金額010203實(shí)驗(yàn)代碼與運(yùn)行結(jié)果result.append(coin)#將當(dāng)前硬幣加入結(jié)果集合returnresultifamount==0elseNone#如果目標(biāo)金額為0則返回結(jié)果集合，否則返回None表示無(wú)法湊出目標(biāo)金額實(shí)驗(yàn)代碼與運(yùn)行結(jié)果哈夫曼編碼問(wèn)題代碼示例```python```實(shí)驗(yàn)代碼與運(yùn)行結(jié)果importheapqclassNodedef__init__(self,freq,char=None,left=None,right=None)010203實(shí)驗(yàn)代碼與運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果030201self.freq=freqself.char=charself.left=left實(shí)驗(yàn)代碼與運(yùn)行結(jié)果010203self.right=rightdef__lt__(self,other)returnself.freq<other.freq實(shí)驗(yàn)代碼與運(yùn)行結(jié)果defhuffman_encoding(freqs)heap=[Node(freq,char)forchar,freqinfreqs.items()]#構(gòu)建初始節(jié)點(diǎn)和優(yōu)先隊(duì)列heapq.heapify(heap)#堆化優(yōu)先隊(duì)列實(shí)驗(yàn)代碼與運(yùn)行結(jié)果whilelen(heap)>1:#當(dāng)優(yōu)先隊(duì)列中至少有兩個(gè)節(jié)點(diǎn)時(shí)node1=heapq.heappop(heap)#取出頻率最小的節(jié)點(diǎn)node2=heapq.heappop(heap)#取出頻率次小的節(jié)點(diǎn)merged=Node(node1.freq+node2.freq,left=node1,right=node2)#合并節(jié)點(diǎn)heapq.heappush(heap,merged)#將新節(jié)點(diǎn)加入優(yōu)先隊(duì)列huffman_tree=heap[0]#哈夫曼樹的根節(jié)點(diǎn)實(shí)驗(yàn)代碼與運(yùn)行結(jié)果實(shí)驗(yàn)代碼與運(yùn)行結(jié)果defbuild_codes(node,prefix,codes):#構(gòu)建哈夫曼編碼的遞歸函數(shù)codes={}#哈夫曼編碼字典ifnode.char:#葉節(jié)點(diǎn)，將字符和對(duì)應(yīng)編碼加入字典codes[node.char]=prefixelse:#非葉節(jié)點(diǎn)，遞歸處理左右子樹build_codes(node.left,prefix實(shí)驗(yàn)代碼與運(yùn)行結(jié)果07實(shí)驗(yàn)七：分治算法設(shè)計(jì)與分析算法思想二分搜索算法是一種在有序數(shù)組中查找特