數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題-文庫吧在線文庫
【正文】 B．出邊 C．入邊和出邊 D．不是入邊也不是出邊11．在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有______鄰接點(diǎn)。A．l/2 B．1 C．2 D．43．一個(gè)具有n個(gè)頂點(diǎn)的無向圖最多包含______條邊。A．n(n1) B．n(n+l) C．n(nl)/2 D．n(n+l)/26．對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為______。A．先序遍歷 B．中序遍歷C．后序遍歷 D．按層遍歷14．采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的______算法。A．極小連通子圖 B．極小子圖C．極大連通子圖 D．極大子圖22．設(shè)無向圖 G=(V, E) 和G’= (V’, E’)，如果 G’為G的生成樹，則下列說法中不正確的是______。A．是個(gè)有根有向圖 B．是個(gè)強(qiáng)連通圖C．含有多個(gè)入度為0的頂點(diǎn) D．含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量26．判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用____。3．對(duì)于具有n個(gè)頂點(diǎn)的有向圖，每個(gè)頂點(diǎn)的度最大可達(dá)___________。v1v2v3v4 ∧v5v6 ∧234 ∧35 ∧6 ∧4 63 ∧圖73 圖G的鄰接表11．n個(gè)頂點(diǎn)連通圖的生成樹一定有__________條邊。三、判斷題1．具有n個(gè)頂點(diǎn)的無向圖至多有n（n1）條邊。9．強(qiáng)連通分量是有向圖的極大連通子圖。17．從n個(gè)頂點(diǎn)的連通圖中選取n1條權(quán)值最小的邊，即可構(gòu)成最小生成樹。25．在AOE網(wǎng)中工程工期為關(guān)鍵活動(dòng)上權(quán)值之和。12543圖74 一個(gè)無向圖7．對(duì)于圖75所示的有向圖，試給出：（1）鄰接矩陣。（3）找出關(guān)鍵路徑并指明完成該工程所需的最短時(shí)間。（2）求出圖G中每個(gè)頂點(diǎn)的出度（3）求出圖G中出度最大的一個(gè)頂點(diǎn)，輸出該頂點(diǎn)的編號(hào)。8．假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，判斷無向圖G是否連通，若連通則返回1；否則返回0。13．假設(shè)圖G采用鄰接矩陣存儲(chǔ)，設(shè)計(jì)一個(gè)算法判斷在給定的有向圖中是否存在一個(gè)簡單有向回路，若存在，則以頂點(diǎn)序列的方法輸出該回路（找到一條即可）。18．假設(shè)圖G采用鄰接矩陣存儲(chǔ)，采用弗洛伊德算法設(shè)計(jì)一個(gè)求有向圖的根的算法。21．假設(shè)AOE網(wǎng)以鄰接表方式存儲(chǔ)，設(shè)計(jì)一個(gè)算法求該AOE網(wǎng)的所有關(guān)鍵活動(dòng)。試?yán)蒙疃葍?yōu)先搜索方法，對(duì)該圖中所有頂點(diǎn)進(jìn)行逆向拓?fù)渑判?。假設(shè)每1km的鐵路造價(jià)為1000萬元。（2）給定一組必經(jīng)點(diǎn){7,9}，即輸出的路徑必須包含這些頂點(diǎn)。4．一個(gè)連通圖采用鄰接表作為存儲(chǔ)機(jī)構(gòu)，設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)從頂點(diǎn)v出發(fā)的深度優(yōu)先遍歷的非遞歸過程。（2）求出圖G中每個(gè)頂點(diǎn)的出度（3）求出圖G中出度最大的一個(gè)頂點(diǎn)，輸出該頂點(diǎn)的編號(hào)。BNPLTMB 109828121124N109585510832P825839792L815539589T211089795113M12432928911311．對(duì)于圖77所示的帶權(quán)有向圖，采用狄克斯特拉算法求從頂點(diǎn)1到其它頂點(diǎn)的最短路徑，要求給出求解過程。29．某些關(guān)鍵活動(dòng)若提前完成，將可能使整個(gè)工程提前完成。21．拓?fù)渑判蛩惴▋H適用于有向無環(huán)圖。13．有向圖的遍歷不可采用廣度優(yōu)先搜索方法。5．如果表示圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定是無向圖。15．可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是_________。7．對(duì)于n個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是__________，判斷任意兩個(gè)頂點(diǎn)i和
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1