目錄

簡答題

計算題

時間復(fù)雜度的計算

遞歸算法計算

背包問題（0-1背包問題）

回溯法

動態(tài)規(guī)劃法

編程題

用回溯法解方程

動態(tài)規(guī)劃法解決蜘蛛吃蚊子

用分治法解決拋硬幣問題

用二分法分兩邊求最大值

---

簡答題

1、什么是算法？算法有哪些特征？

算法是求解問題的一系列計算步驟。算法具有有限性、確定性、可行性、輸入性和輸出性。

2、什么是直接遞歸和間接遞歸？消除遞歸一般要用什么數(shù)據(jù)結(jié)構(gòu)？

直接遞歸：一個 f 函數(shù)定義中直接調(diào)用 f 函數(shù)自己。

間接遞歸：一個 f 函數(shù)定義中調(diào)用 g 函數(shù)，而 g 函數(shù)的定義中調(diào)用 f 函數(shù)。消除遞歸一般要用棧實現(xiàn)。

3、分治法的設(shè)計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題：

問題規(guī)模不同，問題性質(zhì)相同。

4、在尋找 n 個元素中第 k 小元素問題中，如快速排序算法思想，運用分治算法對 n個元素進行劃分，如何選擇劃分基準？

隨機選擇一個元素作為劃分基準、取子序列的第一個元素作為劃分基準、用中位數(shù)的中位數(shù)方法尋找劃分基準。

5、快速排序算法是根據(jù)分治策略來設(shè)計的，簡述其基本思想。

對于無序序列 a[low..high]進行快速排序，整個排序為“大問題”。選擇其中的一個基準 base=a[i]（通常以序列中第一個元素為基準），將所有小于等于 base 的元素移動到它的前面，所有大于等于 base 的元素移動到它的后面，即將基準歸位到 a[i]，這樣產(chǎn)生a[low..i-1]和 a[i+1..high]兩個無序序列，它們的排序為“小問題”。當(dāng) a[low..high]序列只有一個元素或者為空時對應(yīng)遞歸出口。

所以快速排序算法就是采用分治策略，將一個“大問題”分解為兩個“小問題”來求解。由于元素都是在 a 數(shù)組中，其合并過程是自然產(chǎn)生的，不需要特別設(shè)計。

6、假設(shè)含有 n 個元素的待排序的數(shù)據(jù) a 恰好是遞減排列的，說明調(diào)用 QuickSort(a，0，n-1)遞增排序的時間復(fù)雜度為 O()。

此時快速排序?qū)?yīng)的遞歸樹高度為 O(n)，每一次劃分對應(yīng)的時間為 O(n)，以整個排序時間為 O()。

7、哪些算法采用分治策略。

其中二路歸并排序和折半查找算法采用分治策略。

8、適合并行計算的問題通常表現(xiàn)出哪些特征？

1）將工作分離成離散部分，有助于同時解決。例如，對于分治法設(shè)計的串行算法，可以將各個獨立的子問題并行求解，最后合并成整個問題的解，從而轉(zhuǎn)化為并行算法。
2）隨時并及時地執(zhí)行多個程序指令。
3）多計算資源下解決問題的耗時要少于單個計算資源下的耗時。

9、設(shè)有兩個復(fù)數(shù) x=a+bi 和 y=c+di。復(fù)數(shù)乘積 xy 可以使用 4 次乘法來完成，即xy=(ac-bd)+(ad+bc)i。設(shè)計一個僅用 3 次乘法來計算乘積 xy 的方法。

xy=(ac-bd)+((a+b)(c+d)-ac-bd)i。由此可見，這樣計算 xy 只需要 3 次乘法（即ac、bd 和(a+b)(c+d)乘法運算）。

10、?有 4 個數(shù)組 a、b、c 和 d，都已經(jīng)排好序，說明找出這 4 個數(shù)組的交集的方法。

采用基本的二路歸并思路，先求出 a、b 的交集 ab，再求出 c、d 的交集 cd，最后求出 ab 和 cd 的交集，即為最后的結(jié)果。也可以直接采用 4 路歸并方法求解。

11、簡要比較蠻力法和分治法。

