計算機專業基礎綜合（數據結構）模擬試卷5（總分:102.00,做題時間：90分鐘）一、單項選擇題（總題數：35,分數：70.00）單項選擇題1-40小題。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。下面是一個求最小生成樹的算法，其中G是連通無向圖，T是所求的生成樹。T;=G;WhileT中存在回路dobegin在T中找一條權值最大的邊e；T：=T一[e]；（T中去掉e邊）End.試問該算法是哪一種求最小生成樹的算法？（）Prim（普里姆）算法Kruskal（克魯斯卡爾算法）"羅巴赫算法其他算法由算法可以看出使用的是Knlskal算法。鄰接表是圖的一種（）。順序存儲結構鏈接存儲結構V索引存儲結構散列存儲結構圖的鄰接表存儲結構是一種鏈接存儲結構。下面試圖對圖中路徑進行定義，說法正確的是（）。由頂點和相鄰頂點序列構成的邊所形成的序列V由不同頂點所形成的序列由不同邊所形成的序列上述定義都不是由圖的定義可知，B與c是錯誤的。無向圖中項點個數為n,那么邊數最多為（）。n一1n（n-1）/2Vn（n+1）/2TOC\o"1-5"\h\zn2無向圖中有n個頂點，如果每兩個頂點之間均是相互連通的，那么此時無向圖中的邊數最多，為凡（n—1）/2。在一個具有n（n〉0）個頂點的連通無向圖中，至少需要的邊數是（）。nn+1n-1Vn/2在無向圖中，如果從一個頂點vj到另一個頂點vj（i#j）有路徑，則稱頂點vj和vj是連通的。如果圖中任意兩頂點都是連通的，則稱該圖是連通圖。所以具有n個頂點的連通無向圖至少有n一1條邊。以下敘述中正確的是（）。I.對有向圖G，如果以任一頂點出發進行一次深度優先或廣度優先搜索能訪問到每個頂點，則該圖一定是完全圖II.連通圖的廣度優先搜索中一般要采用隊列來暫存訪問過的頂點III.圖的深度優先搜索中一般要采用棧來暫存訪問過的頂點I，IIb.n，mvi，mi，ii，mI的敘述是錯誤的，因為如果有向圖構成雙向有向環時，則從任一頂點出發均能訪問到每個頂點，但該圖卻非完全圖。11、111的敘述顯然是正確的。帶權有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（）。第i行非8的元素之和第i列非8的元素之和第i行非8且非0的元素個數第i列非8且非0的元素個數V有向圖的鄰接矩陣中，0和8表示的都不是有向邊，而入度是由鄰接矩陣的列中元素計算出來的。在一個無向圖中，所有頂點的度之和等于邊數的（）倍。TOC\o"1-5"\h\z1/212V4在無向圖中，一條邊計入兩個頂點的度數。采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的（）算法。前序遍歷V中序遍歷后序遍歷按層遍歷由圖的深度優先遍歷算法和二叉樹的前序遍歷可知選A。任何一個無向連通圖（）最小生成樹。只有一棵有一棵或多棵V一定有多棵可能不存在無向連通圖應有一棵或多棵最小生成樹。判斷有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用的是（）。求關鍵路徑的方法求最短路徑的迪杰斯特拉方法深度優先遍歷算法V廣度優先遍歷算法當有向圖中無回路時，從某頂點出發進行深度優先遍歷時，出棧的順序（退出DFSTra—verse算法）即為逆向的拓撲序列。有n個頂點e條邊的無向圖，采用鄰接表存儲時，有（）個表頭結點，有（）個鏈表結點。n，2eVn，2e+1n-1，2en-1，2e+1根據鄰接表的結構，無向圖對應的鄰接表有n個表頭結點，有2e個鏈表結點（每條邊對應兩個鏈表結點）。對于由n個頂點組成的有向完全圖來說，圖中共包含（）條邊，對于由n個頂點組成的無向完全圖來說，圖中共包含（）條邊。n，n（n一1）n，n（n一1）/22n，n（n—1）n（n一1），n（n一1）/2V由完全圖的定義可知本題答案為D。在一個（）圖中尋找拓撲序列的過程稱為（）。有向，拓撲排序V無向，拓撲排序

