參***
第1章演算法分析基本概念
1.1(a)6 (b)5 (c)6 (d)6
1.4演算法執行了7+6+5+4+3+2+1=28次比較
1.5(a)演算法modselectionsort執行的元素賦值的最少次數是0,元素已按非降序排列的時候達到最小值。
(b) 演算法modselectionsort執行的元素賦值的最多次數是,元素已按非公升序排列的時候達到最小值。
1.7由上圖可以看到執行的比較次數為1+1+2+2+2+6+2=16次。
1.11
由上圖可以得出比較次數為5+6+6+9=26次。
1.13
ftf,ttt,ftf,tff,ftf
1.16
(a) 執行該演算法，元素比較的最少次數是n-1。元素已按非降序排列時候達到最小值。
(b) 執行該演算法，元素比較的最多次數是。元素已按非公升序排列時候達到最大值。
(c) 執行該演算法，元素賦值的最少次數是0。元素已按非降序排列時候達到最小值。
(d) 執行該演算法，元素賦值的最多次數是。元素已按非公升序排列時候達到最大值。
(e)用o符號和符號表示演算法bubblesort的執行時間：，
(f)不可以用符號來表示演算法的執行時間：是用來表示演算法的精確階的，而本演算法執行時間由線性到平方排列，因此不能用這一符號表示。
1.27
不能用關係來比較和增長的階。
∵不是的，即不能用關係來比較和增長的階。
1.32
(a)當n為2的冪時，第六步執行的最大次數是：
時，(b)由(a)可以得到：當每一次迴圈j都為2的冪時，第六步執行的次數最大，
則當（其中取整）時，
(c)用符號表示的演算法的時間複雜性是
已證明n=2k的情況，下面證明n=2k+1的情況：
因為有所以n=2k+1時，第六步執行的最大次數仍是n log n。
(d) 用符號表示的演算法的時間複雜性是。
當滿足取整為奇數時，演算法執行的次數是次，其他情況演算法執行次數均大於。
(e) o更適合表示演算法的時間複雜性。因為本演算法時間複雜性從到，而是表示精確階的。
1.38
對個數進行排序。
第5章歸納法
5.3（本題不僅有以下乙個答案）
1.max(n
過程：max(i)
if n=1 return a[1]
t=max(i-1)
if a[i-1]>t return a[i-1]
else return t
end if
5.6最多次數：
最少次數：
c(n)=n-1
5.7參考例5.1
5.14
(a)不穩定，例如：
可見selectionsort中相等元素的序在排序後改變。
(b)(c)(d)(f)穩定
5.17
(a)利用
取，5.18
(a)第6章分治
6.3輸入：a[1,2,…n]
輸出：max,min
1.for i=1 to mid
2. j=high-i
3. if a[i]>a[j], then exchange a[i],a[j]
4.end for
5.for i=low to mid
6. if a[i+1]7.end for
8.for i=mid+1 to high
9. if a[i+1]>a[high], then exchange a[high],a[i+1]
10.end for
6.5輸入：乙個整數陣列a[1,2,…,n]
輸出：sum
1.if high-low=1 then
2. sum=a[low]+a[high]
3.else
4. mid=(low+high)/2
5 sum1=sum(low,mid)
6 sum2=sum(mid+1,high)
7. sum=sum1+sum2
8.end if
9.return sum
演算法需要的工作空間為3
6.10.
6.31
彩色代表i,j所指的數字j總在i前
6.36
6.42
quicksort不是穩定的。
6.43
bcefg均為適應的，a、h不是適應的。
第7章動態規劃
7.1(c),演算法bottomupsort
7.5字串a=」xzyzzyx」和b=」zxyyzxz」的最長公共子串行長度為4，共有6個最長公共子串行，分別是：①zyyx ②zyzz ③zyzx ④xyyx ⑤xyzz ⑥xyzx
7.9c[1,5]=c[1,1]+c[2,5]+r[1]*r[2]*r[6]=307
c[1,5]=c[1,2]+c[3,5]+r[1]*r[3]*r[6]=252
c[1,5]=c[1,3]+c[4,5]+r[1]*r[4]*r[6]=372
c[1,5]=c[1,4]+c[5,5]+r[1]*r[5]*r[6]=260
所以最優括號表示式為（m1m2）((m3m4)m5)
7.15
7.21
7.23
當物品體積為負值時，執行演算法會發生溢位錯誤。
第八章貪心演算法
8.12
由演算法從s到t要選擇先到a然後到t,其結果為4，而從s到t距離為2，所以探索不總是產生從s到t的距離
8.13
8.23（共有4棵最小生成樹，此處僅舉一例）
8.24（共有4棵最小生成樹，此處僅舉一例）
8.31
每乙個二叉樹都取左邊為0，右邊為1
則最優編碼為a:10 b:001 c:0001
d:0000 e:01 f:11
注意：編碼不唯一回溯法
演算法設計與分析 1
湖南中醫藥大學 2009 2010 學年第一學期 演算法設計與分析 期末考試試卷 班級姓名學號 一 選擇題 10題 2分 20分 1.我們常用演算法的最壞時間來估計演算法的時間複雜性，下面 不是這樣做的原因 a 在實際問題中，演算法的執行時間常常達到這個上界。b 平均執行時間難以計算。c 假設每乙個...
分析演算法技巧
一 平方數速算 牢記常用平方數，特別是11 30以內數的平方，可以很好地提高計算速度 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 二 錯位相加 減 a 9型速算技巧 a 9 a 10 ...
演算法設計與分析期末試題
總題一 記得哪些演算法複雜性的知識？用自己的話簡述。例如最壞時間複雜性 複雜性漸進性態的階 二 演算法的時間複雜性分析 1 如何根據演算法的結構分析演算法的時間複雜性？例如選擇基本運算步驟 依據演算法的結構統計。2 分析遞迴演算法的方法，歸方程方法和遞迴樹。姐遞迴方程有迭代法 遞推 法解遞迴方程，或...