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

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

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

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

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

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

點(diǎn)擊查看完整答案

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

參考答案：

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

參考答案：8天

5.問(wèn)答題快速排序算法最壞情況下需要多少次比較運(yùn)算？

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