西工大《算法設計與分析B卷》2024年10月作業(yè)考核（答案）一、選擇題1.以下哪種算法復雜度的漸進上界最??？（）A.O(n^2)B.O(nlogn)C.O(2^n)D.O(n)答案：D分析：根據(jù)復雜度大小關系O(n)<O(nlogn)<O(n^2)<O(2^n)，漸進上界最小的是O(n)。2.下列排序算法中，平均時間復雜度為O(nlogn)且是穩(wěn)定排序的是（）A.快速排序B.堆排序C.歸并排序D.希爾排序答案：C分析：快速排序平均時間復雜度是O(nlogn)，但不穩(wěn)定；堆排序平均時間復雜度O(nlogn)，不穩(wěn)定；希爾排序平均時間復雜度介于O(n)-O(n^2)，不穩(wěn)定；歸并排序平均時間復雜度O(nlogn)且穩(wěn)定。二、填空題1.分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相______，并且與原問題______。答案：獨立；相同分析：分治法就是把大問題分解成多個相互獨立且與原問題性質(zhì)相同的小問題，分別求解小問題后合并得到原問題的解。2.動態(tài)規(guī)劃算法的兩個基本要素是______和______。答案：最優(yōu)子結構；子問題重疊分析：最優(yōu)子結構保證問題的最優(yōu)解包含子問題的最優(yōu)解，子問題重疊使得我們可以通過保存子問題的解避免重復計算。三、簡答題1.簡述貪心算法和動態(tài)規(guī)劃算法的區(qū)別。答案：貪心算法在每一步都做出當前看來最優(yōu)的選擇，即局部最優(yōu)，且不考慮子問題的解對后續(xù)選擇的影響，它通常不能保證得到全局最優(yōu)解。而動態(tài)規(guī)劃算法會考慮所有子問題的解，通過保存子問題的解避免重復計算，利用問題的最優(yōu)子結構性質(zhì)，從子問題的最優(yōu)解推導出原問題的最優(yōu)解，能保證得到全局最優(yōu)解。分析：貪心算法只關注眼前利益，不回溯；動態(tài)規(guī)劃則全面考慮子問題之間的關聯(lián)。2.分析冒泡排序算法的時間復雜度和空間復雜度。答案：時間復雜度：最好情況下，數(shù)組已經(jīng)有序，只需遍歷一次，時間復雜度為O(n)；最壞和平均情況下，需要進行n-1趟排序，每趟比較次數(shù)逐漸減少，總的比較次數(shù)約為n(n-1)/2，時間復雜度為O(n^2)。空間復雜度：冒泡排序只需要常數(shù)級的額外空間，用于交換元素，空間復雜度為O(1)。分析：時間復雜度取決于數(shù)組的初始狀態(tài)，空間復雜度主要看額外使用的存儲空間。四、算法設計題1.設計一個算法，實現(xiàn)對一個整數(shù)數(shù)組的快速排序。```pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[0]left=[]right=[]fornuminarr[1:]:ifnum<=pivot:left.append(num)else:right.append(num)returnquick_sort(left)+[pivot]+quick_sort(right)```分析：快速排序采用分治法，選擇一個基準元素，將數(shù)組分為兩部分，小于基準的元素放在左邊，大于基準的元素放在右邊，然后遞歸地對左右兩部分進行排序。2.設計一個動態(tài)規(guī)劃算法，計算斐波那契數(shù)列的第n項。```pythondeffibonacci(n):ifn==0:return0ifn==1:return1dp=[0](n+1)dp[0]=0dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]