有向，最短路徑搜索無向，最短路徑搜索尋找拓撲序列就是拓撲排序，只能對有向圖進行拓撲排序。TOC\o"1-5"\h\z用鄰接矩陣A表示圖，判定任意兩個頂點v「和vj之間是否有長度為m的路徑相連，則只要檢查（）的第i行第j列的元素是否為零即可。1JmAAAmVAm-1此題考查的知識點是圖的鄰接矩陣存儲。在圖的鄰接矩陣中，兩點之間有邊，則值為1，否則為0。本題只要考慮Am=AXAX???XA（m個A矩陣相乘后的乘積矩陣）中（i，j）的元素值是否為0就行了。當各邊上的權值（）時，BFS算法可用來解決單源最短路徑問題。均相等V均互不相等不一定相等不確定此題考查的知識點是圖的BFS算法。BFS是從根結點開始，沿著樹的寬度遍歷樹的結點，如果所有結點均被訪問，則算法中止。當各邊上的權值相等時，計算邊數即可，所以選A。下面關于圖的存儲結構的敘述中正確的是（）。用鄰接矩陣存儲圖占用空間大小只與圖中頂點數有關，與邊數無關V用鄰接矩陣存儲圖占用空間大小只與圖中邊數有關，與頂點數無關用鄰接表存儲圖占用空間大小只與圖中頂點數有關，與邊數無關用鄰接表存儲圖占用空間大小只與圖中邊數有關，與頂點數無關鄰接矩陣法的基本思想是對于有n個頂點的圖，用一維數組Vexs[n]存儲頂點信息，用二維數組A[n][n]存儲頂點之間關系的信息。該二維數組稱為鄰接矩陣。在鄰接矩陣中，以頂點在Vexs數組中的下標代表頂點，鄰接矩陣中的元素A[i][j]存放的是頂點i到頂點點，鄰接矩陣中的元素A[i][j]存放的是頂點i到頂點j之間關系的信息。鄰接表法的基本思想:對圖的每個頂點建立一個單鏈表，存儲該頂點所有鄰接頂點及其相關信息。每一個單鏈表設一個表頭結點。第i個單鏈表表示依附于頂點V「第i個單鏈表表示依附于頂點V「的邊（對有向圖是以頂點V.為頭或尾的?。?9.在有向圖G的拓撲序列中，若頂點v「在頂點vj之前a.g中有m<vj，JG中有一條從'vjG中沒有m<vG中有一條從v則下列情形不可能出現的是（）。v.>到v.的路徑，v.〉到vj的路徑V此題考查的知識點是圖的拓撲排序。根據拓撲排序的定義，中頂點vj必在頂點v.之前。若有一條從v.到vj應選DoJJ若頂點v「與頂點vj有一條弧，則拓撲序列的路徑，則頂點v.不可能在頂點vj之前。所以以下關于圖的說法中正確的是（）oI.一個有向圖的鄰接表和逆鄰接表中的結點個數一定相等II.用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中結點個數有關，而與圖的邊數無關III.無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的I，IVb.n，mI，I僅有II說法I是正確的，鄰接表和逆鄰接表的區別僅在于出邊和入邊，邊表的結點個數都等于有向圖中的邊的個數。說法II是正確的，鄰接矩陣的空間復雜度為O（n2），與邊的個數無關。說法m是錯誤的，有向圖的鄰接矩陣不一定是不對稱的，例如，有向完全圖的鄰接矩陣就是對稱的。下列關于AOE網的敘述中，不正確的是（）o

