數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題-第7章答案2014-6-16

第7章圖一、選擇題（每小題1分，共10分）1.一個n個頂點的連通無向圖，其邊的個數(shù)至少為（C）。A.n+lB.nC.n-lD.2n2.下列哪一種圖的鄰接矩陣是對稱矩陣（B）。A.有向圖B.無向圖C.AOV網(wǎng)D.AOE網(wǎng)3.為解決計算機和打印機之間速度不匹配的問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（B）。A.棧B.隊列C.樹D.圖4.設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（C）條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.2n5.無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，由頂點a開始對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點序列正確的是（D）。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b6.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用（B）來實現(xiàn)算法的。A.棧B.隊列C.樹D.圖7.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（D）。A.廣義表B.二叉樹C.圖D.棧8.下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）（B）。A.最小生成樹B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑9.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（C）倍。A.1/2B.1C.2D.10.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（B）倍。A.1/2B.1C.2D.11.有8個頂點無向圖最多有（B）條邊。A.14B.28C.56D.12.有8個頂點無向連通圖最少有（C）條邊。A.5B.6C.7D.13.有8個頂點有向完全圖有（C）條邊。A.14B.28C.56D.14.下列說法不正確的是（A）。A.圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次C.圖的深度遍歷不適用于有向圖B.遍歷的基本算法有兩種：深度遍歷和廣度遍歷D.圖的深度遍歷是一個遞歸過程二、判斷題（每小題1分，共10分）1.n個頂點的無向圖至多有n(n-1)條邊。（錯）2.在n個結(jié)點的無向圖中，若邊數(shù)大于n-1,則該圖必是連通圖。（錯）3.有e條邊的無向圖，在鄰接表中有e個結(jié)點。（錯）4.最小生成樹是指邊數(shù)最少的生成樹。（錯）5.最小生成樹問題是構(gòu)造連通網(wǎng)的最小代價生成樹。（對）6.鄰接多重表是無向圖和有向圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)。（錯）7.線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。(錯)8.拓?fù)渑判蛩惴ò岩粋€無向圖中的頂點排成一個有序序列。（錯）9.有回路的圖不能進(jìn)行拓?fù)渑判?。（對?0.關(guān)鍵路徑是AOE網(wǎng)中從源點到終點的最長路徑。（對）11.強連通圖的各頂點間均可達(dá)。（√）12.對于任意一個圖，從它的某個結(jié)點進(jìn)行一次深度或廣度優(yōu)先遍歷可以訪問到該圖的每個頂點。（×）13.拓?fù)渑判蚴前碅OE網(wǎng)中每個結(jié)點事件的最早發(fā)生時間對結(jié)點進(jìn)行排序。(×)14.圖可以沒有邊，但不能沒有頂點（√）15.在有向圖中，<vi，vj>與<vj，vi>是兩條不同的邊。（√）16.若一個無向圖以頂點V1為起點進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。（√）17.有向圖不能進(jìn)行廣度優(yōu)先遍歷。(×)18.若以某頂點開始，對有n個頂點的有向圖G進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以斷定其邊數(shù)為n-1。(×)19.鄰接表只能用于有向圖的存儲。(×)20.帶權(quán)圖的最小生成樹是唯一的。(×)21.用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。（√）三、填空題（每空1分，共10分）1.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點的個數(shù)分別為__e___和__2e__。2.一個n個頂點的連通無向圖，其邊的個數(shù)至少為n-1。3.對于一個具有n個頂點e條邊的無向圖的鄰接表，則表頭向量大小為_n_，鄰接表的邊結(jié)點個數(shù)為_2e_。4.AOE網(wǎng)中,結(jié)點（頂點）表示__事件__，邊（?。┍硎净顒?。5.AOV網(wǎng)中，結(jié)點（頂點）表示活動，邊（弧）表示活動間的優(yōu)先關(guān)系。6.圖有__鄰接矩陣__、__鄰接表__等存儲結(jié)構(gòu)；遍歷圖有_深度優(yōu)先_、_廣度優(yōu)先_等方法。四、簡答題（共10分）1.用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？答：用鄰接矩陣表示圖，矩陣元素的個數(shù)是頂點個數(shù)的平方，與邊的條數(shù)無關(guān)。矩陣中非零元素的個數(shù)與邊的條數(shù)有關(guān)。2.什么是AOE網(wǎng)？答：在現(xiàn)代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在帶權(quán)有向圖中若以頂點表示事件，有向邊表示活動，邊上的權(quán)值表示該活動持續(xù)的時間，這樣的圖簡稱為AOE網(wǎng)。3.什么是AOV網(wǎng)？答：在現(xiàn)代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在有向圖中若以頂點表示活動，有向邊表示活動之間的先后關(guān)系，這樣的圖簡稱為AOV網(wǎng)。4.什么是拓?fù)渑判?？答：簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓?fù)渑判?。離散數(shù)學(xué)中關(guān)于偏序和全序的定義：若集合X上的關(guān)系是R,且R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關(guān)系。設(shè)R是集合X上的偏序（PartialOrder）,如果對每個x,y屬于X必有xRy或yRx，則稱R是集合X上的全序關(guān)系。比較簡單的理解：偏序是指集合中只有部分成員可以比較，全序是指集合中所有的成員之間均可以比較。5.簡述圖的遍歷的含義，其遍歷方法目前主要有哪兩種？其基本思想是什么？答：圖的遍歷是指從圖中某一頂點出發(fā)，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。（從圖中的任一頂點出發(fā)，對圖中的所有頂點訪問一次且只訪問一次。）其遍歷方法目前主要有深度優(yōu)先搜索法和廣度（寬度）優(yōu)先搜索法兩種算法。深度優(yōu)先搜索法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0出發(fā)，訪問v0，然后選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發(fā)選擇一個與vi相鄰且未被訪問的頂點vj進(jìn)行訪問，依次繼續(xù)。如果當(dāng)前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最后一個擁有未被訪問的相鄰頂點的頂點w，從w出發(fā)按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。圖的廣度優(yōu)先搜索是樹的按層次遍歷的推廣，