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

《大數(shù)據(jù)結(jié)構(gòu)圖 作業(yè)及部分問題詳解》由會(huì)員分享，可在線閱讀，更多相關(guān)《大數(shù)據(jù)結(jié)構(gòu)圖 作業(yè)及部分問題詳解（9頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word 數(shù)據(jù)結(jié)構(gòu)習(xí)題 第七章 圖 一、 選擇題 1、一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有（ C ）條邊。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有4個(gè)頂點(diǎn)的無向完全圖有（ A ）條邊。 A、6 B、12 C、16 D、20 3、具有6個(gè)頂點(diǎn)的無向圖至少有（ A ）條邊才能保證是一個(gè)連通圖。 A、5 B、6 C、7 D、8 4、設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹的邊數(shù)為（ A ）。 A、n-1 B、n C、2n D、2n-1 5、已知一

2、個(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、acfdeb 6、采用鄰接表存儲(chǔ)的圖的深度和廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ B ）和（ D ）。 A、中序遍歷 B、先序遍歷 C、后序遍歷 D、層次遍歷 7、已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，分別根據(jù)圖的深度和廣度優(yōu)先搜索遍歷

3、算法，從頂點(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,v2 8、已知一個(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,v6 9、正確的AOE網(wǎng)必須是（ C ） A、完全圖

4、 B、哈密爾頓圖 C、無環(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,v5 11、下面結(jié)論中正確的是（ B ） A、在無向圖中，邊的條數(shù)是頂點(diǎn)度數(shù)之和。 B、在圖結(jié)構(gòu)中，頂點(diǎn)可以沒有任何前驅(qū)和后繼。 C、在n個(gè)頂點(diǎn)的無向圖中，若邊數(shù)大于n-1，則該圖必定是連通圖 D、圖的鄰接矩陣必定是對(duì)稱矩陣。 12、下面結(jié)論不

5、正確的是（ D ）。 A、無向圖的連通分量是該圖的極通子圖。 B、有向圖用鄰接矩陣表示容易實(shí)現(xiàn)求頂點(diǎn)度數(shù)的操作。 C、無向圖用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣元素之和的一半。 D、無向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的。 13、下面結(jié)論中正確的是（ C ）。 A、按深度優(yōu)先搜索遍歷圖時(shí)，與始點(diǎn)相鄰的頂點(diǎn)先于不與始點(diǎn)相鄰的頂點(diǎn)訪問。 B、一個(gè)圖按深度優(yōu)先搜索遍歷的結(jié)果是唯一的。 C、若有向圖G中包含一個(gè)環(huán)，則G的頂點(diǎn)間不存在拓?fù)渑判颉? D、圖的拓?fù)渑判蛐蛄惺俏ㄒ坏摹? 14、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊

6、數(shù)的（ C ）倍。 A、1/2 B、1 C、2 D、4 二、 填空題 1、對(duì)具有n個(gè)頂點(diǎn)的圖，其生成樹有且僅有( n-1 )條邊。 2、一個(gè)無向圖有n個(gè)頂點(diǎn)和e條邊，則所有頂點(diǎn)的度數(shù)之和為（ 2e ），其鄰接矩陣是一個(gè)關(guān)于( 對(duì)角線 )對(duì)稱的矩陣。 3、具有n個(gè)頂點(diǎn)的無向完全圖，邊的總數(shù)為（ n(n-1)/2 ）條，而有n個(gè)頂點(diǎn)的有向完全圖，邊的總數(shù)為（ n(n-1) ）條。 4、在無權(quán)圖G的鄰接矩陣A中，若(vi,vj)或屬于G的邊/弧的集合，則對(duì)應(yīng)

7、元素A[i][j]等于（ 1 ），否則等于（ 0 ），若A[i][j]=1，則A[j][i]等于（ 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.1 7、任何（ 無環(huán) ）的有向圖，其所有結(jié)點(diǎn)都可以排在一個(gè)拓?fù)湫蛄兄?，拓?fù)渑判虻姆椒ㄊ窍葟?/p>

8、圖中選一個(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)述無向圖和有向圖有哪幾種存儲(chǔ)結(jié)構(gòu)，并說明各種結(jié)構(gòu)在圖不

9、同操作中有什么優(yōu)越性？ 無向圖的存儲(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) 鄰接多重表：是無向圖的一

10、種非常有效的存儲(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、 512364 4、已知連通網(wǎng)的鄰接矩陣如圖7.3所示，頂點(diǎn)集合為{}，試畫出它所表示的從頂點(diǎn)開始利用Prim算法得到的最小生成樹。 5、圖7.4所示為一無向連通網(wǎng)絡(luò)，要求根據(jù)Kruskal算法構(gòu)造出它的最小生成樹。 圖7.4 6、對(duì)圖7.5所示的有向網(wǎng)，試?yán)肈ijkstra算法求從源點(diǎn)1到其他各頂點(diǎn)的最短路徑。 圖7.5 7、已知如圖7.6所示的AOE網(wǎng)。求： （1）每項(xiàng)活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間； （2）完成此工程最少需要多少單位時(shí)間； （3） 關(guān)鍵活動(dòng)與關(guān)鍵路徑。 9 / 9