算法設(shè)計(jì)與分析-課后習(xí)題集答案(編輯修改稿)
2025-02-05 09:30 本頁面
【文章內(nèi)容簡介】 log3log3 13 n ??? log3log3 1n ????????? 冒泡排序最壞時(shí)間復(fù)雜度為 ? ?2n? ，隊(duì)排序最壞時(shí)間復(fù)雜度為 ? ?lognn? ，快速排序最壞時(shí)間復(fù)雜度為? ?lognn? 。所以，該算法不如冒泡排序，堆排序，快速排序。 13. template class T select (Tamp。x,int k) { if(mn) swap(m,n)。 if(m+nk||k=0) {coutOut Of Bounds。 return false。} int *p=new temp[k]。 int mid,left=0,right=n1,t=0,j=0,r=0。 for(int i=0。im。i++) { while(k0) { do { mid=(left+right)/2。 if(a[mid]b[i]) left=mid。 else if(a[mid]b[i]) right=mid。 else {t=mid。 break。} }while(leftright1) if(a[left]b[i]) t=left。 else t=left1。 if(kt) { if(t0) { for(j=0。jt。j++) { temp[j]=a[r]。 r++。 } left=t。 k=t。 } else { temp[j]=b[i]。 left=0。 k。 } } else { for(j=0。jk。j++) { temp[j]=a[r]。 r++。 } left=t。 k=t。 return temp[k1]。 } } } } 第六章 ： 0 1 2 3 4 5 60 1 2 3 4 5 61 0 5 1 5 7 6 1 8 3, , , , , , , , , , , ,2 3 5 7 1 4 1p p p p p p pw w w w w w w?? ????? ??????， 所以，最優(yōu)解為 ? ?0 1 2 3 4 5 6 2, , , , , , , 1 , , 1 , 0 , 1 , 1 , 13x x x x x x x ??? ????， 最大收益為 211 0 5 1 5 6 1 8 3 5 533? ? ? ? ? ? ?。 8. (n1)%(K1)=(111)%(31)=0, 故無需補(bǔ)充虛游程。 9 普里姆算法。 因?yàn)閳D G 是一個(gè)無向連通圖。 所以 n1=m=n (n1)/2。 O(n)=m=O(n2)。 克魯斯卡爾對邊數(shù)較少的帶權(quán)圖有較高的效率，而 ? ? ? ?1 .9 9 2m n n? ? ? ?，此圖邊數(shù)較多，接近完全圖，故選用普里姆算法。 10. T 仍是新圖的最小代價(jià)生成樹。 證明：假設(shè) T 不是新圖的最小代價(jià)生成樹， T’是新圖的最小代價(jià)生成樹，那么 cost(T’)cost(T)。有cost(T’)c(n1)cost(t)c(n1)，即在原圖中存在一顆生成樹，其代價(jià)小于 T 的代價(jià)，這與題設(shè)中 T 是原圖的最小代價(jià)生成樹矛盾。所以假設(shè)不成立。證畢。 第七章 1. Bcost(1,0)=0。 Bcost(2,1)=c(1,1)+Bcost()=5 Bcost(2,2)=c(1,2)+Bcost(1,0)=2 Bcost(3,3)=min{c(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)}=min{6+2,3+5}=8 Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7 Bcost(3,5)=min{c(1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)}=min{3+5,8+2}=8 Bcost(4,6)=min{c(3,6)+Bcost(3,3),c(4,6)+Bcost(3,4),c(5,6)+Bcost(3,5)}=min{1+8,6+7,6+8}=9 Bcost(4,7)=min{c(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)}=min{4+8,2+7,6+8}=9 Bcost(5,8)=min{c(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)}=min{7+9,3+9}=12 （ 0， 2， 4， 7， 8） 向前遞推過程如下： cost(5,8)=0 cost(4,6)=7,cost(4,7)=3 cost(3,3)=min{1+cost(4,6),4+cost(4,7)}=7,
試題試卷相關(guān)推薦
鄂ICP備17016276號-1