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