蠻力法是一種簡單直接地解決問題的方法，適用范圍廣，是能解決幾乎所有問題的一般性方法，常用于一些非?；?、但又十分重要的算法（排序、查找、矩陣乘法和字符串匹配等），蠻力法主要解決一些規(guī)模小或價值低的問題，可以作為同樣問題的更高效算法的一個標準。而分治法采用分而治之思路，把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到問題解決。分治法在求解問題時，通常性能比蠻力法好。

12、在采用蠻力法求解時什么情況下使用遞歸？

如果用蠻力法求解的問題可以分解為若干個規(guī)模較小的相似子問題，此時可以采用遞歸來實現(xiàn)算法

13、回溯法在問題的解空間樹中，按什么策略，從根結(jié)點出發(fā)搜索解空間樹？

深度優(yōu)先

14、對于回溯法說法錯誤的是

回溯算法需要借助隊列這種結(jié)構(gòu)來保存從根結(jié)點到當(dāng)前擴展結(jié)點的路徑

15、回溯法的效率依賴于哪些因素？

滿足顯約束的值的個數(shù)、計算約束函數(shù)的時間、計算限界函數(shù)的時間

16、什么函數(shù)是回溯法中為避免無效搜索采取的策略？

剪枝函數(shù)

17、回溯法的搜索特點是什么？

回溯法在解空間樹中采用深度優(yōu)先遍歷方式進行解搜索，即用約束條件和限界函數(shù)考察解向量元素 x[i]的取值，如果 x[i]是合理的就搜索 x[i]為根結(jié)點的子樹，如果x[i]取完了所有的值，便回溯到 x[i-1]。

18、用回溯法解 0/1 背包問題時，該問題的解空間是何種結(jié)構(gòu)？用回溯法解流水作業(yè)調(diào)
度問題時，該問題的解空間是何種結(jié)構(gòu)？

用回溯法解 0/1 背包問題時，該問題的解空間是子集樹結(jié)構(gòu)。用回溯法解流水作業(yè)調(diào)度問題時，該問題的解空間是排列樹結(jié)構(gòu)。

19、對于遞增序列 a[]={1，2，3，4，5}，采用回溯法求全排列，以 1、2 開頭的排列一定最先出現(xiàn)嗎？為什么？

是的。對應(yīng)的解空間是一棵排列樹，如圖所示給出前面 3 層部分，顯然最先產(chǎn)生的排列是從 G 結(jié)點擴展出來的葉子結(jié)點，它們就是以 1、2 開頭的排列。

?20、考慮 n 皇后問題，其解空間樹為由 1、2、…、n 構(gòu)成的 n!種排列所組成?，F(xiàn)用回溯法求解，如下：

（1）通過解搜索空間說明 n=3 時是無解的。

n=3 時的解搜索空間如圖所示，不能得到任何葉子結(jié)點，所有無解。

（2）給出剪枝操作。

剪枝操作是任何兩個皇后不能同行、同列和同兩條對角線。

（3）最壞情況下在解空間樹上會生成多少個結(jié)點？分析算法的時間復(fù)雜度。

最壞情況下每個結(jié)點擴展 n 個結(jié)點，共有個結(jié)點，算法的時間復(fù)雜度為O()

21、分枝限界法在問題的解空間樹中，按什么策略，從根結(jié)點出發(fā)搜索解空間樹。

廣度優(yōu)先

22、常見的兩種分枝限界法為：

隊列式（FIFO）分枝限界法與優(yōu)先隊列式分枝限界法。

23、分枝限界法求解 0/1 背包問題時，活結(jié)點表的組織形式是

大根堆

24、采用最大效益優(yōu)先搜索方式的算法是

分枝限界法

25、優(yōu)先隊列式分枝限界法選取擴展結(jié)點的原則是

結(jié)點的優(yōu)先級

26、簡述分枝限界法的搜索策略。

分枝限界法的搜索策略是廣度優(yōu)先遍歷，通過限界函數(shù)可以快速找到一個解或者最優(yōu)解。

27、有一個 0/1 背包問題，其中 n=4，物品重量為（4，7，5，3），物品價值為（40，42，25，12），背包最大載重量 W=10，給出采用優(yōu)先隊列式分枝限界法求最優(yōu)解的過程。

