數(shù)據(jù)結(jié)構(gòu)練習(xí)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)練習(xí)題習(xí)題1 緒論1.1 單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中,數(shù)據(jù)元素的 、數(shù)據(jù)信息在計算機中的 以及一組相關(guān)的運算等的課程。 A操作對象計算方法邏輯結(jié)構(gòu)數(shù)據(jù)映象 A存儲結(jié)構(gòu) 關(guān)系 運算 算法2. 數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為DS=（D，R），其中D是 的有限集合，R是D上的 有限集合。 A算法 數(shù)據(jù)元素 數(shù)據(jù)操作 數(shù)據(jù)對象 A操作 映象 存儲 關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4. 算法分析的目的是 ，

2、算法分析的兩個主要方面是 。 A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 研究算法中的輸入和輸出的關(guān)系C. 分析算法的效率以求改進(jìn) D. 分析算法的易懂性和文檔性 A. 空間復(fù)雜性和時間復(fù)雜性 B. 正確性和簡明性C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性5. 計算機算法指的是 ，它必具備輸入、輸出和 等五個特性。 A. 計算方法 B. 排序方法C. 解決問題的有限運算序列 D. 調(diào)度方法 A. 可行性、可移植性和可擴充性 B. 可行性、確定性和有窮性 C. 確定性、有窮性和穩(wěn)定性 D. 易讀性、穩(wěn)定性和安全性1.2 填空題（將正確的答案填在相應(yīng)的空中）1. 數(shù)據(jù)邏輯結(jié)構(gòu)包括 、 和 三種類型，

3、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為 。2. 在線性結(jié)構(gòu)中，第一個結(jié)點 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 個前驅(qū)結(jié)點；最后一個結(jié)點 后續(xù)結(jié)點，其余每個結(jié)點有且只有 個后續(xù)結(jié)點。3. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 結(jié)點，其余每個結(jié)點有且只有 個直接前驅(qū)結(jié)點，葉子結(jié)點沒有 結(jié)點，其余每個結(jié)點的直接后續(xù)結(jié)點可以 。4. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 。5. 線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。6. 算法的五個重要特性是_ _ , _ _ , _ _ , _ _ , _ _。7. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時間復(fù)雜度

4、是_ _。for (i=0;i<n;i+) for (j=0;j<n; j+) Aij=0;8. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時間復(fù)雜度是_ _。for (i=0;i<n;i+) for (j=0; j<i; j+)Aij=0;9. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時間復(fù)雜度是_ _。s=0;for (i=0;i<n;i+) for (j=0;j<n;j+) for (k=0;k<n;k+) s=s+Bijk;sum=s;10. 分析下面算法（程序段）給出最大語句頻度 ，該算法的時間復(fù)雜度是_ _。i=s=0

5、;while (s<n) i+; s+=i; /s=s+i 11. 分析下面算法（程序段）給出最大語句頻度 ，該算法的時間復(fù)雜度是_ _。i=1;while (i<=n) i=i*2;1.3 算法設(shè)計題1. 試寫一算法,自大到小依次輸出順序讀入的三個數(shù)X,Y和Z的值.2. 試寫一算法,求出n個數(shù)據(jù)中的最大值。寫出最大語句頻度，該算法的時間復(fù)雜度。 習(xí)題答案 1.1 1. C , A 2. B,D 3. C 4. C, A 5. C,B1.2 1. 線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)，非線性結(jié)構(gòu) 2. 沒有、1、沒有、1 3. 前驅(qū)、1、后續(xù)、任意多個 4. 任意多個 5. 一對一、一對多

6、、多對多 6. 有窮性、確定性、可行性、輸入、輸出 7. 最大語句頻度：n2 ， 時間復(fù)雜度：. O (n2) 8. 最大語句頻度：n (n+1)/2 ， 時間復(fù)雜度：. O (n2) 9. 最大語句頻度：n3 ， 時間復(fù)雜度：. O (n3)10. 最大語句頻度：n ， 時間復(fù)雜度：. O (n) 11. 最大語句頻度：log2n， 時間復(fù)雜度：. O (log2n )習(xí)題2 線性表2.1 單項選擇題1. 一個向量（即一批地址連續(xù)的存儲單元）第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是_ _。 A. 110 B. 108 C. 100 D. 1202. 線性表的順序

