哈爾濱工程大學(xué)考研數(shù)據(jù)結(jié)構(gòu)7

1、一 、判斷題1求最小生成樹的prim算法在邊較少、結(jié)點(diǎn)較多時(shí)效率較高。2圖的最小生成樹的形狀可能不唯一。 3用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。4鄰接表法只用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無向圖的存儲(chǔ)都適用。5任何有向網(wǎng)絡(luò)（aov-網(wǎng)絡(luò)）拓?fù)渑判虻慕Y(jié)果是唯一的。6有回路的圖不能進(jìn)行拓?fù)渑判颉?存儲(chǔ)無向圖的鄰接矩陣是對(duì)稱的，故只存儲(chǔ)鄰接矩陣的下(或上)三角部分即可。8用鄰接矩陣a表示圖，判定任意兩個(gè)結(jié)點(diǎn)vi和vj之間是否有長度為m的路徑相連，則只要檢查am的第i行第j列的元素是否為0即可。9 aoe網(wǎng)中一定只有一條

2、關(guān)鍵路徑。10關(guān)鍵路徑上活動(dòng)的工期一定能夠縮短整個(gè)工程的工期。二、選擇題1n條邊的無向圖的鄰接表的存儲(chǔ)中，邊表的個(gè)數(shù)有（ ）。a）n b）2n c）n/2 d）n*n2最短路徑的生成算法可用（ ）。a）普里姆算法 b）克魯斯卡爾算法 c）迪杰斯特拉算法 d）哈夫曼算法3有拓?fù)渑判虻膱D一定是（ ）。a）有環(huán)圖 b）無向圖 c）強(qiáng)連通圖 d）有向無環(huán)圖4圖的鄰接表如下圖所示： vertex firstedgev0 1 3 v1 0 2 3 v21 v3 0 1 （選擇題5圖） 5 點(diǎn)v0出發(fā)進(jìn)行深度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)椋?）。a）v0,v3,v2,v1 b）v0,v1,v2,v3 c）v0,

3、v2,v1,v3 d）v0,v1,v3,v26設(shè)有向圖n個(gè)頂點(diǎn)和e條邊，進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為（ ）。a）o (nlog2e) b）o (en ) c）o ( elog2n) d）o (n+e)7對(duì)于含有n個(gè)頂點(diǎn)e條邊的無向連通圖，利用kruskal算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為（ ）。a）o (elog2e) b）o (en ) c）o ( elog2n) d）o (nlog2n)8關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。a）從源點(diǎn)到匯點(diǎn)的最長路徑 b）從源點(diǎn)到匯點(diǎn)的最短路徑 c）最長的回路 d）最短的回路9n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（1）條邊。（1）a）n b）n1 c）n1 d）n（

4、n1）10設(shè)g有n個(gè)頂點(diǎn)和e條邊，進(jìn)行深度優(yōu)先搜索的時(shí)間復(fù)雜度至多為（1）。當(dāng)g是非孤立頂點(diǎn)的連通圖時(shí)有2en,故可推得深度優(yōu)先搜索的時(shí)間復(fù)雜度為（2）。 （1）a）o (ne) b）o (ne ) c）o ( elog2n) d）o (e) （2）a）o (ne) b）o (ne ) c）o ( elog2n) d）o (e)三、填空題1具有n個(gè)頂點(diǎn)的無向完全圖，邊的總數(shù)為_條；而在n個(gè)頂點(diǎn)的有向完全圖中，邊的總數(shù)為_條。2一個(gè)圖的生成樹的頂點(diǎn)是圖的_頂點(diǎn)。3寫出下圖所示的所有拓?fù)湫蛄衉。v3v0v41v2v1v5v6 (填空題5圖)4在如下圖所示的網(wǎng)絡(luò)計(jì)劃圖中關(guān)鍵路徑是_，全部計(jì)劃完成的時(shí)

5、間是_。1215 5 3 0 8171411 2 0 7.2 2 4 1613 4.5 6.5 8 （填空題9圖）5設(shè)g有n個(gè)頂點(diǎn)和e條邊，進(jìn)行廣度優(yōu)先搜索的時(shí)間復(fù)雜度至多為_。當(dāng)g是非孤立頂點(diǎn)的連通圖時(shí)有2en,故可推得廣度優(yōu)先搜索的時(shí)間復(fù)雜度為_。6一個(gè)連通圖的生成樹是一個(gè)_連通子圖，n個(gè)頂點(diǎn)的生成樹有_條邊。7對(duì)于含有n個(gè)頂點(diǎn)e條邊的無向連通圖，利用prim算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為_。四、簡答題1對(duì)于如圖所示的有向圖，試給出（1） 每個(gè)頂點(diǎn)的入度和出度； （2） 鄰接矩陣； （3） 鄰接表； （4） 逆鄰接表； （5） 強(qiáng)連通分量。 2設(shè)無向圖g如圖所示 （簡答題1圖） 試給

6、出v4v1（1） 該圖的鄰接矩陣；v6v3（2） 該圖的鄰接表；v0（3） 該圖的多重鄰接表；v5v2（4） 從a出發(fā)的“深度優(yōu)先”遍歷序列；（5） 從a出發(fā)的“廣度優(yōu)先”遍歷序列。3設(shè)有向圖g如圖所示 （簡答題2圖） 試畫出圖g的十字鏈表結(jié)構(gòu)，并寫出圖g的兩個(gè)拓?fù)湫蛄?。av5v2v41v1 8 3 5cbv3v6 2 （簡答題3圖） （簡答題4圖）4試?yán)酶ヂ逡恋拢╮.w.floyed）算法，求圖所示有向圖的各對(duì)頂點(diǎn)之間的最短路徑，并寫出在執(zhí)行算法過程中，所得的最短路徑長度矩陣序列和最短路徑矩陣序列。5下表列出了某工序之間的優(yōu)先關(guān)系和各工序所需時(shí)間，求：工序代號(hào)所需時(shí)間前序工序工序代號(hào)所需時(shí)間前序工序abcdefg15105081540300無無abc,dbehijklm15120