關鍵活動不按期完成就會影響整個工程的完成時間任何一個關鍵活動提前完成，那么整個工程將會提前完成V所有的關鍵活動提前完成，那么整個工程將會提前完成某些關鍵活動提前完成，那么整個工程將會提前完成此題考查的知識點是圖的關鍵路徑。在AOE網中，從始點到終點具有最大路徑長度（該路徑上的各個活動所持續的時間之和）的路徑稱為關鍵路徑，并且不只一條。關鍵路徑上的活動稱為關鍵活動。A、C、D的說法都正確。但任何一個關鍵活動提前完成，不一定會影響關鍵路徑，所以根據題意應選B。一個二部圖的鄰接矩陣A是一個（）類型的矩陣。nXn矩陣分塊對稱矩陣V上三角矩陣下三角矩陣此題考查的知識點是二部圖的定義與存儲。二部圖定義為：若能將無向圖G=的頂點集V劃分成兩個子集V1和V2（V1CV2=[*]），使得G中任何一條邊的兩個端點一個屬于V1，另一個屬于V2,則稱G為二部圖。由于其特點，其存儲矩陣必為分塊對稱的，所以選B。求解最短路徑的Floyd算法的時間復雜度為（）。O（n）O（n+c）O（n2）O（n3）VV24.下列4組含C1-C7的結點序列中，（）是下圖所示的有向圖的拓撲序列。VA.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C3，C6TOC\o"1-5"\h\zn2nVn-11因為n個頂點構成的環共有n條邊，去掉其中任意一條便是一棵生成樹，共有n種情況，所以可以有n棵不同的生成樹。⑤aecfdbaefdbc5432本題中26.如下圖所示，在下面的5個序列中，符合深度優先遍歷的序列有（）個。①aebfdc②acfdeb③aedfcb④V⑤aecfdbaefdbc5432本題中無向圖G有23條邊，度為4的頂點有5個，度為3的頂點有4個，其余都是度為2的頂點，則圖G最多有（）個頂點。11121516V由于在具有n個頂點e條邊的無向圖中，有由于在具有n個頂點e條邊的無向圖中，有點。故可求得度為2的頂點數為7個，從而最多有16個頂對AOE網絡中有關關鍵路徑的敘述中，正確的是()。從開始頂點到完成頂點的具有最大長度的路徑，關鍵路徑長度是完成整個工程所需的最短時間V從開始頂點到完成頂點的具有最小長度的路徑，關鍵路徑長度是完成整個工程所需的最短時間從開始頂點到完成頂點的具有最大長度的路徑，關鍵路徑長度是完成整個工程所需的最長時間從開始頂點到完成頂點的具有最小長度的路徑，關鍵路徑長度是完成整個工程所需的最長時間本題考查關鍵路徑的定義。關鍵路徑：從起點到終點的最長路徑長度(路徑上各活動持續時間之和)。關鍵活動：關鍵路徑上的活動稱為關鍵活動。以下關于圖的敘述中，正確的是()。強連通有向圖的任何頂點到其他所有頂點都有弧圖與樹的區別在于圖的邊數大于或等于頂點數無向圖的連通分量指無向圖中的極大連通子圖V假設有圖G=｛V，｛E｝｝，頂點集V'UV，E'UE，則V’和｛E’｝構成G的子圖強連通有向圖的任何頂點到其他所有頂點都有路徑，但未必有弧，A錯誤。圖與樹的區別是邏輯上的，而不是邊數的區別，圖的邊數也可能小于樹的邊數。若E'中的邊對應的頂點不是V'中的元素時，則V'和｛E'｝無法構成圖，D錯誤。假設有n個頂點e條邊的有向圖用鄰接表表示，則刪除與某個頂點v相關的所有邊的時間復雜度為()。O(n)O(e)O(n+e)VO(ne)刪除與某項點v相關的所有邊的過程如下：先刪除下標為v的頂點表結點的單鏈表，出邊數最多為n—1，對應時間復雜度為O(n)，再掃描所有邊表結點，刪除所有的入邊，對應時間復雜度為O(e)。故總的時間復雜度為O(n+e)。若G是一個具有36條邊的非連通無向圖(不含自回路和多重邊)，則圖G的結點數至少是()。1110V98n個頂點構成的無向圖中，邊數Wn(n—1)/2,將e=36代入，有nN9,現巳知無向圖是非連通的，則n至少為10O已知有向圖G=(V，A)，其中V=｛a，b，c，d，e｝，A=｛，，，，，｝。對該圖進行拓撲排序，下面序列中不是拓撲排序的是()oa，d，c，b，ed，a，b，c，ea，b，d，c，ea，b，c，d，eV選項D中，刪去a、b及其對應的出邊后，c的入度不為0，因此有邊，故不是拓撲序列。選項A、B、C均為拓撲序列。解答本類題時，建議讀者根據邊集合畫出草圖。用有向無環圖描述表達式(A+B)*((A+B)/A)，至少需要頂點的數目為()。TOC\o"1-5"\h\z5V689

