考試科目名稱計(jì)算機(jī)問(wèn)題求解(三)

考試科目名稱 計(jì)算機(jī)問(wèn)題求解 (三)考試日期：2019年01月09日 教師：陶先平、馬駿、魏恒峰系（專業(yè)）：計(jì)算機(jī)科學(xué)與技術(shù)系 年級(jí)：2017級(jí)姓名： 學(xué)號(hào)： 成績(jī)：題號(hào) 一 二 三 四 五 六 七 八分?jǐn)?shù)注意事項(xiàng):誠(chéng)信考試,不得作弊。若對(duì)題意有疑問(wèn),請(qǐng)及時(shí)提出。題目不是按照難度排列的,請(qǐng)注意合理分配時(shí)間。不完整的解題思路甚至“感覺(jué)”也有可能成為得分點(diǎn)。對(duì)于算法設(shè)計(jì)題:–請(qǐng)先用自然語(yǔ)言闡述算法原理,切勿只寫(xiě)偽代碼。–請(qǐng)明確闡述你設(shè)計(jì)的算法為什么是正確的(要給出關(guān)鍵證明)。–請(qǐng)明確闡述你設(shè)計(jì)的算法為什么是滿足時(shí)間復(fù)雜度要求的 (盡管這可能很簡(jiǎn)單 )。符號(hào)說(shuō)明:κ(G):圖G的點(diǎn)連通度;λ(G):圖G的邊連通度。提示:試題后的提示僅作提示之用,不排除其它解法。12題目1服務(wù)器上有n個(gè)請(qǐng)求等待處理。已知請(qǐng)求i的處理時(shí)長(zhǎng)為ti。當(dāng)服務(wù)器處理某請(qǐng)求時(shí),其它尚未處理的請(qǐng)求需要等待,每個(gè)請(qǐng)求的等待時(shí)間定義為在它之前的請(qǐng)求的處理時(shí)長(zhǎng)之和。請(qǐng)?jiān)O(shè)計(jì)算法計(jì)算最優(yōu)的處理順序,使得所有請(qǐng)求的等待時(shí)間之和最小。題目2給定帶權(quán)無(wú)向連通圖 G=(V,E,w)(w為權(quán)重函數(shù))證明:e不屬于G的任何最小生成樹(shù)當(dāng)且僅當(dāng) u、v

與G中任一條邊 e=(u,v)∈E。之間存在由權(quán)重均小于 w(e)的邊構(gòu)成的路徑。題目3給定無(wú)向連通圖 G=(V,E)。定義(SCC 定向)如果能對(duì) G的每條邊確定一個(gè)方向 ,使得定向后的有向圖是強(qiáng)連通的 ,則稱G存在SCC定向。請(qǐng)證明G存在SCC定向當(dāng)且僅當(dāng)G中沒(méi)有橋。(2)假設(shè)G中沒(méi)有橋,請(qǐng)?jiān)O(shè)計(jì)一個(gè)線性時(shí)間算法給出 G的一種SCC定向。要求:如果你使用了圖遍歷框架 ,偽代碼中需要包含該框架代碼。題目4考慮帶權(quán)無(wú)向連通圖 G。定義(瓶頸長(zhǎng)度)G中路徑的瓶頸長(zhǎng)度指的是該路徑上最小的邊權(quán)重。定義(瓶頸距離)G中兩點(diǎn)的瓶頸距離指的是該兩點(diǎn)間所有路徑中的最大瓶頸長(zhǎng)度。請(qǐng)?jiān)O(shè)計(jì)算法求 G中所有點(diǎn)對(duì)之間的瓶頸距離 (不必給出具體路徑)。(Yourgoalisto,foranysandt,findapathfromstotwhoseminimumedgeweightismaximized.)要求:時(shí)間復(fù)雜度為O(n3)(n為G的頂點(diǎn)數(shù))。請(qǐng)寫(xiě)出偽代碼。3題目5請(qǐng)寫(xiě)出Menger定理(無(wú)向圖“點(diǎn)連通”或“邊連通”版本)。請(qǐng)使用Menger定理證明:如果G是3-正則圖,則κ(G)=λ(G)。(提示:可使用教材中基于Menger定理證明的定理或推論,但需明確說(shuō)明。)題目6中國(guó)象棋有 “馬走日”的規(guī)則。證明或證偽:對(duì)于任何n∈Z+,在4×n的棋盤上,不存在“馬踏棋盤回路”(從某棋盤格開(kāi)始，遍歷所有棋盤格一次且僅一次，并回到起始棋盤格)。(提示:以4×5為例,見(jiàn)圖1。)圖1:灰白相間的棋盤。題目7考慮無(wú)向連通圖 G上的雙人游戲。在該游戲中 ,兩位玩家交替選擇頂點(diǎn)。游戲開(kāi)始時(shí),先手玩家任選一個(gè)頂點(diǎn)。接下來(lái),每位玩家選擇的頂點(diǎn)需要(1)與另一位玩家剛剛選擇的頂點(diǎn)相鄰(2)之前未被選過(guò)。(也就是說(shuō),兩位玩家選擇的頂點(diǎn)構(gòu)成一條簡(jiǎn)單路徑。)若無(wú)頂點(diǎn)可選,則該玩家為輸家,另一玩家為贏家。請(qǐng)解答并