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

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

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

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

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

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

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

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

7.問(wèn)答題編寫(xiě)一個(gè)算法，可以檢測(cè)一個(gè)字符串是否回文（如：afaddafa，abwba等）。

8.問(wèn)答題 求證遞歸方程

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

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

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

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