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

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

1.問答題請列舉幾個常見的NP完全問題。

參考答案：1）合取范式的可滿足性問題；
2）三元合取范式的可滿足性問題；
3）團問題；
4）頂點覆蓋...

2.問答題求最大、最小元算法的時間復(fù)雜度（比較次數(shù)）下界是多少？分治算法在什么情況下可以達到下界？

參考答案：在規(guī)模為n的數(shù)據(jù)元素集合中找出最大元和最小元，至少需要3n/2-2次比較，即3n/2-2是找最大最小元算法的下界。當(dāng)n=...

3.問答題如何重構(gòu)warshall算法最內(nèi)層循環(huán)，使得它到少對于某此輸入來說運行得列快？

4 使用二分搜索算法在1000個有序元素表中搜索一個特定元素，在最壞情況下，搜索總共需要比較的次數(shù)為（）

5.判斷題數(shù)據(jù)結(jié)構(gòu)與算法里，冒泡排序是不穩(wěn)定的排序。

6.問答題寫出歸并排序算法對下列實例排序的過程。（6，2，9，3，5，1，8，7）

7 一個單窗體Vb程序的運行界面如下圖所示：下列說法正確的是（）
（1）窗體內(nèi)有1個按鈕
（2）窗體內(nèi)有2個文本框
（3）窗體內(nèi)有3個標(biāo)簽
（4）該窗體的標(biāo)題（caption）屬性值是“加法計算器”

8 函數(shù)調(diào)用的一種特殊，即自己調(diào)用自己稱為（）。

9.問答題現(xiàn)有另一臺計算機，其運行速度為第一臺的64倍，那么在這臺新機器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？

參考答案：設(shè)新機器用同一算法在t秒內(nèi)能解輸入規(guī)模為n’的問題，則有
T（n）=3×2ⁿ...

10 青蛙過河問題中，如果河中沒有石柱，有x片荷葉的話，那么從左岸到右岸可以過去（）只青蛙