算法設計與分析章節(jié)練習(2020.04.22)

來源：考試資料網

1.判斷題數據結構中，查找表是圖形結構。

2 數據結構與算法里，求兩個數的最大公約數，依照方式不同其時間復雜度可能是（）

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

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

5 ACM算法的素數和計算中，sum變量用于累加素數之和，那么它的初值應賦值為（）

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

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

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

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

9 數據結構與算法里，如果待排序序列是完全有序的，使用改進的冒泡排序，只需要（）趟排序。

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