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

2017～2018學(xué)年度第2學(xué)期《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)提綱一、單項(xiàng)選擇題題號(hào)12345678910答案CADCABABCD題號(hào)11121314151617181920答案AADAADCBAB1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為_(kāi)________兩類。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2．鏈表不具有的特點(diǎn)是_________。A．可隨機(jī)訪問(wèn)任一元素 B．插入、刪除不需要移動(dòng)的元素C．不必事先估計(jì)存儲(chǔ)空間 D．所需空間與線性表長(zhǎng)度成正比3．若線性表最常用的運(yùn)算是存取第i個(gè)元素及其前驅(qū)元素，則采用_________存儲(chǔ)方式節(jié)省時(shí)間。A．單鏈表 B．雙鏈表 C．循環(huán)單鏈表 D．順序表4．算法分析的目的是_________。A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出關(guān)系C．分析算法的效率以求改進(jìn) D．分析算法的易讀性和文檔性5．若一個(gè)棧用數(shù)組data[1..n]存儲(chǔ)，初始棧頂指針top為0，則以下元素x進(jìn)棧的操作正確的是_________。A．top++;data[top]=x; B．data[top]=x;top++;C．top--;data[top]=x; D．data[top]=x;top--;6．表達(dá)式a*(b+c)-d的后綴表達(dá)式是_________。A．a(chǎn)bcd*+- B．a(chǎn)bc+*d- C．a(chǎn)bc*+d- D．-+*abcd7．遞歸函數(shù)f(1)=1，f(n)=f(n-1)+n(n＞1)的遞歸出口是_________。A．f(1)=1 B．f(1)=0 C．f(0)=0 D．f(n)=n8．將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用_________保存中間結(jié)果。A．隊(duì)列 B．棧 C．鏈表 D．樹(shù)9．對(duì)稀疏矩陣采用壓縮存儲(chǔ)，其缺點(diǎn)之一是_________。A．無(wú)法判斷矩陣有多少行、多少列B．無(wú)法根據(jù)行、列號(hào)查找某個(gè)矩陣元素C．無(wú)法根據(jù)行、列號(hào)直接計(jì)算矩陣元素的存儲(chǔ)地址D．使矩陣元素之間的邏輯關(guān)系更加復(fù)雜10．一個(gè)n階上三角矩陣a按行優(yōu)先順序壓縮存放在一維數(shù)組b中，則b中的元素個(gè)數(shù)是_________。A．n B．n2 C．n(n+1)/2 D．n(n+1)/2+111．度為4，高度為h的樹(shù)_________。A．至少有h+3個(gè)結(jié)點(diǎn) B．最多有4h-1個(gè)結(jié)點(diǎn)C．最多有4h個(gè)結(jié)點(diǎn) D．至少有h+4個(gè)結(jié)點(diǎn)12．用雙親存儲(chǔ)結(jié)構(gòu)表示樹(shù)，其優(yōu)點(diǎn)之一是比較方便_________。A．找指定結(jié)點(diǎn)的雙親結(jié)點(diǎn) B．找指定結(jié)點(diǎn)的孩子結(jié)點(diǎn)C．找指定結(jié)點(diǎn)的兄弟結(jié)點(diǎn) D．判斷某結(jié)點(diǎn)是不是葉子結(jié)點(diǎn)13．設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹(shù)，則該哈夫曼樹(shù)共有_________個(gè)結(jié)點(diǎn)。A．13 B．12 C．26 D．2514．無(wú)向圖的鄰接矩陣是一個(gè)_________。A．對(duì)稱矩陣 B．零矩陣 C．上三角矩陣 D．對(duì)角矩陣15．在圖的廣度優(yōu)先遍歷算法中用到一個(gè)隊(duì)列，每個(gè)頂點(diǎn)最多進(jìn)隊(duì)_________次。A．1 B．2 C．3 D．不確定16．在用Prim和Kruskal算法構(gòu)造最小生成樹(shù)時(shí)，前者更適合于_________。A．有向圖 B．無(wú)向圖 C．稀疏圖 D．稠密圖17．有一個(gè)有序表R[1..13]={1,3,9,12,32,41,45,62,75,77,82,95,100}，當(dāng)用二分查找法查找值為82的節(jié)點(diǎn)時(shí)，經(jīng)過(guò)_________次比較后查找成功。A．1 B．2 C．4 D．818．在采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊，則每塊分為_(kāi)________個(gè)結(jié)點(diǎn)最佳。A．9 B．25 C．6 D．62519．若R中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用_________方法最節(jié)省時(shí)間。A．堆排序 B．希爾排序 C．快速排序 D．基數(shù)排序20．有一組序列（48,36,68,99,75,24,28,52）進(jìn)行快速排序，要求結(jié)果從小到大排序，則進(jìn)行一次劃分之后的結(jié)果為_(kāi)________。A．[242836]48[52687599] B．[283624]48[75996852]C．[366899]48[75242852] D．[283624]48[99756852]二、填空題題號(hào)答案題號(hào)答案題號(hào)答案1問(wèn)題規(guī)模2O(n)3假溢出42855462h-17關(guān)鍵活動(dòng)8無(wú)環(huán)圖9RL10基數(shù)排序1．在分析算法的時(shí)間復(fù)雜度時(shí)，通常認(rèn)為算法的執(zhí)行時(shí)間是_________的函數(shù)。2．求一個(gè)雙鏈表長(zhǎng)度的算法的時(shí)間復(fù)雜度為_(kāi)________。3．在實(shí)現(xiàn)順序隊(duì)的時(shí)候，通常將數(shù)組看成是一個(gè)首尾相連的環(huán)，這樣做的目的是為了避免產(chǎn)生_____現(xiàn)象。4．有如下遞歸過(guò)程：voidreverse(intm){printf("%d",n%10);if(n/10!=0)reverse(n/10);}調(diào)用語(yǔ)句reverse(582)的結(jié)果是_________。5．廣義表(((a,b,(),c),d),e,((f),g))的深度是_________。6．在高度為h（h≥0）的二叉樹(shù)中最多有_________個(gè)結(jié)點(diǎn)。7．AOE網(wǎng)中從源點(diǎn)到匯點(diǎn)長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑，該路徑上的活動(dòng)稱為_(kāi)________。8．可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是_________。9．輸入序列為（20，35，30，……），構(gòu)造一棵平衡二叉樹(shù)，其中的第一次調(diào)整為_(kāi)________型調(diào)整。10．在排序過(guò)程中，任何情況下都不比較關(guān)鍵字大小的排序方法是_________。三、判斷題題號(hào)12345678910答案FTFFFTFTFF1．如果數(shù)據(jù)元素值發(fā)生改變，則數(shù)據(jù)的邏輯結(jié)構(gòu)也隨之改變。 （）2．在循環(huán)單鏈表中沒(méi)有為空的指針域。 （）3．順序棧中元素值的大小是有序的。 （）4．任何遞歸算法都是尾遞歸。 （）5．稀疏矩陣的特點(diǎn)是矩陣中元素較少。 （）6．哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)。 （）7．完全二叉樹(shù)中的每個(gè)結(jié)點(diǎn)或者沒(méi)有孩子或者有兩個(gè)孩子。 （）8．強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。 （）9．哈希沖突是指同一個(gè)關(guān)鍵字的記錄對(duì)應(yīng)多個(gè)不同的哈希地址。 （）10．任何情況下折半插入排序都優(yōu)于直接插入排序。 （）四、問(wèn)答題 1．設(shè)計(jì)一個(gè)算法，刪除一個(gè)單鏈表L中元素值最大的結(jié)點(diǎn)（假設(shè)這樣的結(jié)點(diǎn)唯一）。voiddelmaxnode(LinkList*&L){LinkList*p,*pre,*maxp,*maxpre;p=L->next;pre=L;maxp=p;maxpre=pre;while(p!=NULL){if(maxp->data<p->data){maxp=p;maxpre=pre;}pre=p;p=p->next;}maxpre->next=maxp->next;free(maxp);}2．已知一棵完全二叉樹(shù)的第6層（設(shè)根為第1層）有8個(gè)葉子結(jié)點(diǎn)，則該完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是多少。完全二叉樹(shù)的葉子結(jié)點(diǎn)只能在最下兩層，對(duì)于本題，結(jié)點(diǎn)最多的情況是第6層為倒數(shù)第二層，即1~6層構(gòu)成一個(gè)滿二叉樹(shù)，其結(jié)點(diǎn)總數(shù)為26-1=63。第6層有25=32個(gè)結(jié)點(diǎn)，其中含8個(gè)葉子結(jié)點(diǎn)，另外有32-8=24個(gè)非葉子結(jié)點(diǎn)，它們中的每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)（均為第7層的葉子結(jié)點(diǎn)），計(jì)48個(gè)葉子結(jié)點(diǎn)，這樣最多的結(jié)點(diǎn)個(gè)數(shù)=63+48=111。3．一個(gè)有向圖G的鄰接表存儲(chǔ)如下圖所示，要求：（1）給出該圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)；（2）給出該圖的所有強(qiáng)連通分量。4．什么是平衡二叉樹(shù)？輸入關(guān)鍵字序列（16，3，7，11），給出構(gòu)造一棵平衡二叉樹(shù)的過(guò)程。若一棵二叉排序樹(shù)中每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度最多相差1，則稱此二叉樹(shù)為平衡二叉樹(shù)。16160161307030160161110307-15．線性表有順序表和鏈表兩種存儲(chǔ)方式，不同的排序方法適合不同的存儲(chǔ)結(jié)構(gòu)。對(duì)于常見(jiàn)的內(nèi)部排序方法，說(shuō)明哪些更適合于順序表，哪些更適合于鏈表？哪些兩者都適合？更適合于順序表的排序方法有希爾排序、折半插入排序、快速排序、堆排序和歸并排序。更適合于鏈表的排序方法是基數(shù)排序兩者都適合的排序方法有直接插入排序、冒泡排序和簡(jiǎn)單排序。五、算法設(shè)計(jì)題用Floyd算法計(jì)算圖中任意兩個(gè)頂點(diǎn)之間的最短路徑。voidFloyd(MGraphg){intA[MAXV][MAXV],path[MAXV][MAXV];inti,j,k;for(i=0;i<g.n;i++)for(j=0;j<g.n;j++){A[i][j]=g.edges[i][j];path[i][j]=-1;}for(k=0;k<g.n;k++){for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)if(A[i][j]>A[i][k]+A[k][j]){A[i][j]=A[i][k]+A[k][j];path[i][j]=k; //修改最短路徑}}Dispath(A,path,g.n); //輸出最短路徑}

一、選擇題研究數(shù)據(jù)結(jié)構(gòu)就是研究（）。A數(shù)據(jù)的邏輯結(jié)構(gòu)B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C數(shù)據(jù)的邏輯和存儲(chǔ)結(jié)構(gòu)D數(shù)據(jù)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn)鏈表不具有的特點(diǎn)是（）。A可隨機(jī)訪問(wèn)任一元素B插入刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性表長(zhǎng)度成正比設(shè)一個(gè)棧的輸入序列為1，2，3，4，則借助一個(gè)棧所得到的輸出序列不可能是（）。A1，2，3，4B2，4，3，1C3，1，4，2D3，2，4，1設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲(chǔ)結(jié)構(gòu)B棧C線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D隊(duì)列表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。Aabcd*+-Babc+*d-Cabc*+d-D-+*abcd隊(duì)列的操作原則是（）。A先進(jìn)先出B只能進(jìn)行插入C后進(jìn)先出 D只能進(jìn)行刪除判斷帶頭結(jié)點(diǎn)的單鏈表llist為空的條件是（）。Allist->link==llistBllist==NULLCllist->link==NULLDllist!=NULL一個(gè)具有20個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其葉結(jié)點(diǎn)個(gè)數(shù)為（）。A9B10C11D12下列不屬于內(nèi)部排序的算法是（）。A歸并排序B拓?fù)渑判駽選擇排序D插入排序在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為2，度為2的結(jié)點(diǎn)數(shù)為1，則葉結(jié)點(diǎn)數(shù)為（）。A4B5C6D712345678910DACBBACBBC二、填空題第7章圖 數(shù)據(jù)結(jié)構(gòu)作業(yè)答案PAGE13已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少是99。在一個(gè)長(zhǎng)度為n的線性表的第i個(gè)元素（1≦i≦n）之前插入一個(gè)元素時(shí)，插入函數(shù)需向后移動(dòng)n-i+1個(gè)元素。若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。若某線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占2個(gè)存儲(chǔ)單元，首地址為是100，則第5個(gè)元素的地址是108。若結(jié)點(diǎn)y是結(jié)點(diǎn)x的一棵子樹(shù)的根，則x稱作y的父結(jié)點(diǎn)。一個(gè)串中包括的字符個(gè)數(shù)稱作這個(gè)串的長(zhǎng)度。一棵樹(shù)高為h的完全二叉樹(shù)至少有2h-1個(gè)結(jié)點(diǎn)，至多有2h-1個(gè)結(jié)點(diǎn)。算法的復(fù)雜性分析主要從算法的時(shí)間復(fù)雜性和空間復(fù)雜性進(jìn)行考慮。數(shù)據(jù)結(jié)構(gòu)主要根據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)進(jìn)行分類。圖的遍歷分為兩種類型：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。三、算法分析與設(shè)計(jì)題在鏈表中，若已知指針p，要在指針p所指的結(jié)點(diǎn)之后插入數(shù)據(jù)域值相繼為a和b的兩個(gè)結(jié)點(diǎn)，已知指針s指向結(jié)點(diǎn)a。寫(xiě)出實(shí)現(xiàn)上述插入操作的關(guān)鍵語(yǔ)句。ABABDCEFs->next->next=p->next;p->next=s;如圖所示的一棵二叉樹(shù)，寫(xiě)出對(duì)此樹(shù)的先根序列、中根序列和后根序列。先根序列：ABDEFC中根序列：DEFBAC后根序列：FEDBCA以{5，6，7，8，9，10，15，18，22}作為葉結(jié)點(diǎn)的權(quán)值來(lái)構(gòu)造一棵Huffman樹(shù)。100100415919263311152291065871815請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，求出循環(huán)表中結(jié)點(diǎn)的個(gè)數(shù)。intCountnode(ClinkListclist){intn；PNodep；p=clist->link；n=0；while(p!=clist){n++；p=p->link；}return(++n)；}

