算法設(shè)計與分析問答題每日一練(2020.06.10)

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

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

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

2.問答題在最接近點對問題中，用一條垂直線L：x=m將平面點集分為大致相等的兩個子集S1和S2。設(shè)P1和P2分別表示直線L的左邊和右邊的寬為d的兩個垂直長條區(qū)域，d1和d2分別是S1和S2中最小距離，且設(shè)d=min{d1，d2}。對于P1中任意一個點p，可能和在P2中點q構(gòu)成全平面點集的最接近點對的候選點對，請證明：P2中最多有6對這樣的候選點對。

參考答案：根據(jù)鴿籠原理：如果n+1只鴿子飛入n個籠子中，那么至少有一個籠子里包含兩只或兩只以上的鴿子。
將矩形R的長為2...

點擊查看完整答案

3.問答題證明如果一棵樹的所有內(nèi)部節(jié)點的度都為k，則外部節(jié)點數(shù)n滿足nmod（k-1）=1。

參考答案：

4.問答題如果n=2^k，循環(huán)賽最少需要進行幾天；

參考答案：8天

5.問答題快速排序算法最壞情況下需要多少次比較運算？

參考答案：最壞情況下快速排序退化成冒泡排序，需要比較n²次。