2017春季北大算分期末考試

24 人贊了文章

1.讀代碼，給出一個長度為n的數組A，元素為互不相等的實數

Func(A, s, t)

1.Assert(s,t) // 判斷是否滿足s<=t

2.k=Rand(s,t) //從[s,t]中隨機選擇一個k

3.if k > s then

4. If A[k-1] > A[k] then

5. Return Func(A, k, t)

6. Else

7. Return Func(A, s, k-1)

8.if A[s] > A[t]

9. Return t

10.Return s

問代碼作用，求最壞情況的時間複雜度

2.給出一個區間集合S。定義「支配」：若兩個集合相交，那麼他們互相支配彼此。S的支配集P：S中的任意元素都能被P中的元素支配。求一個規模最小的P。

3.動規，求兩個字元串的最小cost匹配，失配cost為2，空白cost為1，且要判斷唯一性

4.線性規劃，求對偶問題的標準形

5.網路流，n個城市，m條路，路的距離都已經給出，有k名自行車選手，要從城市1分別騎行到城市n，每條路只能容納一輛自行車，是否存在一種路徑分配，使得k名選手能從城市1騎到城市n，若存在，求一個所需路徑總長度最小的。

6.Npc，有向圖G，若圖G能被兩兩不相交的圈覆蓋所有的頂點，那麼稱之為圈覆蓋。

（1）設計一個多項式演算法求圖G的圈覆蓋（提示：可以直接調用二部圖匹配）

（2）若把條件加強為：任意一個圈至少有三個頂點，那麼證明這個問題變為NPC問題

7.近似演算法，設計一個O（E）的貪心演算法，求圖的極大匹配，分析近似比，並給出緊實例

8.隨機選擇演算法如下：判斷亂序數組A（1~n）中是否存在x。隨機選擇一個x1，和x比較，若是，則輸出yes，若不是，則在剩下的元素中隨機選擇一個和x比較，以此類推，直到所有元素都和x比較過，那麼輸出no。假設x存在在數組A中的概率為p，求比較次數的期望值。