算法設(shè)計(jì)與分析A8卷

第=page1*2-11頁，共=sectionpages4*28頁第=page1*22頁，共=sectionpages4*28頁南陽理工學(xué)院試卷課程：《算法設(shè)計(jì)與分析》考核方式：（閉卷）課程性質(zhì)：_專業(yè)平臺必修課_適用對象：題號一二三四五六七總分復(fù)核人滿分得分一、填空題：（每空2分，共20分）評卷人得分1．Kruskal算法求最小生成樹的過程中，貪心策略是，否則繼續(xù)選擇下一條最短邊。給定n條邊的無向連通圖，該算法的時(shí)間復(fù)雜度為。2．用分治法設(shè)計(jì)的快速排序算法描述如下，其中R[low:high]存放的待排序序列，請?zhí)顚懣杖辈糠值恼Z句。void

QuickSort(int

R[]，int

low，int

high)

{

int

pivotpos；//記錄基準(zhǔn)元素所在位置

{

pivotpos=Partition(R,low,high)；

；

QuickSort(R,pivotpos+1,high)；

}

}

3．給定n個(gè)城市的交通圖，住地城市為1號城市，旅行售貨員問題的算法描述如下，其中t為當(dāng)前擴(kuò)展結(jié)點(diǎn)所處的層次，g為鄰接矩陣，x記錄當(dāng)前解，bestx記錄當(dāng)前最優(yōu)解，cl記錄當(dāng)前已經(jīng)走的路徑長度，請?zhí)顚懣杖辈糠值恼Z句。voidTraveling(intt){if(t>n)if(g[x[n]][1]!=&&(cl+g[x[n]][1]<bestl)){for(j=1;j<=n;j++)bestx[j]=x[j];bestl=cl+g[x[n]][1];}elsefor(j=t;j<=n;j++)if(g[x[t-1]][x[j]]!=&&(cl+g[x[t-1]][x[j]]<bestl)){swap(x[t],x[j]);//交換兩個(gè)元素的值；Traveling(t+1);cl-=g[x[t-1]][x[j]];;}}4．動(dòng)態(tài)規(guī)劃的基本要素有、、自底向上的求解方法。5．給定n個(gè)頂點(diǎn)的無向圖和m種顏色，圖的m可著色問題的解空間樹是樹，該問題回溯法的時(shí)間復(fù)雜度為二、選擇題：（每題2分，共20分）（說明：將認(rèn)為正確答案的字母填寫在每小題的括號內(nèi)）評卷人得分1．算法必須滿足的特性除了有能行性和確定性外，還有（）。A．輸出B．有限性C．輸入D．無限性2．最長公共子序列問題中，給定兩個(gè)序列X={A,B,C,B,D,A,B}和Y={A,C,B,E,D,B}，這兩個(gè)序列的最長公共子序的長度為（）。A．3B．6C．5D．43．背包問題：給定n=4，W=7，w=(3,5,2,1)，p=(9,10,7,4)，該問題的最大價(jià)值是（）。A．19B．20C．21D．224．分支限界法與回溯法的不同主要表現(xiàn)在（）。A．搜索目標(biāo)B．搜索方式C．搜索開始D．?dāng)U展方式5．影響算法時(shí)間復(fù)雜度的主要因素除算法本身外，以下說法不正確的是（）。A．算法的時(shí)間復(fù)雜度一定與輸入序列有關(guān)B．算法的時(shí)間復(fù)雜度一定不與輸入序列有關(guān)C．算法的時(shí)間復(fù)雜度不一定與輸入序列有關(guān)D．算法的時(shí)間復(fù)雜度一般與問題的規(guī)模有關(guān)6．某算法的時(shí)間復(fù)雜度表達(dá)式為T(n)=30n4+20n3+40n2+46n+100，該算法的時(shí)間復(fù)雜度可以用下列哪個(gè)漸進(jìn)意義下的符號表示。（）A．OB．C．D．以上符號都不能用來表示7．有關(guān)Prim算法和Kruskal算法的描述說法正確的是（）A．Prim算法的時(shí)間復(fù)雜度為（nlogn），其中n為無向連通圖的頂點(diǎn)數(shù)B．對稠密圖，Kruskal算法比Prim算法有效C．對稀疏圖，Kruskal算法比Prim算法有效D．對稠密圖，Kruskal算法不如Prim算法有效8．給定一個(gè)網(wǎng)絡(luò)G=（V,E），假設(shè)s為源點(diǎn)，其標(biāo)號為（0，+∞）。從已標(biāo)號而未檢查的點(diǎn)v出發(fā)，對于邊<w,v>，如果（），則可以對w進(jìn)行標(biāo)號。A．flow(v，w)cap(v，w)B．flow(v，w)>0C．flow(v，w)<cap(v，w)D．flow(v，w)09．分治法中，將規(guī)模大的問題分解為多個(gè)規(guī)模較小的子問題，子問題必須滿足的條件是（）。A．一般不相互獨(dú)立B．相互獨(dú)立C．與原問題相同D．以上都不對10．二分查找的時(shí)間復(fù)雜度為（）。A．O(nlogn)B．O(n)C．O(logn)D．以上都不對三、簡答題：（每題5分，共20分）評卷人得分1．簡述哈夫曼編碼算法的思想。2．簡述合并排序算法的思想。3．簡述動(dòng)態(tài)規(guī)劃算法的求解步驟。4．簡述回溯法的搜索思想。四、求解題：（每題10分，共30分）評卷人得分1．用動(dòng)態(tài)規(guī)劃中的跳躍點(diǎn)算法求解如下問題：有5個(gè)物品，其重量分別為2,2,6,5,4，價(jià)值分別為6,3,5,4,6。背包容量為10，物品不可分割，求裝入背包的物品和獲得的最大價(jià)值。（要求：先寫出求解公式，然后寫出求解過程，最后給出最優(yōu)解和最優(yōu)值）2．用分支限界法解4皇后問題（要求：指明搜索范圍，解空間結(jié)構(gòu)，搜索時(shí)用的剪枝函數(shù)，并畫出搜索樹）3．給定下圖所示的網(wǎng)絡(luò)G=（V，E）及網(wǎng)絡(luò)可行