數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題-免費(fèi)閱讀
【正文】 在這個(gè)算法中嵌套一個(gè)遞歸深度優(yōu)先搜索算法為：Dfs(AGaph G , int v)在遍歷圖的同時(shí)進(jìn)行逆序拓?fù)渑判?，其中，v是頂點(diǎn)編號(hào)。17．設(shè)計(jì)一個(gè)算法求圖的中心點(diǎn)。01234567891011121314圖71012．假設(shè)圖G采用鄰接矩陣存儲(chǔ)，采用遍歷方法實(shí)際一個(gè)有向圖的根的算法。6．設(shè)計(jì)一個(gè)算法，判斷無(wú)向圖G是否是一棵樹(shù)，若是樹(shù)，返回1；否則返回0。（5）判斷圖G中是否存在邊i,j。13．表2所示給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需的時(shí)間。四、簡(jiǎn)答題1．圖G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有多少個(gè)頂點(diǎn)？2．用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？3．對(duì)于稠密圖和稀疏圖，就存儲(chǔ)而言，采用鄰接矩陣和鄰接表哪個(gè)更好些？4．請(qǐng)回答下列關(guān)于圖的一些問(wèn)題：（1）有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊？最少有多少條邊？（2）表示一個(gè)有1000個(gè)頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素？是否為稀疏矩陣？（3）對(duì)于一個(gè)有向圖，不用拓?fù)渑判?，如何判斷圖是否存在環(huán)？5．對(duì)n個(gè)頂點(diǎn)的無(wú)向圖和有向圖，采用鄰接表表示時(shí)，如何判別下列有關(guān)問(wèn)題？（1）圖中有多少條邊？（2）任意兩個(gè)頂點(diǎn)i和j是否有邊相連？（3）任意一個(gè)頂點(diǎn)的度是多少？6．給出如圖74所示的無(wú)向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。23．關(guān)鍵路徑是由權(quán)值最大的邊構(gòu)成的。15．設(shè)G為具有n個(gè)頂點(diǎn)的連通圖，如果其中的某個(gè)子圖有n個(gè)頂點(diǎn)，n1條邊，則該子圖一定是G的生成樹(shù)。7．如果表示某個(gè)圖的鄰接矩陣不是對(duì)稱矩陣，則該圖一定是有向圖。 17．Dijkstra算法從源點(diǎn)到其它各頂點(diǎn)的路徑長(zhǎng)度按________次序依次產(chǎn)生，該算法在邊上的權(quán)出現(xiàn)_________情況時(shí)，不能正確產(chǎn)生最短路徑。9．無(wú)向圖的連通分量是指___________。A．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B．任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C．所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程提前完成D．某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提前完成二、填空題1．對(duì)于具有n個(gè)頂點(diǎn)的無(wú)向圖G最多有_________條邊。D．由n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的生成樹(shù)。A．1，2，4，3，5，7，6 B．1，2，4，3，5，6，7C．1，2，4，5，6，3，7 D．1，2，3，4，5，7，61654327 圖72 一個(gè)無(wú)向圖20．對(duì)圖72所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始進(jìn)行廣度優(yōu)先遍歷，可得到頂點(diǎn)訪問(wèn)序列______。A．入邊 B．出邊C．入邊和出邊 D．不是人邊也不是出邊12．如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則該圖一定是______。 A．n B．n＋1C．n1 D．n(n1)/24．一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含______條邊。A．n(nl) B．n(n+l) C．n(nl)/2 D．n(nl)/25．一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含______條邊。A．完全圖 B．連通圖C．有回路 D．一棵樹(shù)13．采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的______算法。A．1，3，2，4，5，6，7 B．1，2，4，3，5，6，7C．1，2，3，4，5，7，6 D．2，5，1，4，7，3，621．一個(gè)無(wú)向連通圖的生成樹(shù)是含有該連通圖的全部頂點(diǎn)的______。25．若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則可斷定該有向圖_______。2．對(duì)于具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G至少有_________條邊。 10．已知圖G的鄰接表如圖73所示，從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為_(kāi)_______，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列為_(kāi)____________。18．求從某源點(diǎn)到其余各項(xiàng)點(diǎn)的
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1