?參考教材：《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版 第2版）》 嚴(yán)蔚敏，李冬梅，吳偉民編著，人民郵電出版社，2022年版。
截圖未標(biāo)明出處均為原創(chuàng)或取自《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版 第2版）》~
?
本文對(duì)應(yīng)的作業(yè)題講解視頻：
?數(shù)據(jù)結(jié)構(gòu)與算法分析作業(yè)講解視頻合集https://www.bilibili.com/video/BV1NN411A7hd/?share_source=copy_web&vd_source=7fbf4cbf97db097fe9c00746d1be6e44
作業(yè)講解文檔鏈接目錄：?
第二章 線性表
第三章 棧和隊(duì)列
第四章 串、數(shù)組和廣義表
第五章 樹(shù)和二叉樹(shù)
第六章 圖
第七章 查找
第八章 排序
(?//?????)?// ? ? ?(?//*'▽'*)?// ? ? ?(?//??????)?/? ? ??(?//?????)?// ? ? ?(?//*'▽'*)?// ? ? ?(?//??????)?/
? ? ? ? ?╭═════╮╭═══════════╮
? ? ?╭╯讓路！? ?║ 題來(lái)了！題來(lái)了！
? ? ? ?╰⊙═══⊙╯╰═⊙═══⊙═══⊙╯
| 單選題1 |
用鄰接矩陣A表示圖,判定任意兩個(gè)頂點(diǎn)Vi和Vj之間是否有長(zhǎng)度為m的路徑相連,則只要檢查( ???)的第i行第j列的元素是否為零即可。 |
| A: m^A | |
| 正確答案：C | |
| 思路：
| |
| 單選題2 |
用DFS遍歷一個(gè)無(wú)環(huán)有向圖,并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn),則輸出的頂點(diǎn)序列是( ???)。 |
| A: 逆拓?fù)溆行?/span> | |
| 正確答案：A | |
| 思路：
| |
| 單選題3 |
下列說(shuō)法不正確的是( ???)。 |
| A: 圖遍歷是從某源點(diǎn)出發(fā)，每一個(gè)頂點(diǎn)僅被訪問(wèn)一次 | |
| 正確答案：C | |
| 思路： 反例：第二題。 | |
| 單選題4 |
無(wú)向圖G=(V,E),其中:V={a,b,c,d,e,f}, ??E={(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)},對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是( ???)。 |
| A: a,b,e,c,d,f | |
| 正確答案：D | |
| 思路： 先根據(jù)已知條件畫(huà)圖，然后從a點(diǎn)開(kāi)始遍歷。 | |
| 單選題5 |
用鄰接矩陣存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。( ???) |
| A: 正確 | |
| 正確答案：B | |
| 思路： 鄰接矩陣表示法創(chuàng)建無(wú)向圖G的時(shí)間復(fù)雜度是O(n^2)
| |
| 單選題6 |
用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí),在不考慮壓縮存儲(chǔ)的情況下,所占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān),而與圖的邊數(shù)無(wú)關(guān)。 |
| A: 正確 | |
| 正確答案：A | |
| 單選題7 |
有n個(gè)頂點(diǎn)的無(wú)向圖,采用鄰接矩陣表示,圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。( ???) |
| A: 正確 | |
| 正確答案：A | |
| 思路：
? ? | |
| 單選題8 |
有向圖的鄰接矩陣是對(duì)稱的。( ???) |
| A: 正確 | |
| 正確答案：B | |
| 思路：
? ? ?
| |
| 單選題9 |
無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣,有向圖的鄰接矩陣一定是非對(duì)稱矩陣。 |
| A: 正確 | |
| 正確答案：B | |
| 思路： 前半句是對(duì)的；后半句是錯(cuò)的。 | |
| 單選題10 |
連通分量指的是有向圖中的極大連通子圖。 |
| A: 正確 | |
| 正確答案：B | |
| 思路： 連通分量：無(wú)向圖中的極大連通子圖 | |
| 單選題11 |
鄰接多重表是無(wú)向圖和有向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 |
| A: 正確 | |
| 正確答案：B | |
| 思路： 鄰接多重表是無(wú)向圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 | |
| 單選題12 |
十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。 |
| A: 正確 | |
| 正確答案：B | |
| 思路： 十字鏈表是有向圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 | |
| 單選題13 |
無(wú)向圖的鄰接矩陣可用一維數(shù)組存儲(chǔ)。 |
| A: 正確 | |
| 正確答案：A | |
| 思路：
| |
| 單選題14 |
鄰接矩陣適用于有向圖和無(wú)向圖的存儲(chǔ),但不能存儲(chǔ)帶權(quán)的有向圖和無(wú)向圖,而只能使用鄰接表存儲(chǔ)形式來(lái)存儲(chǔ)它。 |
| A: 正確 | |
| 正確答案：B | |
| 單選題15 |
有e條邊的無(wú)向圖,在鄰接表中有e個(gè)結(jié)點(diǎn)。 |
| A: 正確 | |
| 正確答案：B | |
| 思路： 無(wú)向圖中的一條邊要存儲(chǔ)兩次。
| |
| 單選題16 |
有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)。 |
| A: 正確 | |
| 正確答案：B | |
| 思路： 頂點(diǎn)的度=頂點(diǎn)的出度+頂點(diǎn)的入度
| |
| 單選題17 |
強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。 |
| A: 正確 | |
| 正確答案：A | |
| 思路：
| |
| 單選題18 |
強(qiáng)連通分量是無(wú)向圖的極大強(qiáng)連通子圖。 |
| A: 正確 | |
| 正確答案：B | |
| 思路：
| |
| 單選題19 |
一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等。 |
| A: 正確 | |
| 正確答案：B | |
| 思路：
| |
| 單選題20 |
需要借助于一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)DFS算法。 |
| A: 正確 | |
| 正確答案：B | |
| 思路： DFS一般借助?；蜻f歸實(shí)現(xiàn)。 | |
| 單選題21 |
一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖。 |
| A: 正確 | |
| 正確答案：A | |
| 思路：
| |
| 單選題22 |
N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有( ???)個(gè)非零元素。 |
| A: N | |
| 正確答案：B | |
| 思路： N個(gè)頂點(diǎn)的連通圖至少有N-1條邊。無(wú)向圖的一條邊在鄰接矩陣中對(duì)應(yīng)兩個(gè)非零元素，所以整個(gè)矩陣一共有2(N-1)個(gè)非零元素。 | |
| 單選題23 |
在圖G的鄰接表表示中,每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù),對(duì)于無(wú)向圖來(lái)說(shuō)等于該頂點(diǎn)的度;對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的出度。 |
| A: 正確 | |
| 正確答案：A | |
| 思路：
| |
| 單選題24 |
具有10個(gè)頂點(diǎn)的無(wú)向圖,邊的總數(shù)最多為( ???) |
| A: 45 | |
| 正確答案：A | |
| 思路： 每個(gè)頂點(diǎn)和其他所有頂點(diǎn)都有邊，則每個(gè)頂點(diǎn)有9條邊×10個(gè)頂點(diǎn)=90，又因?yàn)闊o(wú)向圖中一個(gè)邊連接兩個(gè)點(diǎn)，所以，90/2= 45條邊。 | |
| 單選題25 |
在有n個(gè)頂點(diǎn)的有向圖中,若要使任意兩點(diǎn)間可以互相到達(dá),則至少需要( ???)條弧。 |
| A: n+1 | |
| 正確答案：C | |
| 思路： 整體形成一個(gè)環(huán)即可。 | |
| 單選題26 |
要連通具有n個(gè)頂點(diǎn)的有向圖,至少需要( ???)條邊。 |
| A: n-1 | |
| 正確答案：B | |
| 思路： 整體形成一個(gè)環(huán)即可。 | |
| 單選題27 |
在有n個(gè)頂點(diǎn)的有向圖中,每個(gè)頂點(diǎn)的度最大可達(dá)( ???)。 |
| A: n+1 | |
| 正確答案：D | |
| 思路： 出度=入度=n-1。即每個(gè)點(diǎn)都有出發(fā)到其他所有點(diǎn)的弧和從其他所有出發(fā)到達(dá)自己的弧。 | |
| 單選題28 |
若用n表示圖中頂點(diǎn)數(shù)目,則有( ???)條邊的無(wú)向圖成為完全圖。 |
| A: n(n-1)/2 | |
| 正確答案：A | |
| 思路：
| |
| 單選題29 |
n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目( ????)。 |
| A: n^2 | |
| 正確答案：D | |
| 單選題30 |
設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有( ???)條邊。 |
| A: n-1 | |
| 正確答案：B | |
| 單選題31 |
G是一個(gè)非連通無(wú)向圖,共有28條邊,則該圖至少有( ???)個(gè)頂點(diǎn)。 |
| A: 9 | |
| 正確答案：A | |
| 思路： 假設(shè)圖G’滿足最少有n個(gè)點(diǎn)構(gòu)成一個(gè)有28條邊的連通無(wú)向圖，則G’再增加一個(gè)孤立的點(diǎn)，就能滿足題意，使該圖成為非連通無(wú)向圖G。且最少有n個(gè)點(diǎn)構(gòu)成一個(gè)有28條邊的連通無(wú)向圖，則G’一定是一個(gè)完全圖，即n(n-1)/2=28, n=8, 即G中的頂點(diǎn)數(shù)=8+1=9。 | |
| 單選題32 |
對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接表的表示,則表頭向量大小為n,鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為( )。 |
| A: n*e | |
| 正確答案：D | |
| 思路： 注意這是一個(gè)無(wú)向圖。
| |
| 單選題33 |
已知一無(wú)向圖G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)始遍歷圖,得到的序列為abecd,則采用的是廣度優(yōu)先遍歷方法。 |
| A: 正確 | |
| 正確答案：B | |
| 單選題34 |
圖中有關(guān)路徑的定義是( ???)。 |
| A: 由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列 | |
| 正確答案：A | |
| 單選題35 |
一個(gè)包含n個(gè)頂點(diǎn)的連通無(wú)向圖,其邊的個(gè)數(shù)至少為( ???)。 |
| A: n-1 | |
| 正確答案：A | |
| 單選題36 |
在一個(gè)無(wú)向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)( ???)倍。 |
| A: 1/2 | |
| 正確答案：D | |
| 思路： 一個(gè)邊連接兩個(gè)點(diǎn)。舉例。 | |
| 單選題37 |
在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的( ?)倍。 |
| A: 0 | |
| 正確答案：D | |
| 思路： 一個(gè)弧提供一個(gè)入度+一個(gè)出度。所以入度之和=出度之和=弧的數(shù)量。 | |
| 單選題38 |
一個(gè)有n個(gè)結(jié)點(diǎn)的圖,最少有( ???)個(gè)連通分量。 |
| A: 0 | |
| 正確答案：B | |
| 思路： 連通分量是指無(wú)向圖中的極大連通子圖。 | |
| 單選題39 |
一個(gè)有n個(gè)結(jié)點(diǎn)的圖,最多有( ???)個(gè)連通分量。 |
| A: 1 | |
| 正確答案：C | |
| 思路： 連通分量是指無(wú)向圖中的極大連通子圖。 | |
| 單選題40 |
下列哪一種圖的鄰接矩陣是對(duì)稱矩陣?( ???) |
| A: 有向圖 | |
| 正確答案：B | |
| 思路：
| |
| 單選題41 |
關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中( ???)。 |
| A: 從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 C: 最長(zhǎng)回路 D: 最短回路 | |
| 正確答案：A | |
| 思路：
| |
| 單選題42 |
關(guān)鍵路徑是AOE網(wǎng)中從源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑。 |
| A: 正確 | |
| 正確答案：A | |
| 單選題43 |
下列關(guān)于AOE網(wǎng)的敘述中,不正確的是( ???)。 |
| A: 關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間 C: 所有的關(guān)鍵活動(dòng)提前完成,那么整個(gè)工程將會(huì)提前完成 D: 某些關(guān)鍵活動(dòng)提前完成,那么整個(gè)工程將會(huì)提前完成 | |
| 正確答案：B | |
| 思路： 關(guān)鍵路徑可能不止一條，一個(gè)關(guān)鍵路徑上的關(guān)鍵活動(dòng)提前完成，另一條關(guān)鍵路徑上的活動(dòng)保持不變，整個(gè)工程還是不會(huì)提前完全。 | |
| 單選題44 |
在表示某工程的AOE網(wǎng)中,加速其關(guān)鍵路徑上的任意關(guān)鍵活動(dòng)均可縮短整個(gè)工程的完成時(shí)間。 |
| A: 正確 | |
| 正確答案：B | |
| 單選題45 |
下面關(guān)于求關(guān)鍵路徑的說(shuō)法不正確的是( ???)。 |
| A: 求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的 C: 一個(gè)事件的最遲開(kāi)始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開(kāi)始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差 D: 關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上 | |
| 正確答案：C | |
| 思路：
? | |
| 單選題46 |
在AOE圖中關(guān)鍵路徑上活動(dòng)的時(shí)間延長(zhǎng)多少,整個(gè)工程時(shí)間也就隨之延長(zhǎng)多少。 |
| A: 正確 | |
| 正確答案：A | |
| 單選題47 |
Dijkstra最短路徑算法從源點(diǎn)到其余各頂點(diǎn)的最短路徑的路徑長(zhǎng)度按遞增次序依次產(chǎn)生,該算法弧上的權(quán)出現(xiàn)負(fù)值情況時(shí),不能正確產(chǎn)生最短路徑。 |
| A: 正確 | |
| 正確答案：A | |
| 思路：
| |
| 單選題48 |
已知有向圖G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7}, ??E={<V1,V2>, <V1,V3>, <V1,V4>, <V2,V5>, <V3,V5>, <V3,V6>, <V4,V6>, <V5,V7>, <V6,V7>},G的拓?fù)湫蛄惺? ???)。 |
| A: V1,V3,V4,V6,V2,V5,V7 | |
| 正確答案：A | |
| 思路：
| |
| 單選題49 |
下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)( ???) |
| A: 深度優(yōu)先遍歷 | |
| 正確答案：B | |
| 思路： 在 AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)榇嬖诃h(huán)意味著某項(xiàng)活動(dòng)應(yīng)以自己為先決條件。顯然，這是荒謬的。若設(shè)計(jì)出這樣的流程圖，工程便無(wú)法進(jìn)行。而對(duì)程序的數(shù)據(jù)流圖來(lái)說(shuō)，則表明存在一個(gè)死循環(huán)。因此，對(duì)給定的 AOV-網(wǎng)應(yīng)首先判定網(wǎng)中是否存在環(huán)。檢測(cè)的辦法是對(duì)有向圖的頂點(diǎn)進(jìn)行拓?fù)渑判?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該A0V-網(wǎng)中必定不存在環(huán)。 | |
| 單選題50 |
有向圖G可拓?fù)渑判虻呐袆e條件是不存在環(huán)。 |
| A: 正確 | |
| 正確答案：A | |
| 單選題51 |
拓?fù)渑判虻挠邢驁D中,最多存在一條環(huán)路。 |
| A: 正確 | |
| 正確答案：B | |
| 單選題52 |
在有向圖G的拓?fù)湫蛄兄?若頂點(diǎn)Vi在頂點(diǎn)Vj之前,則下列情形不可能出現(xiàn)的是( ???)。 |
| A: G中有弧<vi,vj> | |
| 正確答案：D | |
| 思路： 頂點(diǎn)Vi在頂點(diǎn)Vj之前，說(shuō)明Vi是執(zhí)行Vj的先決條件。如果還有D答案Vj到Vi的路徑，則Vj是Vi的先決條件，彼此互為先決條件，則存在環(huán)，無(wú)法產(chǎn)生產(chǎn)生拓?fù)渑判颍c題目矛盾，所以選D。 | |
| 單選題53 |
設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊,進(jìn)行拓?fù)渑判驎r(shí),總的計(jì)算時(shí)間為( ???)。 |
| A: O(n) | |
| 正確答案：C | |
| 思路： 因?yàn)橥負(fù)渑判蛩惴ㄊ窃贏OV-網(wǎng)上進(jìn)行的，是一種有向圖，并且排序算法的整個(gè)過(guò)程對(duì)每個(gè)活動(dòng)（頂點(diǎn)）和每個(gè)弧都只經(jīng)歷一次。且用鄰接表表示圖時(shí)的時(shí)間復(fù)雜度為O(n+e)。 | |
| 單選題54 |
在用鄰接表表示圖時(shí),拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為( ???)。 |
| A: O(n) | |
| 正確答案：B | |
| 思路： 因?yàn)橥負(fù)渑判蛩惴ㄊ窃贏OV-網(wǎng)上進(jìn)行的，是一種有向圖，并且排序算法的整個(gè)過(guò)程對(duì)每個(gè)活動(dòng)（頂點(diǎn)）和每個(gè)弧都只經(jīng)歷一次。且用鄰接表表示圖時(shí)的時(shí)間復(fù)雜度為O(n+e)。 | |
| 單選題55 |
拓?fù)渑判蛩惴ò岩粋€(gè)無(wú)向圖中的頂點(diǎn)排成一個(gè)有序序列。 |
| A: 正確 | |
| 正確答案：B | |
| 單選題56 |
拓?fù)渑判蛩惴▋H能適用于有向無(wú)環(huán)圖。 |
| A: 正確 | |
| 正確答案：B | |
| 單選題57 |
帶權(quán)的連通無(wú)向圖的最小代價(jià)生成樹(shù)是唯一的。( ???) |
| A: 正確 | |
| 正確答案：B | |
| 思路：
可能會(huì)生成多個(gè)代價(jià)之和相同且都為最小的生成樹(shù)。 | |
| 單選題58 |
最小生成樹(shù)問(wèn)題是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(shù)。( ???) |
| A: 正確 | |
| 正確答案：A | |
| 單選題59 |
任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?而且拓?fù)湫蛄胁晃ㄒ弧?/span> |
| A: 正確 | |
| 正確答案：B | |
| 思路： 不能在有環(huán)的有向圖上完成拓?fù)渑判颉?/span> | |
| 單選題60 |
不同的求最小生成樹(shù)的方法最后得到的生成樹(shù)是相同的。 |
| A: 正確 | |
| 正確答案：B | |
| 思路： 最小生成樹(shù)的形狀可以是不同，但能保證代價(jià)之和相同且同為最小。 | |
| 單選題61 |
最小生成樹(shù)的KRUSKAL算法是一種貪心法。 |
| A: 正確 | |
| 正確答案：A | |
| 思路： KRUSKAL算法：克魯斯卡爾算法。 | |
| 單選題62 |
求最小生成樹(shù)的普里姆()算法中邊上的權(quán)可正可負(fù)。 |
| A: 正確 | |
| 正確答案：B | |
| 單選題63 |
判斷一個(gè)無(wú)向圖是一棵樹(shù)的條件是有n個(gè)頂點(diǎn),n-1條邊的無(wú)向連通圖。 |
| A: 正確 | |
| 正確答案：A | |
| 單選題64 |
Prim(普里姆)算法適用于求邊稠密的網(wǎng)的最小生成樹(shù);kruskal(克魯斯卡爾)算法適用于求邊稀疏的網(wǎng)的最小生成樹(shù)。 |
| A: 正確 | |
| 正確答案：A | |
| 思路： 因?yàn)槠绽锬匪惴ǎ狱c(diǎn)法）的過(guò)程是不斷選點(diǎn)加入?？唆斔箍査惴ǎ舆叿ǎ┑倪^(guò)程是不斷選邊加入。 | |
| 單選題65 |
如果含n個(gè)頂點(diǎn)的圖形形成一個(gè)環(huán),則它有( ???)棵生成樹(shù)。 |
| A: n-1 | |
| 正確答案：B | |
| 思路： n個(gè)頂點(diǎn)形成一個(gè)環(huán)，則有n條邊。每斷一條邊，這個(gè)環(huán)都構(gòu)不成，整個(gè)圖可以被看出一棵樹(shù)，有n條不同的邊可以斷，則對(duì)應(yīng)有n種生成樹(shù)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-777423.html |
??????????????????????????????????????????????????????? \?HAVE A GOOD?DAY?/??? ??????????????????????????????????????????????????????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-777423.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法分析 第六章 圖 作業(yè)講解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