一、填空題1．設(shè)有一個(gè)8階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式,按行優(yōu)先順序存儲(chǔ)方式。設(shè)a11為第一個(gè)元素,其存儲(chǔ)地址為1,假設(shè)每個(gè)元素占用1個(gè)存儲(chǔ)單元,則a64的存儲(chǔ)地址為19。2．若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3．算法的5個(gè)重要特征是有窮性、確定性、可行性、輸入和輸出。4.每次從無(wú)序子表中取出一個(gè)元素，然后把它插入到有序子表的適當(dāng)位置，則此種排序方法叫做直接插入排序。5．設(shè)二維數(shù)組A[1..M，1..N]（即M行N列）按行優(yōu)先順序存儲(chǔ)在一維數(shù)組B[1..M*N]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為(i-1)*N+j。6．在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要進(jìn)行4次元素之間的比較。7．一棵樹(shù)高為h的完全二叉樹(shù)至少有2h-1個(gè)結(jié)點(diǎn)，至多有2h-1個(gè)結(jié)點(diǎn)。8．由權(quán)值分別為11,8,6,2,5的葉結(jié)點(diǎn)生成一棵Huffman樹(shù)，它的帶權(quán)路徑長(zhǎng)度為71。9．對(duì)關(guān)鍵字序列(52,80,63,44,48,91)一趟快速排序后的結(jié)果(48，44，52，63，80，91)。二、單項(xiàng)選擇題題號(hào)12345678910答案DAAACBDBAC題號(hào)11121314151617181920答案CAADDCDAAC1.數(shù)據(jù)結(jié)構(gòu)是指。A.一種數(shù)據(jù)類型B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C.一組性質(zhì)相同的數(shù)據(jù)元素的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2.以下算法的時(shí)間復(fù)雜度為。voidfun(intn){ inti=1; while(i<=n) i++;}A.O(n) B.O()C.O(nlog2n) D.O(log2n)3.在一個(gè)長(zhǎng)度為n的有序順序表中刪除元素值為x的元素時(shí)，在查找元素x時(shí)采用二分查找，此時(shí)的時(shí)間復(fù)雜度為。A.O(n) B.O(nlog2n)C.O(n2) D.O()4.在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表L中，刪除元素值為x的結(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為。A.O(n) B.O()C.O(nlog2n) D.O(n2)5.若一個(gè)棧采用數(shù)組s[0..n-1]存放其元素，初始時(shí)棧頂指針為n，則以下元素x進(jìn)棧的正確操作是。A.top++;s[top]=x; B.s[top]=x;top++;C.top--;s[top]=x; B.s[top]=x;top--;6.中綴表達(dá)式“2*(3+4)-1”的后綴表達(dá)式是，其中#表示一個(gè)數(shù)值的結(jié)束。A.2#3#4#1#*+- B.2#3#4#+*1#-C.2#3#4#*+1#- D.-+*2#3#4#1#7.設(shè)環(huán)形隊(duì)列中數(shù)組的下標(biāo)為0～N-1，其隊(duì)頭、隊(duì)尾指針?lè)謩e為front和rear（front指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置），則其元素個(gè)數(shù)為。A.rear-front B.rear-front-1C.(rear-front)％N+1 D.(rear-front+N)％N8.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)環(huán)形隊(duì)列，隊(duì)頭指針front指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置。若當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為。A.1和5 B.2和4C.4和2 D.5和19.一棵深度為h（h≥1）的完全二叉樹(shù)至少有個(gè)結(jié)點(diǎn)。A.2h-1 B.2hC.2h+1 D.2h-1+110.一棵含有n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)中，其線索個(gè)數(shù)為。A.2n B.n-1C.n+1 D.n11.設(shè)一棵哈夫曼樹(shù)中有1999個(gè)結(jié)點(diǎn)，該哈夫曼樹(shù)用于對(duì)個(gè)字符進(jìn)行編碼。A.999 B.998C.1000 D.100112.一個(gè)含有n個(gè)頂點(diǎn)的無(wú)向連通圖采用鄰接矩陣存儲(chǔ)，則該矩陣一定是。A.對(duì)稱矩陣 B.非對(duì)稱矩陣C.稀疏矩陣 D.稠密矩陣13.設(shè)無(wú)向連通圖有n個(gè)頂點(diǎn)e條邊，若滿足，則圖中一定有回路。A.e≥n B.e<nC.e=n-1 D.2e≥n14.對(duì)于AOE網(wǎng)的關(guān)鍵路徑，以下敘述是正確的。A.任何一個(gè)關(guān)鍵活動(dòng)提前完成，則整個(gè)工程一定會(huì)提前完成B.完成整個(gè)工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最短路徑長(zhǎng)度C.一個(gè)AOE網(wǎng)的關(guān)鍵路徑一定是唯一的D.任何一個(gè)活動(dòng)持續(xù)時(shí)間的改變可能會(huì)影響關(guān)鍵路徑的改變15.設(shè)有100個(gè)元素的有序表，用折半查找時(shí)，不成功時(shí)最大的比較次數(shù)是。A.25 B.50C.10 D.716.在一棵m階B-樹(shù)中刪除一個(gè)關(guān)鍵字會(huì)引起合并，則該結(jié)點(diǎn)原有個(gè)關(guān)鍵字。A.1 B.m/2C.m/2-1 D.m/2+117.哈希查找方法一般適用于情況下的查找。A.查找表為鏈表B.查找表為有序表C.關(guān)鍵字集合比地址集合大得多D.關(guān)鍵字集合與地址集合之間存在著某種對(duì)應(yīng)關(guān)系。18.對(duì)含有n個(gè)元素的順序表采用直接插入排序方法進(jìn)行排序，在最好情況下算法的時(shí)間復(fù)雜度為。A.O(n) B.O(nlog2n)C.O(n2) D.O()19.用某種排序方法對(duì)數(shù)據(jù)序列{24,88,21,48,15,27,69,35,20}進(jìn)行遞增排序，元素序列的變化情況如下：（1）{24,88,21,48,15,27,69,35,20}（2）{20,15,21,24,48,27,69,35,88}（3）{15,20,21,24,35,27,48,69,88}（4）{15,20,21,24,27,35,48,69,88}則所采用的排序方法是。A.快速排序 B.簡(jiǎn)單選擇排序C.直接插入排序 D.歸并排序20.以下序列是堆的是。A.{75,65,30,15,25,45,20,10} B.{75,65,45,10,30,25,20,15}C.{75,45,65,30,15,25,20,10} D.{75,45,65,10,25,30,20,15}三、問(wèn)答題1.有一棵二叉排序樹(shù)按先序遍歷得到的序列為：(12,5,2,8,6,10,16,15,18,20)?；卮鹨韵聠?wèn)題：（1）畫(huà)出該二叉排序樹(shù)。（2）給出該二叉排序樹(shù)的中序遍歷序列。（3）求在等概率下的查找成功和不成功情況下的平均查找長(zhǎng)度。答：（1）先序遍歷得到的序列為：(12,5,2,8,6,10,16,15,18,20)，中序序列是一個(gè)有序序列，所以為：(2,5,6,8,10,12,15,16,18,20)，由先序序列和中序序列可以構(gòu)造出對(duì)應(yīng)的二叉樹(shù)，如圖所示。（2）中序遍歷序列為：2,5,6,8,10,12,15,16,18,20。（3）ASL成功=(1×1+2×2+4×3+3×4)/10=29/10。ASL不成功=(5×3+6×4)/11=39/11。2.有人提出這樣的一種從圖G中頂點(diǎn)u開(kāi)始構(gòu)造最小生成樹(shù)的方法：假設(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖，T=(U，TE)是G的最小生成樹(shù)，其中U是T的頂點(diǎn)集，TE是T的邊集，則由G構(gòu)造從起始頂點(diǎn)u出發(fā)的最小生成樹(shù)T的步驟如下：（1）初始化U={u}。以u(píng)到其他頂點(diǎn)的所有邊為候選邊。（2）重復(fù)以下步驟n-1次，使得其他n-1個(gè)頂點(diǎn)被加入到U中。從候選邊中挑選權(quán)值最小的邊加入到TE，設(shè)該邊在V-U中的頂點(diǎn)是v，將v加入U(xiǎn)中?？疾轫旤c(diǎn)v，將v與V-U頂點(diǎn)集中的所有邊作為新的候選邊。若此方法求得的T是最小生成樹(shù)，請(qǐng)予以證明。若不能求得最小邊，請(qǐng)舉出反例。答：此方法不能求得最小生成樹(shù)。例如，對(duì)于如圖（a）所示的帶權(quán)連通無(wú)向圖，按照上述方法從頂點(diǎn)0開(kāi)始求得的結(jié)果為（b）所示的樹(shù)，顯然它不是最小生成樹(shù)，正確的最小生成樹(shù)如圖（c）所示。在有些情況下，上述方法無(wú)法求得結(jié)果，例如對(duì)于如圖（d）所示的帶權(quán)連通無(wú)向圖，從頂點(diǎn)0出發(fā)，找到頂點(diǎn)1（邊（0,1）），從頂點(diǎn)1出發(fā)，找到頂點(diǎn)3（邊（1,3）），再?gòu)捻旤c(diǎn)3出發(fā)，找到頂點(diǎn)0（邊（3,0）），這樣構(gòu)成回路，就不能求得最小生成樹(shù)了。求最小生成樹(shù)的反例圖3.如果對(duì)含有n（n>1）個(gè)元素的線性表的運(yùn)算只有4種：刪除第一個(gè)元素；刪除最后一個(gè)元素；在第一個(gè)元素前面插入新元素；在最后一個(gè)元素的后面插入新元素，則最好使用以下哪種存儲(chǔ)結(jié)構(gòu)，并簡(jiǎn)要說(shuō)明理由。（1）只有尾結(jié)點(diǎn)指針沒(méi)有頭結(jié)點(diǎn)指針的循環(huán)單鏈表（2）只有尾結(jié)點(diǎn)指針沒(méi)有頭結(jié)點(diǎn)指針的非循環(huán)雙鏈表（3）只有頭結(jié)點(diǎn)指針沒(méi)有尾結(jié)點(diǎn)指針的循環(huán)雙鏈表（4）既有頭結(jié)點(diǎn)指針也有尾結(jié)點(diǎn)指針的循環(huán)單鏈表答：本題答案為（3），因?yàn)閷?shí)現(xiàn)上述4種運(yùn)算的時(shí)間復(fù)雜度均為O(1)。4.已知一棵度為4的樹(shù)中，其度為0、1、2、3的結(jié)點(diǎn)數(shù)分別為14、4、3、2，求該樹(shù)的結(jié)點(diǎn)總數(shù)n和度為4的結(jié)點(diǎn)個(gè)數(shù)，并給出推導(dǎo)過(guò)程。答：結(jié)點(diǎn)總數(shù)n=n0+n1+n2+n3+n4，即n=23+n4，又有：度之和=n-1=0×n0+1×n1+2×n2+3×n3+4×n4，即n=17+4n4，綜合兩式得：n4=2，n=25。所以，該樹(shù)的結(jié)點(diǎn)總數(shù)為25，度為4的結(jié)點(diǎn)個(gè)數(shù)為2。四、算法設(shè)計(jì)題1.假設(shè)二叉樹(shù)b采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法voidfindparent(BTNode*b,ElemTypex,BTNode*&p)求指定值為x的結(jié)點(diǎn)的雙親結(jié)點(diǎn)p。提示：根結(jié)點(diǎn)的雙親為NULL；若在b中未找到值為x的結(jié)點(diǎn)，p亦為NULL。voidfindparent(BTNode*b,ElemTypex,BTNode*&p){ if(b!=NULL) { if(b->data==x)p=NULL; elseif(b->lchild!=NULL&&b->lchild->data==x) p=b; elseif(b->rchild!=NULL&&b->rchild->data==x) p=b; else { findparent(b->lchild,x,p); if(p==NULL) findparent(b->rchild,x,p); } } elsep=NULL;}2.設(shè)A和B是兩個(gè)結(jié)點(diǎn)個(gè)數(shù)分別為m和n的單鏈表（帶頭結(jié)點(diǎn)），其中元素遞增有序。設(shè)計(jì)一個(gè)盡可能高效的算法求A和B的交集，要求不破壞A、B的結(jié)點(diǎn)，將交集存放在單鏈表C中。給出所設(shè)計(jì)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。voidinsertion(LinkList*A,LinkList*B,LinkList*&C){ LinkList*p=A->next,*q=B->next,*s,*t; C=(LinkList*)malloc(sizeof(LinkList)); t=C; while(p!=NULL&&q!=NULL) { if(p->data==q->data) { s=(LinkList*)malloc(sizeof(LinkList)); s->data=p->data; t->next=s; t=s; p=p->next; q=q->next; } elseif(p->data<q->data) p=p->next; else q=q->next; } t->next=NULL;}算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(MIN(m,n))。一、單選題C01、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。A)1/2B)1C)2D)4B02、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A)1/2B)1C)2D)4B03、有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有條邊。A)14B)28C)56D)112C04、有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。A)5B)6C)7D)8C05、有8個(gè)結(jié)點(diǎn)的有向完全圖有條邊。A)14B)28C)56D)112B06、用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A)棧B)隊(duì)列C)樹(shù)D)圖A07、用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A)棧B)隊(duì)列C)樹(shù)D)圖A08、一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲(chǔ)結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為。A)O(n)B)O(e)C)O(n+e)D)O(n2)C09、已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是。A)0243156B)0136542CB10、已知圖的鄰接矩陣同上題，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是。A)0243651B)0123465CD11、已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是。A)0132B)0231C)0321D)0123A12、已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是。A)0321B)0123C)0132D)0312A13、圖的深度優(yōu)先遍歷類似于二叉樹(shù)的。A)先序遍歷B)中序遍歷C)后序遍歷D)層次遍歷D14、圖的廣度優(yōu)先遍歷類似于二叉樹(shù)的。A)先序遍歷B)中序遍歷C)后序遍歷D)層次遍歷B15、任何一個(gè)無(wú)向連通圖的最小生成樹(shù)。A)只有一棵B)一棵或多棵C)一定有多棵D)可能不存在A16、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則頂點(diǎn)表的大小為，所有邊鏈表中邊結(jié)點(diǎn)的總數(shù)為。A)n、2eB)n、eC)n、n+eD)2n、2eC17、判斷有向圖是否存在回路，可以利用___算法。A)關(guān)鍵路徑B)最短路徑的DijkstraC)拓?fù)渑判駾)廣度優(yōu)先遍歷A18、若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的“1”的個(gè)數(shù)為A)圖中每個(gè)頂點(diǎn)的入度B)圖中每個(gè)頂點(diǎn)的出度C)圖中弧的條數(shù)D)圖中連通分量的數(shù)目C19、求最短路徑的Dijkstra算法的時(shí)間復(fù)雜度是___。A)O(n)B)O(n+e)C)O(n2)D)O(n*e)B20、設(shè)圖G采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為。A)O(n)B)O(n+e)C)O(n2)D)O(n*e)D21、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中。A)第i行非∞的元素之和B)第i列非∞的元素之和C)第i行非∞且非0的元素個(gè)數(shù)D)第i列非∞且非0的元素個(gè)數(shù)C22、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有條邊。A)nB)n(n-1)C)n(n-1)/2D)2nD23、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是。A)nB)(n-1)2C)n-1D)nA24、對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)，。A)第i行上的非零元素個(gè)數(shù)和第i列的非零元素個(gè)數(shù)一定相等B)矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù)C)第i行上，第i列上非零元素總數(shù)等于頂點(diǎn)vi的度數(shù)D)矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù)D25、已知圖的表示如下，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為。A)abecdfB)acfebdC)aebcfdD)aedfcbB26、已知圖的表示如上題，若從頂點(diǎn)a出發(fā)按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為。A)abcedfB)abcefdC)aebcfdD)acfdebC27、有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，則根據(jù)有向圖的深度遍歷算法，從頂點(diǎn)v1出發(fā)得到的頂點(diǎn)序列是。A)v1,v2,v3,v5,v4B)v1,v2,v3,v4,v5C)v1,v3,v4,v5,v2D)v1,v4,v3,v5,v2B28、有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如上題所示，則根據(jù)有向圖的廣度遍歷算法，從頂點(diǎn)v1出發(fā)得到的頂點(diǎn)序列是。A)v1,v2,v3,v4,v5B)v1,v3,v2,v4,v5CA29、一個(gè)圖中有n個(gè)頂點(diǎn)且包含k個(gè)連通分量，若按深度優(yōu)先搜索方法訪問(wèn)所有結(jié)點(diǎn)，則必須調(diào)用次深度優(yōu)先遍歷算法。A)kB)1C)n-kD)nD30、以下不正確的說(shuō)法是。A)無(wú)向圖中的極大連通子圖稱為連通分量B)連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)C)圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)D)有向圖的遍歷不可采用廣度優(yōu)先搜索方法A31、圖中有關(guān)路徑的定義是___。A)由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B)由不同頂點(diǎn)所形成的序列C)由不同邊所形成的序列D)上述定義都不是B32、設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有___條邊。A)n-1B)n(n-1)/2C)n(n+1)/2D)nA33、一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為_(kāi)__。A)n-1B)nC)n+1D)nlognB34、要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要___條邊。A)n-lB)nC)n+lD)2nB35、在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)___倍。A)1/2B)2C)1D)4C36、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的___倍。A)1/2B)2CA37、用有向無(wú)環(huán)圖描述表達(dá)式(A+B)*（（A+B）/A），至少需要頂點(diǎn)的數(shù)目為_(kāi)__。A)5B)6CA38、用DFS遍歷一個(gè)無(wú)環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是___。A)逆拓?fù)溆行駼)拓?fù)溆行駽)無(wú)序的D)原順序B39、下列___的鄰接矩陣是對(duì)稱矩陣。A)有向圖B)無(wú)向圖C)AOV網(wǎng)D)AOE網(wǎng)BBD40、從鄰接陣矩可以看出，該圖共有①個(gè)頂點(diǎn)；如果是有向圖該圖共有②條??；如果是無(wú)向圖，則共有③條邊。①A)9B)3C)6D)1E)以上答案均不正確②A)5B)4C)3D)2E)以上答案均不正確③A)5B)4CB41、當(dāng)一個(gè)有N個(gè)頂點(diǎn)的圖用鄰接矩陣A表示時(shí)，頂點(diǎn)Vi的度是___。B42、下列說(shuō)法不正確的是___。A)圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次B)圖的深度遍歷不適用于有向圖C)遍歷的基本算法有兩種：深度遍歷和廣度遍歷D)圖的深度遍歷是一個(gè)遞歸過(guò)程D43、無(wú)向圖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)序列正確的是___。A)abecdfB)acfebdC)aebcfdD)aedfcbD44、如圖所示，在5個(gè)序列“aebdfc、acfdeb、aedfcb、aefdcb、aefdbc”，符合深度優(yōu)先遍歷的序列有___個(gè)。A)5B)4C)3DCC45、圖中給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先遍歷得到的序列是①，進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是②。①A)1354267B)1347652C)1534276D)1247653E②A)1534267B)1726453C)l354276D)1247653EB46、在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的Prim算法的時(shí)間復(fù)雜度為_(kāi)__。A)O(n)B)O(n+e)C)O(n2)D)O(n3)CABA47、下面是求連通網(wǎng)的最小生成樹(shù)的prim算法：集合VT，ET分別放頂點(diǎn)和邊，初始為①，下面步驟重復(fù)n-1次：②；③；最后：④。①A)VT，ET為空B)VT為所有頂點(diǎn)，ET為空C)VT為網(wǎng)中任意一點(diǎn)，ET為空D)VT為空，ET為網(wǎng)中所有邊②A)選i屬于VT，j不屬于VT，且(i,j)上的權(quán)最小B)選i屬于VT，j不屬于VT，且(i,j)上的權(quán)最大C)選i不屬于VT，j不屬于VT，且(i,j)上的權(quán)最小D)選i不屬于VT，j不屬于VT，且(i,j)上的權(quán)最大③A)頂點(diǎn)i加入VT，(i,j)加入ETB)頂點(diǎn)j加入VT，(i,j)加入ETC)頂點(diǎn)j加入VT，(i,j)從ET中刪去D)頂點(diǎn)i,j加入VT，(i,j)加入ET④A)ET中為最小生成樹(shù)B)不在ET中的邊構(gòu)成最小生成樹(shù)C)ET中有n-1條邊時(shí)為生成樹(shù)，否則無(wú)解D)ET中無(wú)回路時(shí)，為生成樹(shù)，否則無(wú)解A48、下面不正確的是___。①求從指定源點(diǎn)到其余各頂點(diǎn)的Dijkstra最短路徑算法中弧上權(quán)不能為負(fù)的原因是在實(shí)際應(yīng)用中無(wú)意義；②利用Dijkstra求每一對(duì)不同頂點(diǎn)之間的最短路徑的算法時(shí)間是O(n3)；(圖用鄰接矩陣表示)③Floyd求每對(duì)不同頂點(diǎn)對(duì)的算法中允許弧上的權(quán)為負(fù)，但不能有權(quán)和為負(fù)的回路。A)①②③B)①C)①③D)②③A49、已知有向圖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,V6D50、在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是___。A)G中有弧<Vi，Vj>B)G中有一條從Vi到Vj的路徑C)G中沒(méi)有弧<Vi,Vj>D)G中有一條從Vj到Vi的路徑A51、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中___。A)從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B)從源點(diǎn)到匯點(diǎn)的最短路徑C)最長(zhǎng)回路D)最短回路C52、下面關(guān)于求關(guān)鍵路徑的說(shuō)法不正確的是___。A)求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B)一個(gè)事件的最早開(kāi)始時(shí)間同以該事件為尾的弧的活動(dòng)最早開(kāi)始時(shí)間相同C)一個(gè)事件的最遲開(kāi)始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開(kāi)始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差D)關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上B53、下列關(guān)于AOE網(wǎng)的敘述中，不正確的是___。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)提前完成，那么整個(gè)工程將會(huì)提前完成二、填空題01、在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的入度。02、含n個(gè)頂點(diǎn)的無(wú)向連通圖中至少含有n-1條邊。03、圖的存儲(chǔ)結(jié)構(gòu)表示有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表等多種存儲(chǔ)結(jié)構(gòu)。04、圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表可以看成是有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表。05、遍歷圖的2種常見(jiàn)方法是深度遍歷和廣度遍歷。06、有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的出度。07、如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有n棵生成樹(shù)。08、n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為O(n2)。若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為O(n+e)。09、圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于有向圖。10、已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是將鄰接矩陣的第i行全部置0。11、圖采用鄰接矩陣表示，則計(jì)算第i個(gè)頂點(diǎn)入度的方法是求鄰接矩陣第i列非0元素之和。12、用鄰接矩陣表示圖時(shí)，則判斷任意兩個(gè)頂點(diǎn)vi和vj之間是否有路徑相連，只需要檢查第i行第j列的元素是否為0即可。13、用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹(shù)的時(shí)間復(fù)雜度為O(n2)；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是O(elog2e)。14、對(duì)稀疏圖最好用克魯斯卡爾(Kruskal)算法求最小生成樹(shù)，對(duì)稠密圖最好用普里姆(Prim)算法來(lái)求解最小生成樹(shù)。15、用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度遞增的次序來(lái)得到最短路徑的。16、拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有0個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的。17、有向圖G用鄰接矩陣存儲(chǔ)，則第i行的所有元素之和等于頂點(diǎn)i的出度。18、有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G至少有n條弧。19、設(shè)有向圖G的鄰接矩陣為A，如果圖中不存在弧<Vi,Vj>，則A[i,j]的值為0。20、在n個(gè)頂點(diǎn)的無(wú)向圖中，若邊數(shù)>n-1，則該圖必是連通圖，此斷言是錯(cuò)誤的。(正確/錯(cuò)誤)21、在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)2(n-1)。22、若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)渑判蛐蛄斜囟ù嬖凇?存在/不存在)23、一個(gè)有向無(wú)環(huán)圖的拓?fù)渑判蛐蛄胁灰欢ㄊ俏ㄒ坏摹?一定/不一定)24、判斷一個(gè)無(wú)向圖是一棵樹(shù)的條件是有n個(gè)頂點(diǎn)，n-1條邊的無(wú)向連通圖。25、有向圖G的強(qiáng)連通分量是指有向圖的極大強(qiáng)連通子圖。26、一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖。27、具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為45。28、若用n表示圖中頂點(diǎn)數(shù)目，則有n(n-1)/2條邊的無(wú)向圖成為完全圖。29、G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有9個(gè)頂點(diǎn)。30、在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要n條弧。31、構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有n條弧。32、有n個(gè)頂點(diǎn)的有向圖，至少需要量n條弧才能保證是連通的。33、N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有2(N-1)個(gè)非零元素。34、在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該頂點(diǎn)的度；對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的出度。35、在有向圖的鄰接矩陣表示中，計(jì)算第i個(gè)頂點(diǎn)入度的方法是第i列非0元素個(gè)數(shù)。36、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接表的表示，則表頭向量大小為n，鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為2e。37、已知一無(wú)向圖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開(kāi)始遍歷圖，得到的序列為abecd，則采用的是深度優(yōu)先遍歷方法。38、一無(wú)向圖G(V,E)，其中V(G)={1,2,3,4,5,6,7}，E(G)={(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(6,7),(5,1)}，對(duì)該圖從頂點(diǎn)3開(kāi)始進(jìn)行遍歷，去掉遍歷中未走過(guò)的邊，得一生成樹(shù)G'(V,E'),V(G')=V(G),E(G')={(1,3),(3,6),(7,3),(1,2),(1,5),(2,4)}，則采用的遍歷方法是廣度優(yōu)先遍歷。39、為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪問(wèn)的圖的結(jié)點(diǎn)外，還需隊(duì)列存放被訪問(wèn)的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷。40、構(gòu)造連通網(wǎng)最小生成樹(shù)的兩個(gè)典型算法是普里姆(prim)算法和克魯斯卡爾(Kruskal)算法。41、Prim(普里姆)算法適用于求邊稠密的網(wǎng)的最小生成樹(shù)；kruskal(克魯斯卡爾)算法適用于求邊稀疏的網(wǎng)的最小生成樹(shù)。42、下面描述的是一種構(gòu)造最小生成樹(shù)算法的基本思想。設(shè)要處理的無(wú)向圖包括n個(gè)節(jié)點(diǎn)V1，V2，．．．，Vn，用相鄰矩陣A表示，邊的權(quán)全是正數(shù)。請(qǐng)?jiān)谙铝袆澗€處填上正確敘述。(1)若(Vi,Vj)是邊，則A(i,j)的值等于(Vi,Vj)邊上的權(quán)值，若(Vi,Vj)不是邊，則A(i,j)的值是一個(gè)比任何邊的權(quán)都大的數(shù)，矩陣的對(duì)角線元素全為0。(2)構(gòu)造最小生成樹(shù)過(guò)程中，若節(jié)點(diǎn)Vi已包括進(jìn)生成樹(shù)，就把相鄰矩陣的對(duì)角線元素A(i,i)置成1，若(Vi,Vj)已包括進(jìn)生成樹(shù)，就把矩陣元素A(i,j)置成負(fù)值。(3)算法結(jié)束時(shí)，相鄰矩陣中為負(fù)的元素指出最小生成樹(shù)的邊。43、有一個(gè)用于n個(gè)頂點(diǎn)連通帶權(quán)無(wú)向圖的算法描述如下：(1)設(shè)集合T1與T2，初始均為空；(2)在連通圖上任選一點(diǎn)加入T1；(3)以下步驟重復(fù)n-1次：a)在i屬于T1，j不屬于T1的邊中選最小權(quán)的邊；b)該邊加入T2。上述算法完成后，T2中共有n-1條邊，該算法稱普里姆算法，T2中的邊構(gòu)成圖的最小生成樹(shù)。44、有向圖G可拓?fù)渑判虻呐袆e條件是不存在環(huán)。45、Dijkstra最短路徑算法從源點(diǎn)到其余各頂點(diǎn)的最短路徑的路徑長(zhǎng)度按遞增次序依次產(chǎn)生，該算法弧上的權(quán)出現(xiàn)負(fù)值情況時(shí)，不能正確產(chǎn)生最短路徑。46、有向圖G=(V,E),其中V(G)={0,1,2,3,4,5}，用<a,b,d>三元組表示弧<a,b>及弧上的權(quán)d.E(G)為{<0,5,100>,<0,2,10>,<1,2,5>,<0,4,30>,<4,5,60>,<3,5,10>,<2,3,50>,<4,3,20>}，則從源點(diǎn)0到頂點(diǎn)3的最短路徑長(zhǎng)度是50，經(jīng)過(guò)的中間頂點(diǎn)是頂點(diǎn)4。47、上面的圖去掉有向弧看成無(wú)向圖則對(duì)應(yīng)的最小生成樹(shù)的邊權(quán)之和為75。48、在AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)路徑上各活動(dòng)時(shí)間總和最長(zhǎng)的路徑稱為關(guān)鍵路徑。49、當(dāng)一個(gè)AOV網(wǎng)用鄰接表表示時(shí)，可按下列方法進(jìn)行拓?fù)渑判颉?1)查鄰接表中入度為0的頂點(diǎn)，并進(jìn)棧；(2)若棧不空，則①輸出棧頂元素Vj，并退棧；②查Vj的直接后繼Vk，對(duì)Vk入度處理，處理方法是Vk度減1，若Vk入度己減到零，則Vk頂點(diǎn)入棧；(3)若?？諘r(shí)，輸出頂點(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，說(shuō)明有環(huán)，否則拓?fù)渑判蛲瓿?。三、判斷題√01、樹(shù)中的結(jié)點(diǎn)和圖中的頂點(diǎn)就是指數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素?！?2、在n個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1,則該圖必是連通圖?！?3、有e條邊的無(wú)向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。×04、有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)?！?5、強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)?！?6、強(qiáng)連通分量是無(wú)向圖的極大強(qiáng)連通子圖?！?7、連通分量指的是有向圖中的極大連通子圖?！?8、十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)?！?9、無(wú)向圖的鄰接矩陣可用一維數(shù)組存儲(chǔ)?！?0、用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)?！?1、有n個(gè)頂點(diǎn)的無(wú)向圖,采用鄰接矩陣表示,圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半?！?2、有向圖的鄰接矩陣是對(duì)稱的?！?3、無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣，有向圖的鄰接矩陣一定是非對(duì)稱矩陣?！?4、鄰接矩陣適用于有向圖和無(wú)向圖的存儲(chǔ)，但不能存儲(chǔ)帶權(quán)的有向圖和無(wú)向圖，而只能使用鄰接表存儲(chǔ)形式來(lái)存儲(chǔ)它?！?5、用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)?！?6、一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等?！?7、廣度遍歷生成樹(shù)描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。×18、不同的求最小生成樹(shù)的方法最后得到的生成樹(shù)是相同的?！?9、連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹(shù)是唯一的。√20、在圖G的最小生成樹(shù)G1中，可能會(huì)有某條邊的權(quán)值超過(guò)未選邊的權(quán)值?！?1、拓?fù)渑判蛩惴ò岩粋€(gè)無(wú)向圖中的頂點(diǎn)排成一個(gè)有序序列?！?2、拓?fù)渑判蛩惴▋H能適用于有向無(wú)環(huán)圖?！?3、無(wú)環(huán)有向圖才能進(jìn)行拓?fù)渑判颉！?4、有環(huán)圖也能進(jìn)行拓?fù)渑判??！?5、拓?fù)渑判虻挠邢驁D中，最多存在一條環(huán)路。×26、任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃ㄒ??！?7、既使有向無(wú)環(huán)圖的拓?fù)湫蛄形ㄒ唬膊荒芪ㄒ淮_定該圖?！?8、若一個(gè)有向圖的鄰接矩陣對(duì)角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖??！?9、對(duì)一個(gè)AOV網(wǎng)，從源點(diǎn)到終點(diǎn)的路徑最長(zhǎng)的路徑稱作關(guān)鍵路徑?！?0、關(guān)鍵路徑是AOE網(wǎng)中從源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑。×31、在表示某工程的AOE網(wǎng)中，加速其關(guān)鍵路徑上的任意關(guān)鍵活動(dòng)均可縮短整個(gè)工程的完成時(shí)間?！?2、在AOE圖中，關(guān)鍵路徑上某個(gè)活動(dòng)的時(shí)間縮短，整個(gè)工程的時(shí)間也就必定縮短。√33、在AOE圖中，關(guān)鍵路徑上活動(dòng)的時(shí)間延長(zhǎng)多少，整個(gè)工程的時(shí)間也就隨之延長(zhǎng)多少?！?4、當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑。四、簡(jiǎn)答題01、寫(xiě)出下面有向圖的所有強(qiáng)連通分量。答：3個(gè)，分別是：a,bce,dfg02、已知圖的鄰接表如下，畫(huà)出圖G的所有連通分量。答：03、如下圖，分別用普里姆算法和克魯斯卡爾算法從頂點(diǎn)1開(kāi)始求最小生成樹(shù)，寫(xiě)出按次序產(chǎn)生邊的序列。說(shuō)明：邊用(i,j)方式表示。答：普里姆算法產(chǎn)生邊的序列：(1,3),(3,4),(4,6),(6,5),(1,2)克魯斯卡爾算法產(chǎn)生邊的序列：(4,6),(1,3),(4,3),(6,5),(1,2)04、如下圖，寫(xiě)出所有的拓?fù)湫蛄?，并求在添加什么邊之后僅可能有惟一的拓?fù)湫蛄小４穑簐1,v2,v3,v4v1,v3,v2,v4v2,v1,v3,v4<v3,v2>05、已知如圖所示的有向圖，請(qǐng)給出該圖的:(1)每個(gè)頂點(diǎn)的入/出度；(2)鄰接矩陣；(3)鄰接表；(4)逆鄰接表。答：(1)每個(gè)頂點(diǎn)的入/出度(2)鄰接矩陣(3)鄰接表(4)逆鄰接表06、寫(xiě)出無(wú)向帶樹(shù)圖的鄰接矩陣，并按普里姆算法填寫(xiě)表格中的內(nèi)容，最后畫(huà)出最小生成樹(shù)；VbcDeFghUV-UVexlowcosta4a3A∞a∞a∞a∞a∞{a}{bcdefgh}VexlowcostVexlowcostVexlowcostVexlowcostVexlowcostVexLowcostVexlowcost答：(1)鄰接矩陣為：VbcdefghUV-UVexlowcosta4a3a∞a∞a∞a∞a∞{a}{b,c,d,e,f,g,h}Vexlowcosta40c5a∞a∞a∞c5{a,c}{b,d,e,f,g,h}Vexlowcost00c5b9a∞a∞c5{a,c,b}{d,e,f,g,h}Vexlowcost000d7d6d5d4{a,c,b,d}{e,f,g,h}Vexlowcost000d7d6d50{a,c,b,d,h}{e,f,g}Vexlowcost000d7g200{a,c,b,d,h,g}{f,e}Vexlowcost000f3000{a,c,b,d,h,g,f}{e}Vexlowcost0000000{a,c,b,d,h,g,f,e}{}最小生成樹(shù)07、按克魯斯卡爾算法寫(xiě)出下面無(wú)向帶權(quán)圖求最小生成樹(shù)產(chǎn)生的邊序列。答：fg(2)ac(3)fe(3)ab(4)dh(4)bd(5)dg(5)08、已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。答：09、利用Dijkstra算法填寫(xiě)表格求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，并寫(xiě)出最終結(jié)果。終點(diǎn)DistbcDefgS(終點(diǎn)集)k=1k=2k=3k=4k=5k=6答：ac：2(a,c)af：6(a,c,f)ae：10(a,c,e)ad：11(a,c,f,d)ag：14(a,c,f,d,g)ab：15(a,b)10、求出下圖中從頂點(diǎn)1出發(fā)到其余各頂點(diǎn)的最短路徑。答：11、設(shè)圖G=(V，E)，V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}。畫(huà)出圖G，并寫(xiě)出圖G中頂點(diǎn)的所有拓?fù)湫蛄?。答?，2，3，6，5，41，3，2，6，5，41，3，6，2，5，4五、代碼填空題01、圖的存儲(chǔ)結(jié)構(gòu)定義如下：typedefstructArcCell{VRTypeadj;/*圖中有1/0表示是否有邊，網(wǎng)中表示邊上的權(quán)值*//*InfoType*info;與邊相關(guān)的信息*/}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*頂點(diǎn)向量*/AdjMatrixarcs;/*鄰接矩陣*/intvexnum,arcnum;/*圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)*/}MGraph;(1)請(qǐng)寫(xiě)出下面函數(shù)實(shí)現(xiàn)的功能：頂點(diǎn)在頂點(diǎn)向量中的定位。intLocateVex(MGraphG,VertexTypev){inti;for(i=0;i<G.vexnum;i++)if(strcmp(v,G.vexs[i])==0)break;returni;}(2)下面函數(shù)的功能是在圖中查找第1個(gè)鄰接點(diǎn)，請(qǐng)?zhí)羁?。intFirstAdjVex(MGraphG,intv){intj,p=-1;for(j=0;j<G.vexnum;j++)if(G.arcs[v][j].adj==1){p=j;break;}returnp;}(3)下面函數(shù)的功能是在圖中查找下一個(gè)鄰接點(diǎn)，請(qǐng)?zhí)羁?。intNextAdjVex(MGraphG,intv,intw){intj,p=-1;for(j=w+1;j<G.vexnum;j++)if(G.arcs[v][j].adj==1){p=j;break;}returnp;}02、已知圖的鄰接表表示的形式說(shuō)明如下：#defineMaxNum80typedefstructnode{intadjvex;//鄰接點(diǎn)域structnode*next;//鏈指針域}EdgeNode;//邊表結(jié)點(diǎn)結(jié)構(gòu)描述typedefstruct{charvertex;//頂點(diǎn)域EdgeNode*firstedge;//邊表頭指針}VertexNode;//頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述typedefstruct{VertexNodeadjlist[MaxNum];//鄰接表intn,e;}AlGraph;//鄰接表結(jié)構(gòu)描述下列算法輸出圖G的深度優(yōu)先生成樹(shù)(或森林)的邊，閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個(gè)完整的算法。typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxNum];voidDFSForest(AlGraph*G){for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)if(!visited[i])DFSTree(G,i);}voidDFSTree(AlGraph*G,inti){visited[i]=TRUE;p=G->adjlist[i].firstedge;while(p!=NULL){if(!visited[p->adjves]){printf(G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex);DSFTree(G,p->adjvex);}p=p->next;}}六、算法設(shè)計(jì)題01、編寫(xiě)編歷算法，完成對(duì)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。答：深度優(yōu)先搜索：課本P169算法7