求解過程如下：
1）根結(jié)點 1 進隊，對應(yīng)結(jié)點值：e.i=0，e.w=0，e.v=0，e.ub=76，x:[0，0，0，0]。
2）出隊結(jié)點 1：左孩子結(jié)點 2 進隊，對應(yīng)結(jié)點值：e.no=2，e.i=1，e.w=4，e.v=40，e.ub=76，x:[1，0，0，0]；右孩子結(jié)點 3 進隊，對應(yīng)結(jié)點值：e.no=3，e.i=1，
e.w=0，e.v=0，e.ub=57，x:[0，0，0，0]。
3）出隊結(jié)點 2：左孩子超重；右孩子結(jié)點 4 進隊，對應(yīng)結(jié)點值：e.no=4，e.i=2，e.w=4，e.v=40，e.ub=69，x:[1，0，0，0]。
4）出隊結(jié)點 4：左孩子結(jié)點 5 進隊，對應(yīng)結(jié)點值：e.no=5，e.i=3，e.w=9，e.v=65，e.ub=69，x:[1，0，1，0]；右孩子結(jié)點 6 進隊，對應(yīng)結(jié)點值：e.no=6，e.i=3，e.w=4，e.v=40，e.ub=52，x:[1，0，0，0]。
5）出隊結(jié)點 5：產(chǎn)生一個解，maxv= 65，bestx:[1，0，1，0]。
6）出隊結(jié)點 3：左孩子結(jié)點 8 進隊，對應(yīng)結(jié)點值：e.no=8，e.i=2，e.w=7，e.v=42，e.ub=57，x:[0，1，0，0]；右孩子結(jié)點 9 被剪枝。
7）出隊結(jié)點 8：左孩子超重；右孩子結(jié)點 10 被剪枝。
8）出隊結(jié)點 6：左孩子結(jié)點 11 超重；右孩子結(jié)點 12 被剪枝。
9）隊列空，算法結(jié)束，產(chǎn)生的最優(yōu)解：maxv= 65，bestx:[1，0，1，0]。

28、有一個流水作業(yè)調(diào)度問題，n=4，a[]={5，10，9，7}，b[]={7，5，9，8}，給出采用優(yōu)先隊列式分枝限界法求一個解的過程。

求解過程如下：
1）根結(jié)點 1 進隊，對應(yīng)結(jié)點值：e.i=0，e.f1=0，e.f2=0，e.lb=29， x：[0，0，0，0]。
2）出隊結(jié)點 1：擴展結(jié)點如下：
進隊（j=1）：結(jié)點 2，e.i=1，e.f1=5，e.f2=12，e.lb=27，x：[1，0，0，0]。
進隊（j=2）：結(jié)點 3，e.i=1，e.f1=10，e.f2=15，e.lb=34，x：[2，0，0，0]。
進隊（j=3）：結(jié)點 4，e.i=1，e.f1=9，e.f2=18，e.lb=29，x：[3，0，0，0]。
進隊（j=4）：結(jié)點 5，e.i=1，e.f1=7，e.f2=15，e.lb=28，x：[4，0，0，0]。
3）出隊結(jié)點 2：擴展結(jié)點如下：
進隊（j=2）：結(jié)點 6，e.i=2，e.f1=15，e.f2=20，e.lb=32，x：[1，2，0，0]。
進隊（j=3）：結(jié)點 7，e.i=2，e.f1=14，e.f2=23，e.lb=27，x：[1，3，0，0]。
進隊（j=4）：結(jié)點 8，e.i=2，e.f1=12，e.f2=20，e.lb=26，x：[1，4，0，0]。
4）出隊結(jié)點 8：擴展結(jié)點如下：
進隊（j=2）：結(jié)點 9，e.i=3，e.f1=22，e.f2=27，e.lb=31，x：[1，4，2，0]。
進隊（j=3）：結(jié)點 10，e.i=3，e.f1=21，e.f2=30，e.lb=26，x：[1，4，3，0]。
5）出隊結(jié)點 10，擴展一個 j=2 的子結(jié)點，有 e.i=4，到達葉子結(jié)點，產(chǎn)生的一個解
是 e.f1=31，e.f2=36，e.lb=31，x=[1，4，3，2]。
該解對應(yīng)的調(diào)度方案是：第 1 步執(zhí)行作業(yè) 1，第 2 步執(zhí)行作業(yè) 4，第 3 步執(zhí)行作業(yè)
3，第 4 步執(zhí)行作業(yè) 2，總時間=36。

