2025年大學(xué)《系統(tǒng)科學(xué)與工程》專業(yè)題庫——復(fù)雜系統(tǒng)網(wǎng)絡(luò)建模與優(yōu)化算法考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每題2分，共20分）1.在無向圖中，如果存在一條從頂點(diǎn)u到頂點(diǎn)v的路徑，那么頂點(diǎn)u和頂點(diǎn)v一定是（）。A.鄰接的B.相同的C.連通的D.無關(guān)的2.下列哪個(gè)指標(biāo)主要用于衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力或中心性？（）A.緊密度中心性B.網(wǎng)絡(luò)直徑C.介數(shù)中心性D.聚類系數(shù)3.對于一個(gè)有n個(gè)頂點(diǎn)的連通無向圖，其邊數(shù)至少為（）。A.n-1B.nC.n+1D.2n4.線性規(guī)劃問題的標(biāo)準(zhǔn)形式要求目標(biāo)函數(shù)是（）。A.最大化B.最小化C.等式D.不等式5.在解決整數(shù)規(guī)劃問題時(shí)，如果放松整數(shù)約束，得到的線性規(guī)劃問題稱為（）。A.松弛問題B.原問題C.對偶問題D.可行解6.貪心算法在每一步都選擇當(dāng)前看起來最優(yōu)的選擇，其目標(biāo)是保證得到（）。A.惟一解B.可行解C.最優(yōu)解D.近似解7.在網(wǎng)絡(luò)流問題中，容量約束指的是每條邊的流量不能超過其（）。A.容量B.流量C.前向流量D.后向流量8.模擬退火算法在搜索過程中，為了跳出局部最優(yōu)，會允許接受（）解。A.更好B.更差C.相同D.隨機(jī)9.遺傳算法中，代表種群中個(gè)體優(yōu)劣的指標(biāo)稱為（）。A.選擇算子B.交叉算子C.變異算子D.適應(yīng)度函數(shù)10.用于解決多目標(biāo)優(yōu)化問題的方法，如果能在不降低一個(gè)目標(biāo)值的情況下，不提高其他目標(biāo)值，則稱該解是（）。A.原始解B.非支配解C.可行解D.最優(yōu)解二、填空題（每空1分，共15分）1.一個(gè)無向圖G包含n個(gè)頂點(diǎn)和m條邊，若G是樹，則m=________。2.計(jì)算圖中節(jié)點(diǎn)i的介數(shù)中心性，需要計(jì)算節(jié)點(diǎn)i是否是所有節(jié)點(diǎn)對之間最短路徑的________。3.線性規(guī)劃問題中，約束條件通常表示為線性________。4.求解最小生成樹的Prim算法和Kruskal算法都屬于________算法。5.在最大流問題中，增廣路徑上的瓶頸容量決定了該次增廣能增加的流量。6.啟發(fā)式算法通常不能保證找到問題的________解，但可以在可接受的時(shí)間內(nèi)找到高質(zhì)量的________。7.遺傳算法中，通過模擬生物的________和________機(jī)制來指導(dǎo)搜索過程。8.粒子群優(yōu)化算法中，每個(gè)粒子根據(jù)自身的________和群體的________來更新其位置。三、簡答題（每題5分，共20分）1.簡述無向圖和有向圖在定義上的主要區(qū)別。2.簡要說明什么是網(wǎng)絡(luò)覆蓋問題，并舉例說明集合覆蓋問題的應(yīng)用場景。3.簡述貪心算法與動態(tài)規(guī)劃算法在基本思想上的主要區(qū)別。4.簡要解釋模擬退火算法中“溫度”參數(shù)的作用及其對算法行為的影響。四、計(jì)算題（每題8分，共16分）1.給定一個(gè)無向圖G，其頂點(diǎn)集V={A,B,C,D,E}，邊集E={AB,AC,AD,BC,BD,CE}。請計(jì)算圖中頂點(diǎn)A的度中心性、緊密度中心性和介數(shù)中心性（提示：可以假設(shè)所有邊的權(quán)重相同，路徑長度為1）。2.考慮一個(gè)簡單的整數(shù)規(guī)劃問題：MaxZ=3x1+2x2，約束條件為x1+x2<=4，x1>=0,x2>=0,且x1,x2為整數(shù)。嘗試用割平面法或分支定界法的基本思想，描述如何尋找該問題的最優(yōu)解（無需給出完整求解過程，只需闡述思路）。五、算法設(shè)計(jì)/分析題（10分）已知一個(gè)無向連通圖G=(V,E)，頂點(diǎn)集V包含一個(gè)特殊頂點(diǎn)s。要求設(shè)計(jì)一個(gè)算法，找到從頂點(diǎn)s出發(fā)，能夠覆蓋所有其他頂點(diǎn)的最短路徑（即所有頂點(diǎn)到s的最短路徑之和最短）。請簡要描述你的算法思路，并分析該算法的時(shí)間復(fù)雜度（假設(shè)圖采用鄰接矩陣或鄰接表存儲）。試卷答案一、選擇題1.A2.C3.A4.B5.A6.B7.A8.B9.D10.B二、填空題1.n-12.中間節(jié)點(diǎn)3.等式或不等式（根據(jù)題目具體要求，通常指不等式約束）4.圖論5.最小6.最優(yōu)，近似7.交叉，變異8.最佳位置，平均位置三、簡答題1.解析思路：無向圖的邊沒有方向，頂點(diǎn)u和頂點(diǎn)v之間的邊表示u與v之間的連接是雙向的；有向圖的邊具有方向，從頂點(diǎn)u到頂點(diǎn)v的邊表示u與v之間的單向連接，反之不一定存在邊。2.解析思路：網(wǎng)絡(luò)覆蓋問題是指在一個(gè)網(wǎng)絡(luò)（通常用圖表示）中，找到一個(gè)子集（如頂點(diǎn)集或邊集），使得網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)（或邊）至少被這個(gè)子集中的一個(gè)元素“覆蓋”。集合覆蓋問題是指給定一系列集合，每個(gè)集合包含一些元素，要求找到一個(gè)最小的子集集合，使得這些子集的并集包含所有的元素。應(yīng)用場景舉例：在社交網(wǎng)絡(luò)中，找到最小的博主集合覆蓋所有用戶；在城市交通規(guī)劃中，找到最小的公交線路集合覆蓋所有區(qū)域。3.解析思路：貪心算法在每一步選擇當(dāng)前看起來最優(yōu)的選擇，并立即執(zhí)行，不考慮未來可能的影響，目標(biāo)是達(dá)到局部最優(yōu)；動態(tài)規(guī)劃算法通過將問題分解為子問題，存儲子問題的解（通常使用表格），避免重復(fù)計(jì)算，目標(biāo)是達(dá)到全局最優(yōu)。4.解析思路：模擬退火算法中的“溫度”參數(shù)T控制著算法接受“壞解”（目標(biāo)函數(shù)值更差的解）的概率。高溫時(shí)，接受壞解的概率高，算法能在解空間中自由探索，避免陷入局部最優(yōu)；低溫時(shí)，接受壞解的概率低，算法逐漸收斂到當(dāng)前解鄰域內(nèi)的較好解。四、計(jì)算題1.解析思路：度中心性是節(jié)點(diǎn)連接的邊的數(shù)量；緊密度中心性是節(jié)點(diǎn)可達(dá)的鄰居節(jié)點(diǎn)數(shù)除以最大可能的鄰居節(jié)點(diǎn)數(shù)（對于無向圖是n-1）；介數(shù)中心性是節(jié)點(diǎn)出現(xiàn)在所有其他節(jié)點(diǎn)對之間的最短路徑上的次數(shù)。根據(jù)給定的圖和定義進(jìn)行計(jì)算。度中心性A：連接邊有AB,AC,AD，共3條，度數(shù)為3。緊密度中心性A：鄰居節(jié)點(diǎn)有B,C,D，共3個(gè)，最大鄰居節(jié)點(diǎn)數(shù)是n-1=4，緊密度中心性=3/4。介數(shù)中心性A：計(jì)算所有節(jié)點(diǎn)對的最短路徑，并統(tǒng)計(jì)A是否為中間節(jié)點(diǎn)。AB-AC:A是中間節(jié)點(diǎn)。AB-AD:A是中間節(jié)點(diǎn)。AB-BD:A是中間節(jié)點(diǎn)。AC-BD:A是中間節(jié)點(diǎn)。AC-CE:A不是中間節(jié)點(diǎn)。AD-CE:A不是中間節(jié)點(diǎn)。BD-CE:A不是中間節(jié)點(diǎn)。共7條最短路徑，其中4條以A為中間節(jié)點(diǎn)，介數(shù)中心性=4/10=2/5。（注意：此處計(jì)算基于所有邊的權(quán)重相同且路徑長度為1的簡化假設(shè)，實(shí)際圖論計(jì)算可能更復(fù)雜）2.解析思路：割平面法的基本思想是在松弛問題的可行域上添加線性不等式（割平面），限制可行解的范圍，使得最優(yōu)解（如果存在）不會在新的可行域中，從而逐步逼近整數(shù)規(guī)劃問題的最優(yōu)解。分支定界法的基本思想是將整數(shù)規(guī)劃問題的解空間分解為多個(gè)子問題（分支），對每個(gè)子問題求解其松弛問題（可能是線性規(guī)劃或整數(shù)規(guī)劃），通過比較目標(biāo)函數(shù)值和上界/下界，剪枝掉不可能包含最優(yōu)解的子問題，最終找到最優(yōu)解。五、算法設(shè)計(jì)/分析題解析思路：可以將問題轉(zhuǎn)化為求圖中從頂點(diǎn)s到所有其他頂點(diǎn)的最短路徑之和。這可以看作是一個(gè)帶權(quán)圖的最小路徑覆蓋問題，或者通過構(gòu)造一個(gè)新圖來求解。一個(gè)可能的思路是：1.從頂點(diǎn)s出發(fā)，使用Dijkstra算法或BFS算法找到到所有其他頂點(diǎn)的最短路徑，并記錄每條路徑的長度。2.將問題轉(zhuǎn)化為：在原圖G中，找到一個(gè)邊集，使得每條邊至少屬于某一條從s到其他頂點(diǎn)的最短路徑，并且這個(gè)邊集的總權(quán)重（即路徑長度之和）是最小的。3.這個(gè)問題類似于最小邊權(quán)最大流問題，可以將頂點(diǎn)s作為源點(diǎn)，所有其他頂點(diǎn)作為匯點(diǎn)，在每條從s出發(fā)到達(dá)其他頂點(diǎn)的最短路徑上設(shè)置單位容量和相應(yīng)的路徑長度作為容量和權(quán)重，然后求解最小邊權(quán)最大流。這個(gè)流網(wǎng)絡(luò)的流量為1，其最小