【正文】 (a) (b)圖612。 圖6110165948372(a)603451278(b) 3. 已知一個(gè)無向圖的鄰接矩陣如圖612(a)所示，試寫出從頂點(diǎn)0出發(fā)分別進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。 2. 對于一個(gè)有向圖611(b)，假定采用鄰接表表示，并且假定每個(gè)頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)是按出邊鄰接點(diǎn)序號從大到小的次序鏈接的，試分別寫出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。三、應(yīng)用題1. 對于一個(gè)無向圖611(a)，假定采用鄰接矩陣表示，試分別寫出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。 19. 根據(jù)圖的存儲結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是__（唯一/不唯一）的。 17. 對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為________和________。 15. 一個(gè)圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為____________。 13. 假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣和鄰接表表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為________和________。 11. 在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有________和________結(jié)點(diǎn)。________。 8. 若一個(gè)圖的頂點(diǎn)集為{a,b,c,d,e,f}，邊集為{(a,b),(a,c),(b,c),(d,e)}，則該圖含有________個(gè)連通分量。 6. 在一個(gè)連通圖中存在著________個(gè)連通分量。 4. 在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要________條邊。 2. 在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。n 24. 已知一個(gè)有向圖的邊集為{a,b,a,c,a,d,b,d,b,e,d,e}，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨? )。A. 1,2,3,4,5 B. 1,2,4,3,5C. 1,2,4,5,3 D. 1,4,2,5,3 23. 由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有( )條邊。A. A,B,C,D,E,F B. A,B,C,F,D,EC. A,B,D,C,E,F D. A,C,B,F,D,E 21. 若一個(gè)圖的邊集為{1,2,1,4,2,5,3,1,3,5,4,3}，則從頂點(diǎn)1開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( )。A. 出邊數(shù) B. 入邊數(shù) C. 度數(shù) D. 度數(shù)減1 19. 若一個(gè)圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( )。A. k1 B. k2 C. k1k2 D. k1+k2 17. 對于一個(gè)無向圖，下面( )種說法是正確的。A. 1 B. 2 C. 3 D. 4 15. 對于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2，則對應(yīng)鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為( )。e 13. 在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為( )。A. n B. n180。e C. e D. 2180。e 11. 在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個(gè)數(shù)為( )。A. n B. n180。A. k B. 1 C. k1 D. k+1 9. 若要把n個(gè)頂點(diǎn)連接為一個(gè)連通圖，則至少需要( )條邊。A. k B. k+1 C. k+2 D. 2k 7. 對于一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖，它包含的連通分量的個(gè)數(shù)為( )。A. n B. n(n1) C. n(n1)/2 D. n(n+1)/2 5. 在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為( )。A. s B. s1 C. s+1 D. 2s 3. 在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若具有e條邊，則所有頂點(diǎn)的度數(shù)之和為(　　)。}}習(xí)題6一、單項(xiàng)選擇題 1. 在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的入度數(shù)之和為(　　)。}}}while(rear= =front)。} if (trchild!=NULL) //右子樹的根結(jié)點(diǎn)入隊(duì) { rear=rear%maxsize+1。} else { if (tlchild!=NULL) //左子樹的根結(jié)點(diǎn)入隊(duì) { rear=rear%maxsize+1。 front=rear。 t=que[front]。 que[1]=t。 //n是根結(jié)點(diǎn)，無雙親else{ front=0。parent=NULL。int front,rear。int n。算法中的front為隊(duì)頭指針，rear為隊(duì)尾指針，若當(dāng)前隊(duì)頭結(jié)點(diǎn)的左、右子樹的根結(jié)點(diǎn)不是所求結(jié)點(diǎn)，則將兩子樹的根結(jié)點(diǎn)入隊(duì)，否則，隊(duì)頭指針?biāo)附Y(jié)點(diǎn)即為結(jié)點(diǎn)的雙親。 //將s結(jié)點(diǎn)的左線索指向p結(jié)點(diǎn)sltag=1。prchild=s。qlchild=prchild。}else{ q=prchild。prchild=s。if (prtag= =1) //無右子樹，則有右線索{ srchild=prchild。insert(p, s) //將s結(jié)點(diǎn)作為p的右子樹插入BiThrNode *p,*s。}}while (rear= =front)。} if (trchild!=NULL) //右子樹的根結(jié)點(diǎn)入隊(duì) { rear=rear%maxsize+1。 if (tlchild!=NULL) //左子樹的根結(jié)點(diǎn)入隊(duì) { rear=rear%maxsize+1。 //出隊(duì) t=que[front]。que[1]=t。if (t!=NULL){ front=0。levelorder (BiTree *t) //按層次遍歷二叉樹t{ BiTree *que[maxnum]。}}}2. 解答：考慮用一個(gè)順序隊(duì)que來保存遍歷過程中的各個(gè)結(jié)點(diǎn)，由于二叉樹以二叉鏈表存儲，所以可設(shè)que為一個(gè)指向數(shù)據(jù)類型為bitree的指針數(shù)組，最大容量為maxnum，下標(biāo)從1開始，同層結(jié)點(diǎn)從左到右存放。} if (stop1) //棧非空訪問，遍歷右子樹 { root=sdata[stop]*2+1。 sdata[stop]=root。 (stop1)){ while (root=n){ printf(R[root])。while ((root=n) amp。 //s為一個(gè)指針棧，類型為seqstack，其中包含top域和數(shù)組datastop= 1。{ int root。BGDCHKEIFJLMNOA圖51650 92030111614 7 7 2 5圖517五、算法設(shè)計(jì)題1. 解答：這個(gè)問題可以用遞歸算法，也可用非遞歸算法，下面給出的為非遞歸算法。7. 解答：后序序列：ACDBGJKIHFE8. 解答：先序序列：ABCDGEIHFJK9. 解答：先根遍歷：ABCDEFGHIJKLMNO后根遍歷：BDEFCAHJIGKNOML森林轉(zhuǎn)換成二叉樹如圖516所示。其右兄弟的編號是n+1。（3）編號為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號是(n1)*m+i+1。3. 解答：　略4. 解答：　先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5. 解答：（1）第i層上的結(jié)點(diǎn)數(shù)目是mi1。其中根結(jié)點(diǎn)為a；葉子結(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號分別是2和5；樹的深度為5。i/2若沒有結(jié)點(diǎn)n或者該結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)，分別輸出相應(yīng)的信息；若結(jié)點(diǎn)n有雙親，輸出其雙親的值。3. 寫出在中序線索二叉樹中結(jié)點(diǎn)P的右子樹中插入一個(gè)結(jié)點(diǎn)s的算法。ABDEFCGHJIKNOML圖514五、算法設(shè)計(jì)題1. 一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹以一維數(shù)組作為存儲結(jié)構(gòu)，試設(shè)計(jì)一個(gè)對該完全二叉樹進(jìn)行先序遍歷的算法。9. 給出如圖514所示的森林的先根、后根遍歷結(jié)點(diǎn)序列，然后畫出該森林對應(yīng)的二叉樹。5. 一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對全部結(jié)點(diǎn)編號，回答下列問題：（1）各層的結(jié)點(diǎn)數(shù)目是多少？（2）編號為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號是多少？（3）編號為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號是多少？（4）編號為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號是多少？6. 找出所有滿足下列條件的二叉樹：（1）它們在先序遍歷和中序遍歷時(shí)，得到的遍歷序列相同；（2）它們在后序遍歷和中序遍歷時(shí)，得到的遍歷序列相同；（3）它們在先序遍歷和后序遍歷時(shí)，得到的遍歷序列相同；7. 假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請寫出該二叉樹的后序遍歷序列。四、應(yīng)用題1. 已知一棵樹邊的集合為{i，m，i，n，e，i，b，e，b，d，a，b，g，j，g，k，c，g，c，f，h，l，c，h，a，c}，請畫出這棵樹，并回答下列問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)g的雙親？（4）哪些是結(jié)點(diǎn)g的祖先？（5）哪些是結(jié)點(diǎn)g的孩子？（6）哪些是結(jié)點(diǎn)e的孩子？（7）哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？（8）結(jié)點(diǎn)b和n的層次號分別是什么？（9）樹的深度是多少？（10）以結(jié)點(diǎn)c為根的子樹深度是多少？2. 一棵度為2的樹與一棵二叉樹有何區(qū)別。19. 線索鏈表中的rtag域值為_____時(shí)，表示該結(jié)點(diǎn)無右孩子，此時(shí)______域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。17. 三叉鏈表比二叉鏈表多一個(gè)指向______________的指針域。15. 空樹是指________________________，最小的樹是指_______________________。13. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲時(shí)，鏈表中指針域的總數(shù)為_________個(gè)，其中___________個(gè)用于鏈接孩子結(jié)點(diǎn)，_____________個(gè)空閑著。11. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，______形態(tài)達(dá)到最大深度，____形態(tài)達(dá)到最小深度。9. 由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有____種不同的形態(tài)。7. 在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=______。5. 在一棵二叉排序樹上按_______遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。3. 對于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵________二叉樹時(shí)具有最小高度，即為_______，當(dāng)它為一棵單支樹具有_______高度，即為_______。 （?。┤?、填空題1. 假定一棵樹的廣義表表示為A（B（E），C（F（H，I，J），G），D），則該樹的度為_____，樹的深度為_____，終端結(jié)點(diǎn)的個(gè)數(shù)為______，單分支結(jié)點(diǎn)的個(gè)數(shù)為______，雙分支結(jié)點(diǎn)的個(gè)數(shù)為______，三分支結(jié)點(diǎn)的個(gè)數(shù)為_______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_______，其孩子結(jié)點(diǎn)為_______和_______結(jié)點(diǎn)。 （　）9. 哈夫曼樹一定是完全二叉樹。 （?。?. 根據(jù)任意一種遍歷序列即可唯一確定對應(yīng)的二叉樹。 （　）5. 由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。 （　）3. 線索二叉樹是一種邏輯結(jié)構(gòu)。A. 是完全二叉樹 B. 不是完全二叉樹