第七章復習題1．圖中有關路徑的定義是（A）。

A．由頂點和相鄰頂點序偶構成的邊所形成的序列

B．由不同頂點所形成的序列

C．由不同邊所形成的序列D．上述定義都不是2．設無向圖的頂點個數(shù)為n，則該圖最多有（B）條邊。

A．n-1B．n(n-1)/2C．n(n+1)/2

D．n23．一個n個頂點的連通無向圖，其邊的個數(shù)至少為（A）。

A．n-1B．nC．n+1D．nlogn4．要連通具有n個頂點的有向圖，至少需要（B）條邊。

A．n-lB．nC．n+lD．2n5．n個結點的完全有向圖含有邊的數(shù)目（D）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一個有n個結點的圖，最少有（B）個連通分量，最多有（D）個連通分量。A．0B．1C．n-1D．N7．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（B）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（C）倍。A．1/2B．2C．1D．48．下列哪一種圖的鄰接矩陣一定是對稱矩陣？（B）A．有向圖B．無向圖

C．AOV網(wǎng)D．AOE網(wǎng)9.下列說法不正確的是（C）。

A．圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次

B．遍歷的基本算法有兩種：深度遍歷和廣度遍歷C．圖的深度遍歷不適用于有向圖

D．圖的深度遍歷是一個遞歸過程10．無向圖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)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（D）

A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,d

C．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b11．下面哪一方法不能判斷出一個有向圖是否有環(huán)（C）：A．深度優(yōu)先遍歷B.拓撲排序

C.求最短路徑D.求關鍵路徑12.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是（D）。A．G中有弧<Vi，Vj>B．G中有一條從Vi到Vj的路徑C．G中沒有弧<Vi,Vj>D．G中有一條從Vj到Vi的路徑

14．已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓撲序列是（A）。

A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V715.關鍵路徑是事件結點網(wǎng)絡中（A）。A．從源點到匯點的最長路徑C．最長回路B．從源點到匯點的最短路徑D．最短回路16.下面關于求關鍵路徑的說法不正確的是（C）。

A．求關鍵路徑是以拓撲排序為基礎的

B．一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同

C．一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差（改為發(fā)生）

D．關鍵活動一定位于關鍵路徑上17．下列關于AOE網(wǎng)的敘述中，不正確的是（B）。A．關鍵活動不按期完成就會影響整個工程的完成時間B．任一個關鍵活動提前完成，整個工程都將會提前完成C．所有的關鍵活動提前完成，則整個工程將會提前完成D．某些關鍵活動提前完成，會使整個工程提前完成18.G是一個非連通無向圖，共有28條邊，則該圖至少有__9____個頂點。19．如果含n個頂點的圖形形成一個環(huán)，則它有___n___棵生成樹。20.為了實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標志數(shù)組標志已訪問的圖的結點外，還需___隊列___存放被訪問的結點以實現(xiàn)遍歷。

21.設無向圖G有n個頂點和e條邊，每個頂點Vi的度為di（1<=i<=n〉，則e=__di____

22.Prim（普里姆）算法適用于求______的網(wǎng)的最小生成樹；kruskal（克魯斯卡爾）算法適用于求______的網(wǎng)的最小生成樹。23.AOV網(wǎng)中,結點表示______,邊表示______。AOE網(wǎng)中,結點表示______,邊表示______。24.有向圖G可拓撲排序的判別條件是_圖中無環(huán)_____。25.在AOE網(wǎng)中，從源點到匯點路徑上各活動時間總和最長的路徑稱為______。26.已知一無向圖G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是______遍歷方法。查找的基本概念

列表：由同一類型的數(shù)據(jù)元素（或記錄）構成的集合，可利用任意數(shù)據(jù)結構實現(xiàn)。關鍵字：數(shù)據(jù)元素的某個數(shù)據(jù)項的值，用它可以標識列表中的一個或一組數(shù)據(jù)元素。如果一個關鍵字可以唯一標識列表中的一個數(shù)據(jù)元素，則稱其為主關鍵字，否則為次關鍵字。當數(shù)據(jù)元素僅有一個數(shù)據(jù)項時，數(shù)據(jù)元素的值就是關鍵字。查找：

根據(jù)給定的關鍵字值，在特定的列表中確定一個其關鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。若找到相應的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找是失敗的，此時應返回空地址及失敗信息，并可根據(jù)要求插入這個不存在的數(shù)據(jù)元素。顯然，查找算法中涉及到三類參量：①查找對象K（找什么）；②查找范圍L（在哪找）；③K在L中的位置（查找的結果）。其中①、②為輸入?yún)⒘浚蹫檩敵鰠⒘?，在函?shù)中，輸入?yún)⒘勘夭豢缮?，輸出參量也可用函?shù)返回值表示。