29、貪心算法的基本要素的是

貪心選擇性質(zhì)

30、什么問題不能使用貪心法解決。

n 皇后問題

31、采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復(fù)雜度為

O(nlog2n)

32、關(guān)于 0/ 1 背包問題

對于同一背包與相同的物品，做背包問題取得的總價值一定大于等于做 0/1 背包問題。

33、一棵哈夫曼樹共有 215 個結(jié)點，對其進行哈夫曼編碼，共能得到（ ）個不同的碼字。

108

34、求解哈夫曼編碼中如何體現(xiàn)貪心思路？

在構(gòu)造哈夫曼樹時每次都是將兩棵根結(jié)點最小的樹合并，從而體現(xiàn)貪心的思路。

35、舉反例證明 0/1 背包問題若使用的算法是按照 vi/wi的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進就裝入背包，則此方法不一定能得到最優(yōu)解（此題說明 0/1 背包問題與背包問題的不同）。

例如，n=3，w={3，2，2}，v={7，4，4}，W=4 時，由于 7/3 最大，若按題目要求的方法，只能取第一個，收益是 7。而此實例的最大的收益應(yīng)該是 8，取第 2、3個物品。

36、通常以自底向上的方式求解最優(yōu)解的是

動態(tài)規(guī)劃法

37、備忘錄方法是什么算法的變形。

動態(tài)規(guī)劃法

38、動態(tài)規(guī)劃算法基本要素的是。

子問題重疊性質(zhì)

39、一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的：

最優(yōu)子結(jié)構(gòu)性質(zhì)

40、簡述動態(tài)規(guī)劃法的基本思路。

動態(tài)規(guī)劃法的基本思路是將待求解問題分解成若干個子問題，先求子問題的解，然后從這些子問題的解得到原問題的解。

41、簡述動態(tài)規(guī)劃法與貪心法的異同。

動態(tài)規(guī)劃法的 3 個基本要素是最優(yōu)子結(jié)構(gòu)性質(zhì)、無后效性和重疊子問題性質(zhì)，而貪心法的兩個基本要素是貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。所以兩者的共同點是都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
兩者的不同點如下：
（1）求解方式不同，動態(tài)規(guī)劃法是自底向上的，有些具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問題只能用動態(tài)規(guī)劃法，有些可用貪心法。而貪心法是自頂向下的。
（2）對子問題的依賴不同，動態(tài)規(guī)劃法依賴于各子問題的解，所以應(yīng)使各子問題最優(yōu)，才能保證整體最優(yōu)；而貪心法依賴于過去所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解。

42、簡述動態(tài)規(guī)劃法與分治法的異同。

兩者的共同點：

是將待求解的問題分解成若干子問題，先求解子問題，然后再從這些子問題的解得到原問題的解。

兩者的不同點是：

適合于用動態(tài)規(guī)劃法求解的問題，分解得到的各子問題往往不是相互獨立的（重疊子問題性質(zhì)），而分治法中子問題相互獨立；另外動態(tài)規(guī)劃法用表保存已求解過的子問題的解，再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間復(fù)雜度，效率較高，而分治法中對于每次出現(xiàn)的子問題均求解，導(dǎo)致同樣的子問題被反復(fù)求解，故產(chǎn)生指數(shù)增長的時間復(fù)雜度，效率較低

43、哪些屬于動態(tài)規(guī)劃算法？

判斷算法是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)、無后效性和重疊子問題性質(zhì)。直接插入排序算法、簡單選擇排序算法 和 二路歸并排序算法 均屬于動態(tài)規(guī)劃算法。

計算題

時間復(fù)雜度的計算

一、

二、

三、

遞歸算法計算

一、

二、

三、

四、

五、

六、

背包問題（0-1背包問題）

回溯法

動態(tài)規(guī)劃法

編程題

用回溯法解方程

