【正文】 //無右子樹，則有右線索{ srchild=prchild。srtag=1。prchild=s。prtag=0。}else{ q=prchild。while(qltag= =0) //查找p所指結(jié)點中序后繼，即為其右子樹中最左下的結(jié)點 q=qlchild。qlchild=prchild。srtag=0。prchild=s。}slchild=p。 //將s結(jié)點的左線索指向p結(jié)點sltag=1。}4. 解答：利用一個隊列來完成，設(shè)該隊列類型為指針類型，最大容量為maxnum。算法中的front為隊頭指針，rear為隊尾指針，若當(dāng)前隊頭結(jié)點的左、右子樹的根結(jié)點不是所求結(jié)點，則將兩子樹的根結(jié)點入隊，否則，隊頭指針?biāo)附Y(jié)點即為結(jié)點的雙親。parentjudge(t,n)BiTree *t。int n。{ BiTree *que[maxnum]。int front,rear。BiTree *parent。parent=NULL。if (t)if (tdata= =n)printf(“no parent!”)。 //n是根結(jié)點，無雙親else{ front=0。 //初始化隊列 rear=1。 que[1]=t。 //根結(jié)點進(jìn)隊 do { front=front%maxsize+1。 t=que[front]。 if((tlchilddata= =n)|| (trchilddata= =n)) //結(jié)點n有雙親 { parent=t。 front=rear。 printf(“parent”,tdata)。} else { if (tlchild!=NULL) //左子樹的根結(jié)點入隊 { rear=rear%maxsize+1。 que[rear]=tlchild。} if (trchild!=NULL) //右子樹的根結(jié)點入隊 { rear=rear%maxsize+1。 que[rear]=trchild。}}}while(rear= =front)。 //隊空時結(jié)束 if (parent = =NULL) printf(“結(jié)點不存在”)。}}習(xí)題6一、單項選擇題 1. 在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有頂點的入度數(shù)之和為(　　)。A. s B. s1 C. s+1 D. n 2. 在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有頂點的度數(shù)之和為(　　)。A. s B. s1 C. s+1 D. 2s 3. 在一個具有n個頂點的無向圖中，若具有e條邊，則所有頂點的度數(shù)之和為(　　)。A. n B. e C. n+e D. 2e 4. 在一個具有n個頂點的無向完全圖中，所含的邊數(shù)為(　　)。A. n B. n(n1) C. n(n1)/2 D. n(n+1)/2 5. 在一個具有n個頂點的有向完全圖中，所含的邊數(shù)為( )。A. n B. n(n1) C. n(n1)/2 D. n(n+1)/2 6. 在一個無向圖中，若兩頂點之間的路徑長度為k，則該路徑上的頂點數(shù)為( )。A. k B. k+1 C. k+2 D. 2k 7. 對于一個具有n個頂點的無向連通圖，它包含的連通分量的個數(shù)為( )。A. 0 B. 1 C. n D. n+1 8. 若一個圖中包含有k個連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂點，則必須調(diào)用( )次深度優(yōu)先搜索遍歷的算法。A. k B. 1 C. k1 D. k+1 9. 若要把n個頂點連接為一個連通圖，則至少需要( )條邊。A. n B. n+1 C. n1 D. 2n 10. 在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個數(shù)為( )。A. n B. n180。e C. e D. 2180。e 11. 在一個具有n個頂點和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個數(shù)為( )。A. n B. n180。e C. e D. 2180。e 12. 在一個具有n個頂點和e條邊的無向圖的鄰接表中，邊結(jié)點的個數(shù)為( )。A. n B. n180。e C. e D. 2180。e 13. 在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈表的表頭指針向量的大小至少為( )。A. n B. 2n C. e D. 2e 14. 在一個無權(quán)圖的鄰接表表示中，每個邊結(jié)點至少包含( )域。A. 1 B. 2 C. 3 D. 4 15. 對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應(yīng)鄰接表中該頂點單鏈表中的邊結(jié)點數(shù)為( )。A. k1 B. k2 C. k1k2 D. k1+k2 16. 對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應(yīng)逆鄰接表中該頂點單鏈表中的邊結(jié)點數(shù)為( )。A. k1 B. k2 C. k1k2 D. k1+k2 17. 對于一個無向圖，下面( )種說法是正確的。A. 每個頂點的入度等于出度 B. 每個頂點的度等于其入度與出度之和C. 每個頂點的入度為0 D. 每個頂點的出度為0 18. 在一個有向圖的鄰接表中，每個頂點單鏈表中結(jié)點的個數(shù)等于該頂點的( )。A. 出邊數(shù) B. 入邊數(shù) C. 度數(shù) D. 度數(shù)減1 19. 若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點A開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點序列可能為( )。A. A,B,C,F,D,E B. A,C,F,D,E,BC. A,B,D,C,F,E D. A,B,D,F,E,C 20. 若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點A開始對該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點序列可能為( )。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. 若一個圖的邊集為{1,2,1,4,2,5,3,1,3,5,4,3}，則從頂點1開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點序列可能為( )。A. 1,2,5,4,3 B. 1,2,3,4,5C. 1,2,5,3,4 D. 1,4,3,2,5 22. 若一個圖的邊集為{1,2,1,4,2,5,3,1,3,5,4,3}，則從頂點1開始對該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點序列可能為( )。A. 1,2,3,4,5 B. 1,2,4,3,5C. 1,2,4,5,3 D. 1,4,2,5,3 23. 由一個具有n個頂點的連通圖生成的最小生成樹中，具有( )條邊。A. n B. n1 C. n+1 D. 2180。n 24. 已知一個有向圖的邊集為{a,b,a,c,a,d,b,d,b,e,d,e}，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨? )。A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e二、填空題 1. 在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的________倍。 2. 在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。 3. 假定一個有向圖的頂點集為{a,b,c,d,e,f}，邊集為{a,c, a,e, c,f, d,c, e,b, e,d}，則出度為0的頂點個數(shù)為________，入度為1的頂點個數(shù)為________。 4. 在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要________條邊。 5. 表示圖的兩種存儲結(jié)構(gòu)為__________和__________。 6. 在一個連通圖中存在著________個連通分量。 7. 圖中的一條路徑長度為k，該路徑所含的頂點數(shù)為________。 8. 若一個圖的頂點集為{a,b,c,d,e,f}，邊集為{(a,b),(a,c),(b,c),(d,e)}，則該圖含有________個連通分量。 9. 對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小至少為________180。________。 10. 對于具有n個頂點和e條邊的有向圖和無向圖，在它們對應(yīng)的鄰接表中，所含邊結(jié)點的個數(shù)分別為________和________。 11. 在有向圖的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有________和________結(jié)點。 12. 對于一個具有n個頂點和e條邊的無向圖，當(dāng)分別采用鄰接矩陣和鄰接表表示時，求任一頂點度數(shù)的時間復(fù)雜度分別為________和________。 13. 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣和鄰接表表示時，其相應(yīng)的空間復(fù)雜度分別為________和________。 14. 一個圖的邊集為{(a,c),(a,e),(b,e),(c,d),(d,e)}，從頂點a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷得到的頂點序列為____________，從頂點a出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點序列為____________。 15. 一個圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，從頂點a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷得到的頂點序列為____________，從頂點a出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點序列為____________。 16. 圖的________優(yōu)先搜索遍歷算法是一種遞歸算法，圖的________優(yōu)先搜索遍歷算法需要使用隊列。 17. 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為________和________。 18. 若一個連通圖中每個邊上的權(quán)值均不同，則得到的最小生成樹是________（唯一/不唯一）的。 19. 根據(jù)圖的存儲結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點序列是__（唯一/不唯一）的。20. 假定一個有向圖的邊集為{a,c,a,e,c,f,d,c,e,b,e,d}，對該圖進(jìn)行拓?fù)渑判虻玫降捻旤c序列為________。三、應(yīng)用題1. 對于一個無向圖611(a)，假定采用鄰接矩陣表示，試分別寫出從頂點0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。 注：每一種序列都是唯一的，因為都是在存儲結(jié)構(gòu)上得到的。 2. 對于一個有向圖611(b)，假定采用鄰接表表示，并且假定每個頂點單鏈表中的邊結(jié)點是按出邊鄰接點序號從大到小的次序鏈接的，試分別寫出從頂點0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。 注：每一種序列都是唯一的，因為都是在存儲結(jié)構(gòu)上得到的。 3. 已知一個無向圖的鄰接矩陣如圖612(a)所示，試寫出從頂點0出發(fā)分別進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索遍歷得到的頂點序列。 4. 已知一個無向圖的鄰接表如圖612(b)所示，試寫出從頂點0出發(fā)分別進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索遍歷得到的頂點序列。 5. 已知圖613所示的一個網(wǎng)，按照Prim方法，從頂點1 出發(fā)，求該網(wǎng)的最小生成樹的產(chǎn)生過程。 6. 已知圖613所示的一個網(wǎng)，按照Kruskal方法，求該網(wǎng)的最小生成樹的產(chǎn)生過程。7. 圖614所示為一個有向網(wǎng)圖及其帶權(quán)鄰接矩陣，要求對有向圖采用Dijkstra算法，求從V0 到其余各頂點的最短路徑。8. 圖615給出了一個具有15個活動、11個事件的工程的AOE網(wǎng)，求關(guān)鍵路徑。四、算法設(shè)計題1. 編寫一個算法，求出鄰接