平均查找長度：為確定數(shù)據(jù)元素在列表中的位置，需和給定值進行比較的關鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。對于長度為n的列表，查找成功時的平均查找長度為：其中Pi為查找列表中第i個數(shù)據(jù)元素的概率，Ci為找到列表中第i個數(shù)據(jù)元素時，已經(jīng)進行過的關鍵字比較次數(shù)。由于查找算法的基本運算是關鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能。查找的基本方法可以分為兩大類，即比較式查找法和計算式查找法。其中比較式查找法又可以分為基于線性表的查找法和基于樹的查找法，而計算式查找法也稱為HASH（哈希）查找法。順序查找法順序查找法的特點是，用所給關鍵字與線性表中各元素的關鍵字逐個比較，直到成功或失敗。存儲結構通常為順序結構，也可為鏈式結構。下面給出順序結構有關數(shù)據(jù)類型定義：＃defineLIST_SIZE20typedef

struct{

KeyTypekey;

OtherType

otherdata;}RecordType;typedef

struct{

RecordTyper［LIST-SIZE+1］;/*r［0］為工作單元*/

intlength;}RecordList;基于順序結構的算法如下：int

SeqSearch（RecordListl,KeyTypek）/*在順序表l中順序查找其關鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0*/{

l.r［0］.key=k;i=l.length;while(l.r［i］.key!=k)i--;return（i）;}其中l(wèi).r［0］稱為監(jiān)視哨，可以起到防止越界的作用。不用監(jiān)視哨的算法如下：int

SeqSearch（RecordListl,KeyTypek）/*不用監(jiān)視哨法，在順序表中查找關鍵字等于k的元素*/{i=l.length;while(i>=1&&l.r［i］.key!=k)i--;if(i>=1)return（i）

elsereturn(0);}其中，循環(huán)條件i>=1判斷查找是否越界。利用監(jiān)視哨可省去這個條件，從而提高查找效率。下面用平均查找長度來分析一下順序查找算法的性能。假設列表長度為n，那么查找第i個數(shù)據(jù)元素時需進行n-i+1次比較，即Ci=n-i+1。又假設查找每個數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：折半查找法折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關鍵字大小有序排列的順序表。其基本過程是：將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。圖8.1給出了用折半查找法查找12、50的具體過程，其中mid=(low+high)/2，當high<low時，表示不存在這樣的子表空間，查找失敗。折半查找的算法如下：int

BinSrch

（SqListl,KeyTypek）{low=1;high=l.length;/*置區(qū)間初值*/while(low<=high){ mid=(low+high)/2;if(k==l.r［mid］.key)return（mid）;/*找到待查元素*/elseif(k<l.r［mid］.key)high=mid-1;/*未找到，則繼續(xù)在前半?yún)^(qū)間進行查找*/elselow=mid+1;/*繼續(xù)在后半?yún)^(qū)間進行查找*/}return(0);}折半查找過程可用一個稱為判定樹的二叉樹描述，判定樹中每一結點對應表中一個記錄，但結點值不是記錄的關鍵字，而是記錄在表中的位置序號。根結點對應當前區(qū)間的中間記錄，左子樹對應前一子表，右子樹對應后一子表。顯然，找到有序表中任一記錄的過程，對應判定樹中從根結點到與該記錄相應的結點的路徑，而所做比較的次數(shù)恰為該結點在判定樹上的層次數(shù)。因此，折半查找成功時，關鍵字比較次數(shù)最多不超過判定樹的深度。6319471025811具有11個元素的有序表進行二分查找時，查找成功時的時間復雜度是什么？？由于判定樹的葉子結點所在層次之差最多為1，故n個結點的判定樹的深度與n個結點的完全二叉樹的深度相等，均為［log2n］+1。這樣，折半查找成功時，關鍵字比較次數(shù)最多不超過［log2n］+1。相應地，折半查找失敗時的過程對應判定樹中從根結點到某個含空指針的結點的路徑，因此，折半查找成功時，關鍵字比較次數(shù)最多也不超過判定樹的深度［log2n］+1。為便于討論，假定表的長度n=2h-1，則相應判定樹必為深度是h的滿二叉樹，h=log2(n+1)。又假設每個記錄的查找概率相等，則折半查找成功時的平均查找長度為分塊查找法分塊查找法要求將列表組織成以下索引順序結構：

·首先將列表分成若干個塊（子表）。一般情況下，塊的長度均勻，最后一塊可以不滿。每塊中元素任意排列，即塊內(nèi)無序，但塊與塊之間有序。

·構造一個索引表。其中每個索引項對應一個塊并記錄每塊的起始位置，以及每塊中的最大關鍵字（或最小關鍵字）。索引表按關鍵字有序