大數(shù)據(jù)結(jié)構(gòu)圖 作業(yè)及部分問(wèn)題詳解

word數(shù)據(jù)結(jié)構(gòu)習(xí)題第七章 圖一、 選擇題1、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有（ C ）條邊。A、n B、n(n-1) C、n(n-1)/2 D、2n2、具有4個(gè)頂點(diǎn)的無(wú)向完全圖有（ A ）條邊。A、6 B、12 C、16 D、203、具有6個(gè)頂點(diǎn)的無(wú)向圖至少有（ A ）條邊才能保證是一個(gè)連通圖。A、5 B、6 C、7 D、84、設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹的邊數(shù)為（ A ）。A、n-1 B、n C、2n D、2n-15、已知一個(gè)圖，若從頂點(diǎn)a出發(fā)進(jìn)行深度和廣度優(yōu)先搜索遍歷，則可能得到的頂點(diǎn)序列分別為（ D ）和（ B ）（1） A、abecdf B、acfebd C、acebfd D、acfdeb（2） A、abcedf B、abcefd C、abedfc D、acfdeb6、采用鄰接表存儲(chǔ)的圖的深度和廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ B ）和（ D ）。A、中序遍歷 B、先序遍歷 C、后序遍歷 D、層次遍歷7、已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，分別根據(jù)圖的深度和廣度優(yōu)先搜索遍歷算法，從頂點(diǎn)v1出發(fā)，得到的頂點(diǎn)序列分別為（ C ）和（ B ）。A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v28、已知一個(gè)圖如下，在該圖的最小生成樹中各邊上權(quán)值之和為（ C ），在該圖的最小生成樹中，從v1到v6的路徑為（ G ）。A、31B、38C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v69、正確的AOE網(wǎng)必須是（ C ）A、完全圖 B、哈密爾頓圖 C、無(wú)環(huán)圖 D、強(qiáng)連通圖10、已知一個(gè)圖如下，則由該圖得到的一種拓?fù)湫蛄袨椋?A ）。A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v511、下面結(jié)論中正確的是（ B ）A、在無(wú)向圖中，邊的條數(shù)是頂點(diǎn)度數(shù)之和。 B、在圖結(jié)構(gòu)中，頂點(diǎn)可以沒(méi)有任何前驅(qū)和后繼。 C、在n個(gè)頂點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1，則該圖必定是連通圖 D、圖的鄰接矩陣必定是對(duì)稱矩陣。12、下面結(jié)論不正確的是（ D ）。A、無(wú)向圖的連通分量是該圖的極通子圖。 B、有向圖用鄰接矩陣表示容易實(shí)現(xiàn)求頂點(diǎn)度數(shù)的操作。 C、無(wú)向圖用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣元素之和的一半。 D、無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的。13、下面結(jié)論中正確的是（ C ）。A、按深度優(yōu)先搜索遍歷圖時(shí)，與始點(diǎn)相鄰的頂點(diǎn)先于不與始點(diǎn)相鄰的頂點(diǎn)訪問(wèn)。 B、一個(gè)圖按深度優(yōu)先搜索遍歷的結(jié)果是唯一的。 C、若有向圖G中包含一個(gè)環(huán)，則G的頂點(diǎn)間不存在拓?fù)渑判颉?D、圖的拓?fù)渑判蛐蛄惺俏ㄒ坏摹?4、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ C ）倍。A、1/2 B、1 C、2 D、4二、 填空題1、對(duì)具有n個(gè)頂點(diǎn)的圖，其生成樹有且僅有( n-1 )條邊。2、一個(gè)無(wú)向圖有n個(gè)頂點(diǎn)和e條邊，則所有頂點(diǎn)的度數(shù)之和為（ 2e ），其鄰接矩陣是一個(gè)關(guān)于( 對(duì)角線 )對(duì)稱的矩陣。3、具有n個(gè)頂點(diǎn)的無(wú)向完全圖，邊的總數(shù)為（ n(n-1)/2 ）條，而有n個(gè)頂點(diǎn)的有向完全圖，邊的總數(shù)為（ n(n-1) ）條。4、在無(wú)權(quán)圖G的鄰接矩陣A中，若(vi,vj)或<vi,vj>屬于G的邊/弧的集合，則對(duì)應(yīng)元素Aij等于（ 1 ），否則等于（ 0 ），若Aij=1，則Aji等于（ 1 ）。5、已知一個(gè)圖的鄰接矩陣表示，計(jì)算第i個(gè)頂點(diǎn)的入度方法為（求矩陣第I列非零元素的和 ）6、已知圖G的鄰接表如圖7.1所示，其從頂點(diǎn)V1出發(fā)的深度優(yōu)先搜索序列為( v1,v2,v3,v6,v5,v4 )，其從頂點(diǎn)V1出發(fā)的廣度優(yōu)先搜索序列為( v1,v2,v5,v4,v3,v6 )。圖7.17、任何（ 無(wú)環(huán) ）的有向圖，其所有結(jié)點(diǎn)都可以排在一個(gè)拓?fù)湫蛄兄?，拓?fù)渑判虻姆椒ㄊ窍葟膱D中選一個(gè)（ 前趨 ）為0的結(jié)點(diǎn)且輸出，然后從圖中刪除該結(jié)點(diǎn)及其（ 所有以它為尾的弧 ），反復(fù)執(zhí)行，直到所有結(jié)點(diǎn)都輸出為止。8、在AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)各活動(dòng)時(shí)間總和最長(zhǎng)的路徑為關(guān)鍵路徑，某作業(yè)工程表示成如圖7.2所示的AOE網(wǎng)。則事件5的最早完成時(shí)間是( 15 )。事件4的最遲開始時(shí)間是( 10 )。事件5的遲緩時(shí)間是( 4 )。關(guān)鍵路徑是( 0149 )。三、 綜合題1、 簡(jiǎn)述無(wú)向圖和有向圖有哪幾種存儲(chǔ)結(jié)構(gòu)，并說(shuō)明各種結(jié)構(gòu)在圖不同操作中有什么優(yōu)越性？無(wú)向圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表和鄰接多重表，有向圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表和十字鏈表。a) 鄰接矩陣：可判定圖中任意兩個(gè)頂點(diǎn)之間是否有邊(或弧)相連，并容易求得各個(gè)頂點(diǎn)的度；此外，對(duì)于圖的遍歷也是可行的。b) 鄰接表：容易找到任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)；但要判斷任意兩個(gè)頂點(diǎn)之間是否有邊或弧相連，則需搜索第i個(gè)及第j個(gè)鏈表，這不如鄰接矩陣方便；此外，對(duì)于圖的遍歷和有向圖的拓?fù)渑判蛞彩强尚械?。c) 十字鏈表：容易找到以某頂點(diǎn)為頭或尾的弧，因此容易求得頂點(diǎn)的入度和出度；在有向圖的應(yīng)用中，十字鏈表是很有用的工具。d) 鄰接多重表：是無(wú)向圖的一種非常有效的存儲(chǔ)結(jié)構(gòu)，在其中容易求得頂點(diǎn)和邊的各種信息。2、 給出下圖鄰接表存儲(chǔ)結(jié)構(gòu)。從頂點(diǎn)1出發(fā)進(jìn)行廣度和深度優(yōu)先搜索遍歷。3、 試列出圖中全部可能的拓?fù)渑判蛐蛄?。全部可能的拓?fù)渑判蛐蛄袨椋?52364、152634、156234、561234、516234、512634、5123644、已知連通網(wǎng)的鄰接矩陣如圖7.3所示，頂點(diǎn)集合為，試畫出它所表示的從頂點(diǎn)開始利用Prim算法得到的最小生成樹。5、圖7.4所示為一無(wú)向連通網(wǎng)絡(luò)，要求根據(jù)Kruskal算法構(gòu)造出它的最小生成樹。圖7.46、對(duì)圖7.5所示的有向網(wǎng)，試?yán)肈ijkstra算法求從源點(diǎn)1到其他各頂點(diǎn)的最短路徑。圖7.57、已知如圖7.6所示的AOE網(wǎng)。求：（1）每項(xiàng)活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間；（2）完成此工程最少需要多少單位時(shí)間；（3） 關(guān)鍵活動(dòng)與關(guān)鍵路徑。9 / 9