第七章復(fù)習(xí)題

第七章復(fù)習(xí)題1．圖中有關(guān)路徑的定義是（A）。

A．由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列

B．由不同頂點(diǎn)所形成的序列

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

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

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

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

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

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

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

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)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（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.拓?fù)渑判?/p>

C.求最短路徑D.求關(guān)鍵路徑12.在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)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的拓?fù)湫蛄惺牵ˋ）。

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.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（A）。A．從源點(diǎn)到匯點(diǎn)的最長路徑C．最長回路B．從源點(diǎn)到匯點(diǎn)的最短路徑D．最短回路16.下面關(guān)于求關(guān)鍵路徑的說法不正確的是（C）。

A．求關(guān)鍵路徑是以拓?fù)渑判驗榛A(chǔ)的

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

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

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

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

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

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

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

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

struct{

KeyTypekey;

OtherType

otherdata;}RecordType;typedef

struct{

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

intlength;}RecordList;基于順序結(jié)構(gòu)的算法如下：int

SeqSearch（RecordListl,KeyTypek）/*在順序表l中順序查找其關(guān)鍵字等于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)視哨法，在順序表中查找關(guā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)視哨可省去這個條件，從而提高查找效率。下面用平均查找長度來分析一下順序查找算法的性能。假設(shè)列表長度為n，那么查找第i個數(shù)據(jù)元素時需進(jìn)行n-i+1次比較，即Ci=n-i+1。又假設(shè)查找每個數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：折半查找法折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。其基本過程是：將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。圖8.1給出了用折半查找法查找12、50的具體過程，其中mid=(low+high)/2，當(dāng)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ū)間進(jìn)行查找*/elselow=mid+1;/*繼續(xù)在后半?yún)^(qū)間進(jìn)行查找*/}return(0);}折半查找過程可用一個稱為判定樹的二叉樹描述，判定樹中每一結(jié)點(diǎn)對應(yīng)表中一個記錄，但結(jié)點(diǎn)值不是記錄的關(guān)鍵字，而是記錄在表中的位置序號。根結(jié)點(diǎn)對應(yīng)當(dāng)前區(qū)間的中間記錄，左子樹對應(yīng)前一子表，右子樹對應(yīng)后一子表。顯然，找到有序表中任一記錄的過程，對應(yīng)判定樹中從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑，而所做比較的次數(shù)恰為該結(jié)點(diǎn)在判定樹上的層次數(shù)。因此，折半查找成功時，關(guān)鍵字比較次數(shù)最多不超過判定樹的深度。6319471025811具有11個元素的有序表進(jìn)行二分查找時，查找成功時的時間復(fù)雜度是什么？？由于判定樹的葉子結(jié)點(diǎn)所在層次之差最多為1，故n個結(jié)點(diǎn)的判定樹的深度與n個結(jié)點(diǎn)的完全二叉樹的深度相等，均為［log2n］+1。這樣，折半查找成功時，關(guān)鍵字比較次數(shù)最多不超過［log2n］+1。相應(yīng)地，折半查找失敗時的過程對應(yīng)判定樹中從根結(jié)點(diǎn)到某個含空指針的結(jié)點(diǎn)的路徑，因此，折半查找成功時，關(guān)鍵字比較次數(shù)最多也不超過判定樹的深度［log2n］+1。為便于討論，假定表的長度n=2h-1，則相應(yīng)判定樹必為深度是h的滿二叉樹，h=log2(n+1)。又假設(shè)每個記錄的查找概率相等，則折半查找成功時的平均查找長度為分塊查找法分塊查找法要求將列表組織成以下索引順序結(jié)構(gòu)：

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

·構(gòu)造一個索引表。其中每個索引項對應(yīng)一個塊并記錄每塊的起始位置，以及每塊中的最大關(guān)鍵字（或最小關(guān)鍵字）。索引表按關(guān)鍵字有序