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

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

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

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

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

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

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

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

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

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

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

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

D．圖的深度遍歷是一個(gè)遞歸過程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)}，對(duì)該圖進(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．下面哪一方法不能判斷出一個(gè)有向圖是否有環(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)的最長(zhǎng)路徑C．最長(zhǎng)回路B．從源點(diǎn)到匯點(diǎn)的最短路徑D．最短回路16.下面關(guān)于求關(guān)鍵路徑的說法不正確的是（C）。

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

B．一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同

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

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

21.設(shè)無向圖G有n個(gè)頂點(diǎn)和e條邊，每個(gè)頂點(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)路徑上各活動(dòng)時(shí)間總和最長(zhǎng)的路徑稱為______。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)實(shí)現(xiàn)。關(guān)鍵字：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)列表中的一個(gè)或一組數(shù)據(jù)元素。如果一個(gè)關(guān)鍵字可以唯一標(biāo)識(shí)列表中的一個(gè)數(shù)據(jù)元素，則稱其為主關(guān)鍵字，否則為次關(guān)鍵字。當(dāng)數(shù)據(jù)元素僅有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，數(shù)據(jù)元素的值就是關(guān)鍵字。查找：

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

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

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

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