#include<iostream>
using namespace std;int a[6] = { 0 };
int solution(int b[], int m, int n)
{if (m == n){if (b[0] * b[1] - b[2] * b[3] - b[4] == 1){printf("解為a=%d b=%d c=%d d=%d e=%d\n", b[0], b[1], b[2], b[3], b[4]);}return 0;}for (int i = 1; i <= n; i++){if (a[i] == 0){a[i] = 1;b[m] = i;solution(b, m + 1, n);a[i] = 0;}}
}
int main()
{int c[6];solution(c, 0, 5);return 0;
}

動態(tài)規(guī)劃法解決蜘蛛吃蚊子

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>int main(int argc, char** argv)
{int n = 5, i, j;if (argc == 2)	n = std::stoi(argv[1]);std::vector<std::vector<int> >  dp(n, std::vector<int>(n, 1));for (i = 1; i < n; ++i)for (j = 1; j < n; ++j){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}std::cout << "total path for " << n << "x" << n << " grid: " << dp[n - 1][n - 1] << std::endl;return 0;
}

用分治法解決拋硬幣問題

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <numeric>
#include <time.h> int solve(std::vector<int>& a, int low, int high);int main(int argc, char** argv)
{int n = 100, m, ans;if (argc == 2)	n = std::stoi(argv[1]);std::vector<int> a(n, 2);srand((unsigned)time(NULL));m = rand() % n;	std::cout << "m: " << m << std::endl;a[m] = 1;std::cout << "solving ..." << std::endl;ans = solve(a, 0, n - 1);std::cout << "coin " << ans << " is fake" << std::endl;return 0;
}int solve(std::vector<int>& a, int low, int high)
{int sum1, sum2, mid, ret_val;if (low == high)		return low;		// 只有一個硬幣if (low == high - 1)					// 只有兩個硬幣{std::cout << "  weighing coin " << low << " and " << high << std::endl;if (a[low] < a[high])	ret_val = low;else					ret_val = high;std::cout << "    --> coin " << ret_val << " is lighter" << std::endl;return ret_val;}mid = (low + high) / 2;if ((high - low + 1) % 2 == 0)				// 硬幣數(shù)量為偶數(shù){sum1 = std::accumulate(a.begin() + low, a.begin() + mid + 1, 0);sum2 = std::accumulate(a.begin() + mid + 1, a.begin() + high + 1, 0);std::cout << "  weighing coin " << low << "-" << mid << " and " << mid + 1 << "-" << high << std::endl;}else									// 硬幣數(shù)量為奇數(shù){sum1 = std::accumulate(a.begin() + low, a.begin() + mid, 0);sum2 = std::accumulate(a.begin() + mid + 1, a.begin() + high + 1, 0);std::cout << "  weighing coin " << low << "-" << mid - 1 << " and " << mid + 1 << "-" << high << std::endl;}std::cout << "    sum1=" << sum1 << " , sum2=" << sum2 << std::endl;if (sum1 == sum2){std::cout << "    --> equal" << std::endl;return mid;}else if (sum1 < sum2){std::cout << "    --> the former is lighter" << std::endl;if ((high - low + 1) % 2 == 0)	return solve(a, low, mid);	// 偶數(shù)else						return solve(a, low, mid - 1);	// 奇數(shù)}else{std::cout << "    --> the latter is lighter" << std::endl;return solve(a, mid + 1, high);}
}

用二分法分兩邊求最大值

#include<stdio.h>
void maxmin(int a, int b, int* min, int* max);
int array[9] = { 1,3,4,5,6,7,8,9,2 };int main() {int _max, _min;maxmin(0, 8, &_min, &_max);printf("MAX:%d, MIN:%d", _max, _min);
}void maxmin(int a, int b, int* min, int* max) {int lmax, lmin, rmax, rmin;if (a == b) *min = *max = array[a];else if (a == b - 1) {if (array[a] < array[b]) {*min = array[a];*max = array[b];}else {*min = array[b];*max = array[a];}}else {int mid = (a + b) / 2;maxmin(a, mid, &lmin, &lmax);maxmin(mid + 1, b, &rmin, &rmax);if (lmin < rmin) *min = lmin;else *min = rmin;if (rmax < lmax) *max = lmax;else *max = rmax;}}