7、存儲結(jié)構(gòu)是一種_ _的存儲結(jié)構(gòu)，而鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種_ _的存儲結(jié)構(gòu)。A隨機存取 B索引存取 C順序存取 D散列存取3. 線性表的邏輯順序與存儲順序總是一致的，這種說法_ _。A. 正確 B. 不正確4. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址_ _。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以5. 在以下的敘述中，正確的是_ _。A. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B. 線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C. 線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D. 線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲

8、結(jié)構(gòu)6. 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找，這種說法_ _。A. 正確 B. 不正確7. 不帶頭結(jié)點的單鏈表head為空的判定條件是_。A. head= =NULL B. head->next= =NULLC. head->next= =head D. head!=NULL8. 帶頭結(jié)點的單鏈表head為空的判定條件是_。A. head= =NULL B. head->next= =NULLC. head->next= =head D. head!=NULL9. 非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足_。A. p->next= =NUL

9、L B. p= =NULLC. p->next= =head D. p= =head 10. 在雙向循環(huán)鏈表的p所指結(jié)點之后插入s所指結(jié)點的操作是_。A. p->right=s; s->left=p; p->right->left=s; s->right=p->right;B. p->right=s; p->right->left=s; s->left=p; s->right=p->right;C. s->left=p; s->right=p->right; p->right=s; p->

10、;right->left=s;D. s->left=p; s->right=p->right; p->right->left=s; p->right=s; 11. 在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行_。A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;B. q->next=s; s->next=p; C. p->next=s; s->next=q;12. 在一個單鏈表中，

11、若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行_。A. s->next=p; p->next=s; B. s->next=p->next; p->next=s;C. s->next=p->next; p=s; C. p->next=s; s->next=p;13. 在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行_。A. p->next= p->next->next； B. p= p->next; p->next= p->next->next；C. p->next= p->n

12、ext; D. p= p->next->next；14. 從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較_個結(jié)點。A. n B. n/2 C. (n-1)/2 D. (n+1)/2 15. 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是_ _。A. O(1) B. O(n) C. O (n2) D. O (nlog2n) 16. 給定有n個元素的向量，建立一個有序單鏈表的時間復(fù)雜度是_ _。A. O(1)） B. O(n) C. O (n2) D. O (n*log2n)2.2 填空題（將正確的答案填在相應(yīng)的空中）1. 單鏈

13、表可以做_ _的鏈接存儲表示。2. 在雙鏈表中，每個結(jié)點有兩個指針域，一個指向_ _，另一個指向_ _。3. 在一個單鏈表中p所指結(jié)點之前插入一個s (值為e)所指結(jié)點時，可執(zhí)行如下操作：q=head;while (q->next!=p) q=q->next;s= new Node; s->data=e;q->next= ; /填空s->next= ; /填空4. 在一個單鏈表中刪除p所指結(jié)點的后繼結(jié)點時，應(yīng)執(zhí)行以下操作：q= p->next;p->next= _ _; /填空delete ; /填空5. 在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點

14、時，應(yīng)執(zhí)行s->next=_ _和p->next=_的操作。 6. 對于一個具有n個結(jié)點的單鏈表，在已知p所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是_ _；在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是_ _。2.3 算法設(shè)計題:1.設(shè)順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。Status Insert_SqList(SqList &va,int x) if(va.length+1>maxsize) return ERROR; va.length+; for(i=va.length-1;va.elemi>x&am

15、p;&i>=0;i-) va.elemi+1=va.elemi; va.elemi+1=x; return OK; 2.試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表（a1, a2,. an）逆置為(an, an-1,., a1)。void reverse(int a, int size) int i,j,tmp; for(i=0, j=size-1; i<j; i+,j-) tmp=ai; ai=aj; aj=tmp; 3. 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時釋

16、放被刪除結(jié)點空間。void del(LinkList L,elemtype a,elemtype b)p= L;q=p->next; while(q!=L && q->data<a)p=q;q=q->next;while(q!=L && q->data<b)r=q;q=q->next;free(r); if(p!=q)p->next=q;4. 試寫一算法，實現(xiàn)單鏈表的就地逆置(要求在原鏈表上進(jìn)行)。void converse(NODEPTR L)  NODEPTR p,q;  p=L->n

