數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡(jiǎn)介】 表頭向量的大小為___________，所有鄰接表中的結(jié)點(diǎn)總數(shù)是__________。6．已知一個(gè)有向圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的弧的方法是____________。7．對(duì)于n個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是__________，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是__________，求任意一個(gè)頂點(diǎn)的度的方法是___________。8．對(duì)于n個(gè)頂點(diǎn)的有向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是_________，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是__________，求任意一個(gè)頂點(diǎn)的度的方法是__________。9．無向圖的連通分量是指___________。 10．已知圖G的鄰接表如圖73所示，從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為________，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列為_____________。v1v2v3v4 ∧v5v6 ∧234 ∧35 ∧6 ∧4 63 ∧圖73 圖G的鄰接表11．n個(gè)頂點(diǎn)連通圖的生成樹一定有__________條邊。12．一個(gè)連通圖的___________是一個(gè)極小連通子圖。 13．Prim算法適用于求_________的網(wǎng)的最小生成樹，Kruskal算法適用于求________的網(wǎng)的最小生成樹。 14．在AOV圖中，頂點(diǎn)表示________,有向邊表示________。15．可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是_________。16．從源點(diǎn)到匯點(diǎn)長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑，該路徑上的活動(dòng)稱為________。 17．Dijkstra算法從源點(diǎn)到其它各頂點(diǎn)的路徑長(zhǎng)度按________次序依次產(chǎn)生，該算法在邊上的權(quán)出現(xiàn)_________情況時(shí)，不能正確產(chǎn)生最短路徑。18．求從某源點(diǎn)到其余各項(xiàng)點(diǎn)的Dijkstra算法在圖的頂點(diǎn)數(shù)為10，用鄰接矩陣表示圖時(shí)計(jì)算時(shí)間約為10ms，則在圖的頂點(diǎn)數(shù)為40時(shí)，計(jì)算時(shí)間約為_________ms。三、判斷題1．具有n個(gè)頂點(diǎn)的無向圖至多有n（n1）條邊。2．有向圖中各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和。3．鄰接矩陣只儲(chǔ)存了邊的信息，沒有存儲(chǔ)頂點(diǎn)的信息。4．對(duì)同一個(gè)有向圖，只保存出邊的鄰接表中結(jié)點(diǎn)的數(shù)目總是和只保存入邊的鄰接表中結(jié)點(diǎn)的數(shù)目一樣多。5．如果表示圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定是無向圖。6．如果表示有向圖的鄰接矩陣是對(duì)稱矩陣，則該有向圖一定是有向完全圖。7．如果表示某個(gè)圖的鄰接矩陣不是對(duì)稱矩陣，則該圖一定是有向圖。8．連通分量是無向圖的極小連通子圖。9．強(qiáng)連通分量是有向圖的極大連通子圖。10．對(duì)有向圖G，如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每一個(gè)頂點(diǎn)，則該圖一定是完全圖。11．連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫時(shí)剛訪問過的頂點(diǎn)。12．圖的深度優(yōu)先搜索中一般要采用棧來暫時(shí)剛訪問過的頂點(diǎn)。13．有向圖的遍歷不可采用廣度優(yōu)先搜索方法。14．連通圖的生成樹包含了圖中所有頂點(diǎn)。15．設(shè)G為具有n個(gè)頂點(diǎn)的連通圖，如果其中的某個(gè)子圖有n個(gè)頂點(diǎn)，n1條邊，則該子圖一定是G的生成樹。16．最小生成樹是指邊數(shù)最小的生成樹。17．從n個(gè)頂點(diǎn)的連通圖中選取n1條權(quán)值最小的邊，即可構(gòu)成最小生成樹。18．只要無向網(wǎng)中沒有權(quán)值相同的邊，其最小生成樹就是惟一的。19．只要無向網(wǎng)中有權(quán)值相同的邊，其最小生成樹就可能不是惟一的。20．有環(huán)圖也能進(jìn)行拓?fù)渑判颉?1．拓?fù)渑判蛩惴▋H適用于有向無環(huán)圖。22．任何有向無環(huán)圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃┮弧?3．關(guān)鍵路徑是由權(quán)值最大的邊構(gòu)成的。24．在AOE網(wǎng)中，減小任一關(guān)鍵活動(dòng)上的權(quán)值后，整個(gè)工期也就相應(yīng)減小。25．在AOE網(wǎng)中工程工期為關(guān)鍵活動(dòng)上權(quán)值之和。26．在關(guān)鍵路徑的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)未必在關(guān)鍵路徑上。27．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。28．所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程將提前完成。29．某些關(guān)鍵活動(dòng)若提前完成，將可能使整個(gè)工程提前完成。30．求單源最短路徑的狄克斯特拉算法不適用于有回路的有向網(wǎng)。四、簡(jiǎn)答題1．圖G是一個(gè)非連通無向圖，共有28條邊，則該圖
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1