算法設(shè)計與分析章節(jié)練習(xí)(2020.06.07)

來源：考試資料網(wǎng)

1 子程序的遞歸邊界應(yīng)是i等于多少的時候。（）

2 以下關(guān)于數(shù)組的描述中，錯誤的有：（）

3 數(shù)據(jù)結(jié)構(gòu)與算法里，是不穩(wěn)定排序的有（）。

4 ACM算法也滿足算法的一般特性，而算法的特性包括（）

5 數(shù)據(jù)結(jié)構(gòu)與算法里，時間復(fù)雜度低于O（n*n）的排序有（）。

6.填空題在忽略常數(shù)因子的情況下，O、Ω和Θ三個符號中，（）提供了算法運(yùn)行時間的一個上界。

7.問答題編寫一個算法，可以檢測一個字符串是否回文（如：afaddafa，abwba等）。

8.問答題 求證遞歸方程

的解是T（n）=n「logn」–2^「logn」+1。

9.問答題 假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹。

參考答案：貪心算法：
（1）標(biāo)準(zhǔn)：重量、價值和單位價值。
（2）使用重量從小到大：FGBAEDC。得到貪心解為...

10.填空題算法的復(fù)雜性是（）的度量，是評價算法優(yōu)劣的重要依據(jù)。