17、ext; q=p->next;  L->next=NULL;  while(p)  /* 對于當(dāng)前結(jié)點p，用頭插法將結(jié)點p插入到頭結(jié)點之后 */        p->next=L->next;     L->next=p;     p=q;     q=q->next;     習(xí)題答案 2.1 1. B 2.

18、A, C 3. B 4. D 5. C 6. A 7. A 8. B 9. C 10. D 11.B 12.B 13.A 14.D 15.B 16.C 2.2 1. 線性結(jié)表 2. 前驅(qū)結(jié)點、后繼結(jié)點 3. s, p 4. q->next, q 5. p->next, s 6. O (1) , O (n)習(xí)題3 棧和隊列3.1 單項選擇題1. 一個棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是_。 A. edcba B. decba C. dceab D. abcde 2. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為_

19、。 A. i B. n=i C. n-i+1 D. 不確定3. 棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是_。A. 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)B. 散列方式和索引方式C. 鏈表存儲結(jié)構(gòu)和數(shù)組D. 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)4. 判定一個順序棧ST（最多元素為m0）為空的條件是_。A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-15. 判定一個順序棧ST（最多元素為m0）為棧滿的條件是_。A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-16. 棧的特點是_，隊列的特點是_。 A. 先進(jìn)先出 B. 先進(jìn)后出7. 向一個棧頂指

20、針為HS的鏈棧中插入一個s所指結(jié)點時，則執(zhí)行_ _。(不帶空的頭結(jié)點)A. HSnext=s;B. snext= HSnext; HSnext=s;C. snext= HS; HS=s;D. snext= HS; HS= HSnext;8. 從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行_ _。(不帶空的頭結(jié)點) A. x=HS; HS= HSnext; B. x=HSdata;C. HS= HSnext; x=HSdata; D. x=HSdata; HS= HSnext;9. 一個隊列的數(shù)據(jù)入列序列是1，2，3，4，則隊列的出隊時輸出序列是_ 。 A. 4，3，2

21、，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，110. 判定一個循環(huán)隊列QU（最多元素為m0）為空的條件是_。A. rear - front= =m0 B. rear-front-1= =m0C. front= = rear D. front= = rear+111. 判定一個循環(huán)隊列QU（最多元素為m0, m0= =Maxsize-1）為滿隊列的條件是_。A. (rear- front)+ Maxsize)% Maxsize = =m0B. rear-front-1= =m0 C. front= =rear D. front= = rear+112. 循環(huán)隊列用數(shù)組A0

22、，m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊列中的元素個數(shù)是_。A. (rear-front+m)%m B. rear-front+1C.rear-front-1 D. rear-front13. 棧和隊列的共同點是_。A. 都是先進(jìn)后出 B. 都是先進(jìn)先出C. 只允許在端點處插入和刪除元素 D. 沒有共同點3.2 填空題（將正確的答案填在相應(yīng)的空中）1. 向量、棧和隊列都是_結(jié)構(gòu)，可以在向量的_位置插入和刪除元素；對于棧只能在_插入和刪除元素；對于隊列只能在_插入元素和_刪除元素。2. 向一個長度為n的向量的第i個元素（1in+1）之前插入一個元素時，需向后移動_

23、個元素。3. 向一個長度為n的向量中刪除第i個元素（1in）時，需向前移動_個元素。4. 在具有n個單元的循環(huán)隊列中，隊滿時共有_個元素。 習(xí)題答案3.1 1. C 2. C 3. A 4. B 5.D 6. BA 7.C 8. B 9. C 10. C 11. A 12. A 13.C 3.2 1. 線性、任何、棧頂、隊尾、隊首 2. n-i+1 3. n-i 4. n-1 習(xí)題6 樹和二叉樹6.1 單項選擇題1. 由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法_。A. 正確 B. 錯誤2. 假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為

24、個。 A15 B16 C17 D473. 按照二叉樹的定義，具有3個結(jié)點的不同形狀的二叉樹有_種。A. 3 B. 4 C. 5 D. 64. 按照二叉樹的定義，具有3個不同數(shù)據(jù)結(jié)點的不同的二叉樹有_種。A. 5 B. 6 C. 30 D. 325. 深度為5的二叉樹至多有_個結(jié)點。A. 16 B. 32 C. 31 D. 106. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為_ _。A. 2h B. 2h-1 C. 2h+1 D. h+17. 對一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h，則_ 。A. n=h+m B. h+m=2n C. m=h-1 D.