此題考查的知識點是有向無環圖的定義。有向無環圖是一個無環的有向圖，可以用來表示公共子表達式，本題中出現的5個字符作為5個頂點，其中A+B和A可共用，所以至少5個即可，選A。鄰接多重表的存儲結構和十字鏈表類似，也是由頂點表和邊表組成，每一條邊用一個結點表示，其頂點表結點結構和邊表結點結構如下圖所示:關于圖中各個域的說明，不正確的是（）。表結點結構和邊表結點結構如下圖所示:關于圖中各個域的說明，不正確的是（）。vertex存儲的是結點的數值域的內容firstedge域指示第一條依附于該頂點的邊mark指向下一條依附于結點的邊Vinfo為指向和邊相關的各種信息的指針域頂點表由兩個域組成,vertex域存儲和該頂點相關的信息，firstedge域指示第一條依附于該頂點的邊。邊表結點由六個域組成：mark為標記域，用以標記該條邊是否被搜索過；ivex和jvex為該邊依附的兩個頂點在圖中的位置；iIink指向下一條依附于頂點ivex的邊；jlink指向下一條依附于頂點jvex的邊：info為指向和邊相關的各種信息的指針域。以下關于十字鏈表的說法中，不正確的是（）。十字鏈表是有向圖的另一種鏈式存儲結構行指針row為矩陣中的行位置，列指針col為矩陣中的列位置數值val為矩陣中的值right指針指向矩陣中的行位置，down指針指向矩陣中的列位置Vright指向右側的一個非零元素，down指向下側的一個非零元素。二、綜合應用題（總題數：16,分數：32.00）綜合應用題41-47小題。證明：具有n個頂點和多于n一1條邊的無向連通圖G一定不是樹。正確答案：（正確答案：此題考查的知識點是圖的定義。具有n個頂點n-1條邊的無向連通圖是自由樹，即沒有確定根結點的樹，每個結點均可當根。若邊數多于n一1條，因一條邊要連接兩個結點，則必因加上這一條邊而使兩個結點多了一條通路，即形成回路。形成回路的連通圖不再是樹（在圖論中樹定義為無回路的連通圖）。）證明：對有向圖的頂點適當地編號，可使其鄰接矩陣為下三角形且主對角線為全0的充要條件是該圖為無環圖。正確答案：（正確答案：此題考查的知識點是無環圖的定義。根據題意，該有向圖頂點編號的規律是讓弧尾頂點的編號大于弧頭頂點的編號。由于不允許從某頂點發出并回到自身頂點的弧，所以鄰接矩陣主對角線元素均為0。先證明該命題的充分條件。由于弧尾頂點的編號均大于弧頭頂點的編號，在鄰接矩陣中，非零元素（A[i][j]=1）自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現弧頭頂點編號大于弧尾頂點編號的弧，否則，就必然存在環路。（對該類有向無環圖頂點編號，應按頂點出度順序編號。））關于圖（Graph）的一些問題：（1）有n個頂點的有向強連通圖最多有多少條邊?最少有多少條邊？（2）表示有1000個頂點、1000條邊的有向圖的鄰接矩陣有多少個矩陣元素?是否為稀疏矩陣？正確答案：（正確答案：（1）n（n—1），n（2）106，不一定是稀疏矩陣提示：此題考查的知識點是圖的相關術語。（1）在有向圖G中，如果對于每一對vj，vj，屬于V，vj不等于vj，從vj到vj和從vj到v「都存在路徑，則稱G是強連通圖。最多邊是所有的頂點每對之間都有邊，邊數為n（n一1）；最少只有一個方向有邊，為n。（2）元素個數為矩陣的大小，即106，稀疏矩陣的定義是非零個數遠小于該矩陣元素個數，且分布無規律，不一定稀疏。）如何對有向圖中的頂點號重新安排可使得該圖的鄰接矩陣中所有的1都集中到對角線以上？正確答案：（正確答案：此題考查的知識點是圖頂點度數。可以按各頂點的出度進行排序。n個頂點的有向圖，其頂點最大出度是n一1，最小出度為0。這樣排序后，出度最大的頂點編號為1，出度最小的頂點編

