圖結(jié)構(gòu)測試題及答案解析

一、單項選擇題（每題2分，共10題）1.一個有n個頂點的無向完全圖的邊數(shù)是（）A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/22.在圖的鄰接矩陣表示中，無向圖的鄰接矩陣一定是（）A.上三角矩陣B.下三角矩陣C.對稱矩陣D.對角矩陣3.深度優(yōu)先搜索遍歷圖，需要用到的數(shù)據(jù)結(jié)構(gòu)是（）A.隊列B.棧C.優(yōu)先隊列D.數(shù)組4.具有n個頂點的連通圖的生成樹，其邊數(shù)為（）A.nB.n-1C.n+1D.2n5.以下哪種算法可以用來求單源最短路徑（）A.Prim算法B.Kruskal算法C.Dijkstra算法D.拓撲排序6.圖的廣度優(yōu)先搜索類似于樹的（）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷7.無向圖中一個頂點的度是指與該頂點相關(guān)聯(lián)的（）A.邊的數(shù)目B.頂點的數(shù)目C.入邊的數(shù)目D.出邊的數(shù)目8.若一個圖的邊集為{(1,2),(2,3),(3,4),(1,4)}，則該圖是（）A.無向圖B.有向圖C.樹D.完全圖9.對于一個有向圖，其鄰接表存儲結(jié)構(gòu)中每個頂點鏈表的結(jié)點數(shù)等于該頂點的（）A.度B.入度C.出度D.邊數(shù)10.求帶權(quán)連通圖的最小生成樹的算法有（）A.迪杰斯特拉算法B.弗洛伊德算法C.Prim算法D.Kahn算法二、多項選擇題（每題2分，共10題）1.以下哪些屬于圖的存儲結(jié)構(gòu)（）A.鄰接矩陣B.鄰接表C.十字鏈表D.廣義表2.關(guān)于圖的遍歷，正確的說法有（）A.深度優(yōu)先遍歷需要使用棧B.廣度優(yōu)先遍歷需要使用隊列C.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都可以用于有向圖和無向圖D.圖的遍歷可以用來判斷圖是否連通3.以下算法中可以用于求圖的最小生成樹的有（）A.Prim算法B.Kruskal算法C.Dijkstra算法D.拓撲排序算法4.無向圖的連通分量是（）A.極大連通子圖B.極小連通子圖C.連通子圖中頂點數(shù)最多的D.連通子圖中邊數(shù)最多的5.有向圖的拓撲排序結(jié)果（）A.唯一B.可能不唯一C.存在的條件是圖中無環(huán)D.不存在的條件是圖中無環(huán)6.圖的鄰接矩陣具有以下哪些特點（）A.無向圖的鄰接矩陣是對稱的B.有向圖的鄰接矩陣可能不對稱C.鄰接矩陣可以方便地判斷頂點之間是否有邊D.鄰接矩陣存儲圖占用空間與頂點數(shù)和邊數(shù)都有關(guān)7.關(guān)于最短路徑算法，正確的是（）A.Dijkstra算法用于求單源最短路徑B.Floyd算法用于求任意兩點間最短路徑C.Dijkstra算法和Floyd算法都適用于帶負權(quán)邊的圖D.最短路徑算法中距離可能為負數(shù)8.以下關(guān)于圖的說法正確的是（）A.一個圖可以沒有邊B.一個圖可以沒有頂點C.無向圖的邊是無序?qū).有向圖的邊是有序?qū)?.圖的鄰接表存儲結(jié)構(gòu)的優(yōu)點有（）A.節(jié)省存儲空間B.方便查找頂點的鄰接點C.適合稀疏圖D.方便刪除邊10.下列哪些操作可以在圖上進行（）A.求連通分量B.求關(guān)鍵路徑C.求拓撲排序D.求單源最短路徑三、判斷題（每題2分，共10題）1.一個圖的鄰接矩陣表示唯一。（）2.深度優(yōu)先搜索和廣度優(yōu)先搜索對有向圖和無向圖都適用。（）3.無向圖中所有頂點的度之和等于邊數(shù)的兩倍。（）4.任何一個連通圖都有生成樹。（）5.拓撲排序適用于有向無環(huán)圖。（）6.求單源最短路徑的Dijkstra算法不能處理帶負權(quán)邊的圖。（）7.圖的鄰接表存儲結(jié)構(gòu)比鄰接矩陣存儲結(jié)構(gòu)更節(jié)省空間。（）8.一個有向圖的強連通分量是該圖的極大強連通子圖。（）9.最小生成樹是帶權(quán)連通圖中權(quán)值和最小的生成樹。（）10.若圖中存在環(huán)，則無法進行拓撲排序。（）四、簡答題（每題5分，共4題）1.簡述圖的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)的優(yōu)缺點。答案：鄰接矩陣優(yōu)點是直觀，方便判斷頂點間是否有邊；缺點是空間復(fù)雜度高，適合稠密圖。鄰接表優(yōu)點是節(jié)省空間，適合稀疏圖，方便找鄰接點；缺點是判斷頂點間是否有邊較復(fù)雜。2.簡述深度優(yōu)先搜索遍歷圖的基本思想。答案：從圖中某一頂點v出發(fā)，訪問v后，選擇一個與v相鄰且未被訪問的頂點w進行遞歸訪問，直到所有與v有路徑相通的頂點都被訪問到。若圖中還有未訪問頂點，則另選一個起始頂點重復(fù)上述過程。3.簡述Prim算法求最小生成樹的基本步驟。答案：任選一個頂點作為起始點，將其加入生成樹頂點集。每次從生成樹頂點集與剩余頂點集之間的邊中，選擇權(quán)值最小的邊，將其另一端頂點加入生成樹頂點集，直到所有頂點都在生成樹中。4.簡述拓撲排序的作用及適用條件。答案：作用是確定有向圖中頂點的線性順序，滿足有向邊的先后關(guān)系。適用條件是有向無環(huán)圖，若圖中有環(huán)則無法進行拓撲排序。五、討論題（每題5分，共4題）1.討論在實際應(yīng)用中，如何根據(jù)圖的特點選擇合適的存儲結(jié)構(gòu)。答案：若圖是稠密圖，頂點數(shù)不多，鄰接矩陣方便操作。若是稀疏圖，頂點數(shù)多，鄰接表節(jié)省空間。需頻繁判斷頂點間是否有邊，鄰接矩陣合適；注重找鄰接點操作，選鄰接表。2.討論Dijkstra算法和Floyd算法在求最短路徑上的區(qū)別和適用場景。答案：區(qū)別：Dijkstra求單源最短路徑，F(xiàn)loyd求任意兩點間最短路徑。適用場景：Dijkstra適用于給定起點到其他點最短路徑；Floyd適用于需知道圖中任意兩點間最短路徑的情況，F(xiàn)loyd能處理有負權(quán)邊但無負權(quán)環(huán)的圖，Dijkstra不能處理帶負權(quán)邊的圖。3.討論圖的遍歷算法在實際問題中的應(yīng)用，舉例說明。答案：在社交網(wǎng)絡(luò)分析中，廣度優(yōu)先搜索可用于查找某個人的k度好友；在文件系統(tǒng)中，深度優(yōu)先搜索可用于遍歷目錄結(jié)構(gòu)，找到特定文件。在電路布線檢測中，遍歷算法可判斷線路是否連通。4.討論最小生成樹算法在實際工程中的意義和應(yīng)用場景。答案：意義在于在帶權(quán)連通圖中找到權(quán)值和最小的生成樹，以達到節(jié)省成本等目的。應(yīng)用場景如通信網(wǎng)絡(luò)布線，可找到連接所有站點且線路成本最低的方案；在電力傳輸網(wǎng)絡(luò)構(gòu)建中，能確定成本最小的輸電線路布局。答案一、單項選擇題1.B2.C3.B4.B5.C6.D7.A8.A9.C10.C二、多項選擇題1.ABC2.