25、n=2 h-18. 任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序_。A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對9. 如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序為_。 A. uwvts B. vwuts C. wuvts D. wutsv10. 二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的前面，這種說法_。 A. 正確 B. 錯誤11. 某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh，中序遍歷的結(jié)點訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是_。A. bdgcefha B. gdbecfha C.

26、bdgaechf D. gdbehfca12. 在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊_。A. 只有右子樹上的所有結(jié)點 B. 只有右子樹上的部分結(jié)點C. 只有左子樹上的部分結(jié)點 D. 只有左子樹上的所有結(jié)點13. 如圖6.1所示二叉樹的中序遍歷序列是_。A. abcdgef B. dfebagc C. dbaefcg D. defbagcgcefdbaagedbchf圖6.2 圖6.1 a14. 一棵二叉樹如圖6.2所示，其中序遍歷的序列為_ _。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgha15設(shè)a,b為一棵二叉樹上的兩個結(jié)點，在中序遍

27、歷時，a在b前的條件是 。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孫16. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是_。 A. acbed B. decab C. deabc D. cedba17. 實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹采用_存儲結(jié)構(gòu)。A. 二叉鏈表 B. 廣義表存儲結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲結(jié)構(gòu)18. 如圖6.3所示的4棵二叉樹，_不是完全二叉樹。(A) (B) (C) (D)圖6.320. 在線索化二叉樹中，t所指結(jié)點沒有左子樹的充要條件是_。A. tleft=NULL B.

28、 tltag=1C. tltag=1且tleft=NULL D. 以上都不對21. 二叉樹按某種順序線索化后，任一結(jié)點均有指向其前驅(qū)和后續(xù)的線索，這種說法_。 A. 正確 B. 錯誤22. 二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法_。 A. 正確 B. 錯誤23. 具有五層結(jié)點的二叉平衡樹至少有_個結(jié)點。A. 10 B. 12 C. 15 D. 1724. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對應(yīng)的二叉樹。結(jié)論_是正確的。A.樹的先根遍歷

29、序列與其對應(yīng)的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對25. 樹最適合用來表示_。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù)6.2 填空題（將正確的答案填在相應(yīng)的空中）1. 有一棵樹如圖6.5所示，回答下面的問題：k1 11kkkkkk21 4356 7 這棵樹的根結(jié)點是_； 這棵樹的葉子結(jié)點是_； 結(jié)點k3的度是_；圖6.5 一棵樹 這棵樹的度是_； 這棵樹的深度是_； 結(jié)點k3的子女是_； 結(jié)點k3的父結(jié)點是_ 2. 指出樹

30、和二叉樹的三個主要差別_、_、_。_；3. 從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是_ _。123456789101112131415161718192021eafdgcjlhb圖6.6 一棵二叉樹的順序存儲數(shù)組t4. 一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組t中，如圖6.6所示，則該二叉樹的鏈接表示形式為_ _。5. 深度為k的完全二叉樹至少有_個結(jié)點。至多有_個結(jié)點，若按自上而下，從左到右次序給結(jié)點編號（從1開始），則編號最小的葉子結(jié)點的編號是_。6. 在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n 0，度為2的結(jié)點的個數(shù)為 n 2，則有n0=_。7. 一棵

31、二叉樹的第i（i1）層最多有_個結(jié)點；一棵有n（n>0）個結(jié)點的滿二叉樹共有_個葉子和_個非終端結(jié)點。8. 結(jié)點最少的樹為_，結(jié)點最少的二叉樹為_。9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有_種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是_。10. 由如圖6.7所示的二叉樹，回答以下問題：iaedbchHf圖6.7 一棵二叉樹i 其中序遍歷序列為_； 其前序遍歷序列為_； 其后序遍歷序列為_；6.3 簡答題1. 根據(jù)二叉樹的定義，具有三個結(jié)點的二叉樹有5種不同的形態(tài)，請將它們分別畫出。2. 假設(shè)一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK

