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

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

1.判斷題數(shù)據(jù)結(jié)構(gòu)中，查找表是圖形結(jié)構(gòu)。

2 數(shù)據(jù)結(jié)構(gòu)與算法里，求兩個數(shù)的最大公約數(shù)，依照方式不同其時間復(fù)雜度可能是（）

3 哈希表的查找效率取決于（）

4 FIFO是（）的一搜索方式。

5 ACM算法的素?cái)?shù)和計(jì)算中，sum變量用于累加素?cái)?shù)之和，那么它的初值應(yīng)賦值為（）

6.問答題用回溯法解布線問題時，求最優(yōu)解的主要程序段如下：如果布線區(qū)域劃分為n×m的方格陣列，擴(kuò)展每個結(jié)點(diǎn)需O（1）的時間，L為最短布線路徑的長度，則算法共耗時（O（mn）），構(gòu)造相應(yīng)的最短距離需要（O（L））時間。

7.問答題寫出Prim算法描述，并給出時間復(fù)雜度的分析。

參考答案：假設(shè)N=（V，E），TE是N最小生成樹邊的集合。算法從U={u0}（u0∈V），TE={}開始，重復(fù)執(zhí)行下述操...

8 以下能正確定義數(shù)組并賦初值正確的語句是：（）。

9 數(shù)據(jù)結(jié)構(gòu)與算法里，如果待排序序列是完全有序的，使用改進(jìn)的冒泡排序，只需要（）趟排序。

10.問答題設(shè)計(jì)一個算法對n個實(shí)數(shù)組成的數(shù)組進(jìn)行重新排列，使得其中所有的負(fù)元素都位于正元素之前.這個算法需要兼顧空間和時間效率.