【正文】 =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}=9Bcost(5,8)=min{c(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)}=min{7+9,3+9}=12 向前遞推過程如下： 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, cost(3,4)=min{6+cost(4,6),2+cost(4,7)}=5cost(3,5)=min{6+cost(4,6),2+cost(4,7)}=5cost(2,1)=min{3+cost(3,3),3+cost(3,5)}=8cost(2,2)=min{6+cost(3,3),8+cost(3,5),5+cost(3,4)}=10cost(1,0)=min{5+cost(2,1),2+cost(2,2)}=12所以，d(4,6)=d(4,7)=8, d(3,3)=d(3,4)=d(3,5)=7, d(2,1)=5, d(2,2)=4, d(1,0)=2從s到t的最短路徑為 (0, d(1,0)=2, d(2,2)=4, d(3,4)=7, d(4,7)=8),路徑長為12。 r++。 else {t=mid。（2）最壞情況發(fā)生在序列按遞減次序排列。所以，算法的最好、最壞情況的時間復雜度為。第二章217. 證明：設(shè)，則 。（4）當n為奇數(shù)時畫線語句的執(zhí)行次數(shù)為 ，當n為偶數(shù)時畫線語句的執(zhí)行次數(shù)為 。 210.（1） 當 時，所以，可選 。 當 時。假定查找表中任何一個元素的概率是相等的，為，那么，不成功搜索的平均時間復雜度為，成功搜索的平均時間復雜度為。 break。 } left=t。第七章9. char A[8]={‘0’,’x’,’z’,’y’,’z