數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題(已修改)
2025-04-06 03:01 本頁面
【正文】 第7章 圖一、單項選擇題1．在一個無向圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的______倍。 A．l/2 B．1 C．2 D．42．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的______倍。A．l/2 B．1 C．2 D．43．一個具有n個頂點的無向圖最多包含______條邊。 A．n B．n＋1C．n1 D．n(n1)/24．一個具有n個頂點的無向完全圖包含______條邊。A．n(nl) B．n(n+l) C．n(nl)/2 D．n(nl)/25．一個具有n個頂點的有向完全圖包含______條邊。A．n(n1) B．n(n+l) C．n(nl)/2 D．n(n+l)/26．對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為______。A．n B．nn C．n1 D．(nl) (nl)7．無向圖的鄰接矩陣是一個______。A．對稱矩陣 B．零矩陣 C．上三角矩陣 D．對角矩陣8．對于一個具有n個頂點和e條邊的無(有)向圖，若采用鄰接表表示，則表頭向量的大小為______。A．n B．e C．2n D．2e9．對于一個具有n個頂點和e條邊的無(有)向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為______。A．n B．e C．2n D．2e10．在有向圖的鄰接表中，每個頂點鄰接表鏈接著該頂點所有______鄰接點。A．入邊 B．出邊 C．入邊和出邊 D．不是入邊也不是出邊11．在有向圖的逆鄰接表中，每個頂點鄰接表鏈接著該頂點所有______鄰接點。A．入邊 B．出邊C．入邊和出邊 D．不是人邊也不是出邊12．如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是______。A．完全圖 B．連通圖C．有回路 D．一棵樹13．采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的______算法。A．先序遍歷 B．中序遍歷C．后序遍歷 D．按層遍歷14．采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的______算法。A．先序遍歷 B．中序遍歷C．后序遍歷 D．按層遍歷15．如果無向圖G必須進行二次廣度優(yōu)先搜索才能訪問其所有頂點，則下列說法中不正確的是______。A．G肯定不是完全圖 B．G一定不是連通圖C．G中一定有回路 D．G有二個連通分量16．下列有關(guān)圖遍歷的說法不正確的是______。A．連通圖的深度優(yōu)先搜索是一個遞歸過程 B．圖的廣度優(yōu)先搜索中鄰接點的尋找具有“先進先出”的特征 C．非連通圖不能用深度優(yōu)先搜索法 D．圖的遍歷要求每一頂點僅被訪問一次17．下列說法中不正確的是______。A．無向圖中的極大連通子圖稱為連通分量 B．連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點 C．圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點 D．有向圖的遍歷不可采用廣度優(yōu)先搜索方法18．一個有向圖G的鄰接表存儲如下圖71所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點v1出發(fā)，所得到的頂點序列是______。A．v1，v2，v3，v4，v5 B．v1，v2，v3，v5，v4C．v1，v2，v4，v5，v3 D．
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1