號為n之后，進行調整，即若存在弧，而頂點j的出度大于頂點i的出度，則將j的編號排在頂點i的編號之前。）假定圖G=（V，E）是有向圖，V=｛1，2,…，N｝，NN1，G以鄰接矩陣方式存儲，G的鄰接矩陣為A，即A是一個二維數組。如果i到j有邊，則A[i，j]=1，否則A[i，j]=0。請給出一個算法思想，該算法能判斷G是否是非循環圖（即G中是否存在回路），要求算法的時間復雜性為O（n2）。正確答案：（正確答案：此題考查的知識點是圖的遍歷。采用深度優先遍歷算法，在執行DFS（v）時，若在退出DFS（v）前碰到某頂點u，其鄰接點是巳經訪問的頂點v，則說明v的子孫u有到v的回邊，即說明有環；否則，無環。）對一個圖進行遍歷可以得到不同的遍歷序列，那么導致得到的遍歷序列不唯一的因素有哪些？正確答案：（正確答案：此題考查的知識點是圖的遍歷。遍歷不唯?的因素有：開始遍歷的頂點不同；存儲結構不同；在鄰接表情況下鄰接點的順序不同。）G=（V，E）是一個帶有權的連通圖，如圖所示。（1）什么是G的最小生成樹G=（V，E）是一個帶有權的連通圖，如圖所示。（1）什么是G的最小生成樹？（2）G如圖所示，請找出G的所有最小生成樹。正確答案：（正確答案：（1）無向連通圖的生成樹包含圖中全部n個頂點，以及足以使圖連通的n-1條邊。而最小生成樹則是各邊權值之和最小的生成樹。（2）最小生成樹有兩棵。下面給出頂點集合和邊集合，編以三元組（Vj，V,，W）形式，其中W代表權值。V（G）=｛1，2，3，4，5｝E1（G）=｛（4，5，2），（2，5，4），（2，3，5），（1，2，7）｝；E2（G）=｛（4，5，2），（2，4，4），（2，3，5），（1，2，7）｝）對于如下的加權有向圖，給出算法Dijkstra產生的最短路徑的支撐樹，設頂點A為源點，并寫出生成過程。過程。正確答案：（正確答案：頂點A到頂點B、C、D、E的最短路徑依次是3、18、38、43,按Dijkstra所選頂點過程是B、C、D、E。支撐樹的邊集合為｛，，，｝，具體分析如下表所示。[*]）（1）對于有向無環圖，敘述求拓撲有序序列的步驟。（2）對于以下的圖，寫出它的4個不同的拓撲有序序列。列。正確答案：（正確答案：（1）對有向圖，求拓撲序列步驟為：①在有向圖中選一個沒有前驅（即入度為零）的頂點并輸出。②在圖中刪除該頂點及所有以它為尾的弧。③重復①和②步，直至全部頂點輸出，這時拓撲排序完成；否則，圖中存在環，拓撲排序失敗。（2）從入度為O的頂點開始，當有多個頂點可以輸出時，將其按序從上往下排列，這樣不會丟掉?種拓撲序列。從頂點1開始的可能的拓撲序列為12345678、12354678、13456278、13546278。提示：此題考查的知識點是拓撲排序。）試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點▼「到頂點Vj的路徑（iNj）。（注意：算法中涉及的圖的基本操作必須在存儲結構上實現。）1J正確答案：（正確答案：算法1：intvisited[]=0：//全局變量，訪問數組初始化intdfs（AdjListg，vi）｛//以鄰接表存儲的有向圖g，判斷vi到vj是否有通路，返回1或0visited[vi]=1；//visited是訪問數組，設頂點的信息就是頂點編號P=g[vi].firstarc；//第一個鄰接點while（P!=null）｛j=p一〉adjvex；if（vj==j）｛flag=1；return（1）；｝//vi和vj有通路if（visited[j]==0）dfs（g，j）；P=P一〉next：｝//whileif（!flag）return（0）；｝算法2：輸出vi到vj的路徑，其思想是用一個棧存放遍歷的頂點，遇到頂點vj時輸出路徑。voiddfs（AdjListg，inti）｛//頂點vi和頂點vj間是否有路徑，如有，則輸出inllop=0，stack[]；//stack是存放頂點編號的棧visited[i]=1；//visited數組在進入dfs前巳初始化stack[++top]=i；P=g[i].firstarc；//求第一個鄰接點while（P）｛if（p一〉adjvex==j）｛stack[++top]=j；printf（"頂點vi和vj的路徑為：\n"）；for（i=1；i<=top；i++）printf（"%4d"，stack[i]）；exit（0）:｝elseif（visited[p一〉adjvex]==0）｛dfs（g，g—〉adjvex）；top一一；P=p一〉next；}}}算法3：非遞歸算法求解。intJudge(AdjListg,inti,j){//判斷n個頂點以鄰接表示的有向圖g中，頂點vi各vj是否有路徑，//有則返回1,否則返回0。for(i=1；i<=n；i++)visited[i]=0i//訪問標記數組初始化intstack[],top=0；stack[++top]=vi；while(top>0){k=stack[top一一];P=g[k].firstarc；while(P!=null&&visited[p一〉adjvex]==1)p=p—〉next；//查第k個鏈表中第一個未訪問的弧結點if(P==null)top一一：else{i=p一〉adjvex；if(i==j)return(1)；//頂點vi和vj間有路徑else{visited[i]=1；stack[++top]=i；}}}whilereturn(0)；}//頂點vi和vj間無通路)假設以鄰接矩陣作為圖的存儲結構，編寫算法判別在給定的有向圖中是否存在一個簡單有向回路，若存在，則以頂點序列的方式輸出該回路(找到一條即可)。(注意：圖中不存在頂點到自己的弧)正確答案：(正確答案：用鄰接矩陣存儲時，可用以下方法實現：voidPrint(intv，intstart){//輸出從頂點start開始的回路for(i：1；i<=n：i++)if(g[v][i]!=0&&visited[i]==1){//若存在邊(v，i)，且頂點i的狀態為1printf("%d.t，V)；if(i==start)printf("\n")：elsePrint(i，start):break；}//if}//Printvoiddfs(intv){visited[v]=；for(j=1；j<=n；j++)if(g[v][j]!=0)//存在邊(v，j)if(visited[j]!=1){if(!visited[j])dfs(j)；}//ifelse{cycle=1；Print(j，j):}visited[v]=2：}voidfind_cycle(){//判斷是否有回路，有則輸出鄰接矩陣。visited數組為全局變量for(i=1；i<=n；i++)visited[i]=0；for(i=1；i<=n；i++)if(!visited[i])dfs(i)：})巳有鄰接表表示的有向圖，請編程判斷從第u頂點至第v頂點是否有簡單路徑，若有則打印出該路徑上的頂點。正確答案：(正確答案：voidAllpath(AdjListg，vertypeU，vertypev){//求有向圖g中頂點u到頂點v的所有簡單路徑，初始調用形式inttop=0，S□:S[++top]=u；visited[U]=1；while(top>0||P){P=g[S[top/]/].firstarc；//第一個鄰接點while(Pf=null&&visited[p一〉adjvex]==1)P=p->next；//下一個訪問鄰接點表if(P==null)top--://退棧else{i=p一〉adjvex;//取鄰接點(編號)if(i==V){//找到從u到v的一條簡單路徑，輸出for(k=1；k<=top；k++)printf("%3d"，s[k])：printf(tt%3d\n"，v)：}//ifelse{visited[i]=1；s[++top]=i；}//else深度優先遍歷}//else}//while})“破圈法”是“任取一圈，去掉圈上權最大的邊”，反復執行這一步驟，直到沒有圈為止。請給出用“破圈法”求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細算法，并用程序實現你所給出的算法。(注意：圈就是回路)正確答案：(正確答案：voidSpnTree(AdjListg){//用"破圈法”求解帶權連通無向圖的一棵最小代價生成樹typedefstruct{inti，j，w：}node；//設頂點信息就是頂點編號，權是整數nodeedge[]；scanf("％d%d”，&e，&n)；//輸入邊數和項點數for(i=1；i<=e；i++)//輸入e條邊：頂點，權值seanf("%d%d%d”，&edge[i].i，&edge[i].j，&edge[i].W)；for(i=2；i<=e；i++){//按邊上的權值大小，對邊進行逆序排序edge[0]=edge[i]；j=i一1；while(edge[j].W<edge[0].W)edge[j+1]=edge[j一一];edge[j+1]=edge[0];}//fork=1；eg=e；while(eg>=n){//破圈，直到邊數e=n一1if(connect(k))//刪除第k條邊若仍連通fedge[k].W=0；eg--；}//測試下一條邊edge[k]，權值置0表示該邊被刪除k++；//下條邊}//while}connect()是測試圖是否連通的函數，可用DFS函數或BFS函數實現，若是連通圖，一次進入DFS函數或BFS函數就可遍歷完全部頂點，否則，因為刪除該邊而使原連通圖成為兩個連通分量時，該邊不應刪除?！捌迫Α苯Y束后，可輸出edge中W不為0的n一1條邊。)設計一個算法求圖的中心點。設v是有向圖G的一個頂點，把v的偏心度定義為：MAx{從3到v的最短距離{3屬于V(G)}如果v是有向圖G中具有最小偏心度的頂點，則稱頂點v是G的中心點。正確答案：(正確答案：設C是有向圖G的鄰接矩陣，求最小偏心度的頂點的步驟如下：(1)利用Floyd算法求出每對頂點之間的最短路徑矩陣A；(2)對矩陣A求出每列i的最大值，得到頂點i的偏心度；(3)在這n個頂點的偏心度中，求出最小偏心度的頂點k，即為圖G的中心點。對應的算法如下：intCenter(MGraph&G)}intA[MAXV][MAXV]，B[MAXV]；inti，j，k，m；for(i=0；i<G.n；i++)//將鄰接矩陣賦給Afor（j=0；j<G.n；j++）A[i][j]=G.edges[i]Ej]；for（k=0；k<G.n；k++）//實現（1）功能，求出每對頂點之間的最短路徑for（i=0；i<G.n；i++）for（j=0；j<G.n；j++）if（A[i][k]+