32、。gcefdba圖6.8 一棵樹請畫出該樹。3. 由如圖6.7所示的二叉樹，回答以下問題：（1）畫出該二叉樹的中序線索二叉樹；（2）畫出該二叉樹的后序線索二叉樹；（3）畫出該二叉樹對應(yīng)的森林。4. 已知一棵樹如圖6.8所示，轉(zhuǎn)化為一棵二叉樹，表示為_。5. 以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點權(quán)值，畫出構(gòu)造Huffman樹的每一步圖示，計算其帶權(quán)路徑長度為。6. 一棵含有N個結(jié)點的k叉樹,可能達(dá)到的最大深度和最小深度各為多少?7. 證明:一棵滿k叉樹上的葉子結(jié)點數(shù)n和非葉子結(jié)點數(shù)n之間滿足以下關(guān)系: n=(k-1)n+16.4 算法設(shè)計題1. 編寫按層次順序（同一層自左至右）遍歷二叉

33、樹的算法。2試編寫算法，對一棵二叉樹,統(tǒng)計葉子的個數(shù)。3試編寫算法，對一棵二叉樹根結(jié)點不變，將左、右子樹進(jìn)行交換，樹中每個結(jié)點的左、右子樹進(jìn)行交換。7. 假設(shè)用于通訊的電文僅有八個字母(a,b,c,d,e,f,g,h)組成，字母在電文中出現(xiàn)的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。試為這八個字母設(shè)計哈夫曼編碼。使用0-7的二進(jìn)制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。8. 試編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計葉子的個數(shù)。假設(shè)一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHI

34、JK。請畫出該樹。 習(xí)題答案6.1 1. B 2. B 3. C 4. C 5. C 6. A 7. D 8. A 9. C 10. A11. D 2. A 13. B 14. B 15. B 16. D 17. C 18. C 19. B 20. B 21. B 22. B 23. B 24. A 25. C 6.2 1. k1 k2,k5,k7,k4 2 3 4 k5,k6 k1 eaEfjcdlghb圖6.92. 樹的結(jié)點個數(shù)至少為1(不同教材規(guī)定不同)，而二叉樹的結(jié)點個數(shù)可以為0；樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2；樹的結(jié)點無左、右之分，而二叉樹的結(jié)點有左、右之分；

35、3. 樹可采用孩子-兄弟鏈表（二叉鏈表）做存儲結(jié)構(gòu)，目的并利用二叉樹的已有算法解決樹的有關(guān)問題。4. 如圖6.9所示 5. 2 k-1 、 2 k-1 、 2 k-2+1 6. n2+1 7. 2 i-1 2log2n+1-1 2log2n+1 1 8. 只有一個結(jié)點的樹；空的二叉樹9. 5；如圖6.10所示a圖6.10 樹形5種aaaacccccbbbbbb10. dgbaechif 、abdgcefhi 、gdbeihfca 、6.3 1. 5種, 圖6.11EBEFAECDKGHIJ圖6.12圖6.11 樹形5種2. 二叉樹如圖6.12所示。3. 中序線索二叉樹如圖6.13（左）所示；后

36、序線索二叉樹如圖6.13（右）所示；該二叉樹轉(zhuǎn)換后的的森林如圖6.14所示。圖6.13a 11dhjbkc 圖 6.14 對應(yīng)的森林iefabcedig圖 6.15 一棵樹的孩子兄弟表示4. 圖6.8的樹轉(zhuǎn)化為一棵二叉樹如下，圖6.15：5. 畫出構(gòu)造Huffman樹如圖6.16所示，計算其帶權(quán)路徑長度為 。6. 一棵含有N個結(jié)點的k叉樹,可能達(dá)到的最大深度 h=N-k+1 ，最小深度各為: logkN+1。623725191813121096745圖6.16 Huffman樹習(xí)題7 圖7.1 單項選擇題1在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_倍。A. 1/2 B. 1 C. 2 D.

37、 4 2任何一個無向連通圖的最小生成樹 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_倍。A. 1/2 B. 1 C. 2 D. 44一個有n個頂點的無向圖最多有_條邊。A. n B. n(n-1) C. n(n-1)/2 D. 2n5具有4個頂點的無向完全圖有_條邊。A. 6 B. 12 C. 16 D. 206具有6個頂點的無向圖至少應(yīng)有_條邊才能確保是一個連通圖。A. 5 B. 6 C. 7 D. 87在一個具有n個頂點的無向圖中，要連通全部頂點至少需要_條邊。A. n B. n+1 C. n-1 D. n/28對

38、于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是_。A. n B. (n-1)2 C. n-1 D. n29對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為_；所有鄰接表中的接點總數(shù)是_。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一個圖如圖7.1所示，若從頂點a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為_；按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為_。 A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b

39、baecdf A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b圖 7.1 一個無向圖11已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖7.2所示。12345324524圖7.2 一個有向圖的鄰接表存儲結(jié)構(gòu) 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是_。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根據(jù)有向圖的寬度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,

40、v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v212采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷13采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的_。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷14判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用_。A. 求關(guān)鍵路徑的方法 B. 求最短路徑的Dijkstra方法C. 寬度優(yōu)先遍歷算法 D. 深度優(yōu)先遍歷算法15關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中 。A.從源點到匯點的最長路徑 B.從源點到匯點的最短路徑C.最長的回路

41、 D.最短的回路16下面不正確的說法是 。 （1）在AOE網(wǎng)中，減小一個關(guān)鍵活動上的權(quán)值后，整個工期也就相應(yīng)減??； （2）AOE網(wǎng)工程工期為關(guān)鍵活動上的權(quán)之和； （3）在關(guān)鍵路徑上的活動都是關(guān)鍵活動，而關(guān)鍵活動也必在關(guān)鍵路徑上。A.（1）B.（2）C.（3）D.（1）、（2）17用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印出相應(yīng)的頂點，則輸出的頂點序列是 。A.逆拓樸有序的B.拓樸有序的C.無序的18在圖7.3所示的拓樸排列的結(jié)果序列為 。A.B.C.D.圖7.3有向圖19一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)為 。A.0B.1C.nD.n+120對于一個有向圖，若一個

42、頂點的入度為k1,、出度為k2，則對應(yīng)鄰接表中該頂點單鏈表中的結(jié)點數(shù)為 。A.k1B.k2C.k1-k2D.k1+k221對于一個有向圖，若一個頂點的入度為k1,、出度為k2，則對應(yīng)逆鄰接表中該頂點單鏈表中的結(jié)點數(shù)為 。A.k1B.k2C.k1-k2D.k1+k27.2 填空題（將正確的答案填在相應(yīng)餓空中）1n個頂點的連通圖至少_條邊。2在無權(quán)圖G的鄰接矩陣A中，若(vi,vj)或vi,vj屬于圖G的邊集合，則對應(yīng)元素Aij等于_，否則等于_。3在無向圖G的鄰接矩陣A中，若Aij等于1，則Aji 等于_。4已知圖G的鄰接表如圖7.4所示，其從頂點v1出發(fā)的深度有限搜索序列為_，其從頂點v1出發(fā)

43、的寬度優(yōu)先搜索序列為_。v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3 圖7.4 圖G的鄰接表5已知一個有向圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是_。6已知一個圖的鄰接矩陣表示，刪除所有從第i個結(jié)點出發(fā)的邊的方法是_。7如果含n個頂點的圖形成一個環(huán)，則它有 棵生成樹。8一個非連通無向圖，共有28條邊，則該圖至少有 個頂點。9遍歷圖的過程實質(zhì)上是 。BFS遍歷圖的時間復(fù)雜度為 ，DFS遍歷圖的時間復(fù)雜度為 ，兩者不同之處在于 ，反映在數(shù)據(jù)結(jié)構(gòu)上的差別是 。10一個圖的 表示法是唯一的，而 表示法是不唯一的。11有向圖中的結(jié)點前驅(qū)后繼關(guān)系的特征是 。12若無向圖G的頂點度數(shù)最

44、小值大于等于 時，G至少有一條回路。13根據(jù)圖的存儲結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點序列是 的。7.3 綜合題1562431已知如圖7.5所示的有向圖，請給出該圖的:（1）每個頂點的入/出度；（2）鄰接距陣；（3）鄰接表；（4）逆鄰接表；（5）強連通分量。圖7。5一個有向圖badcef161115151516131412212請用克魯斯卡爾和普里姆兩種算法分別為圖7.6、圖7.7構(gòu)造最小生成樹： （1） 圖7.661213212495201516106154372（2） 圖7.73試列出圖7.8中全部的拓?fù)渑判蛐蛄小?23456圖7.84請用圖示說明圖7.9從頂點a到其余各頂點之間的最短路徑。543223356abdfce圖7.95已知AOE網(wǎng)有9個結(jié)點：V1，V2，V3，V4，V5，