數(shù)據(jù)結(jié)構(gòu)練習(xí)題(含答案)(DOC)(1)18頁(yè)

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)題習(xí)題1 緒論1.1 單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中,數(shù)據(jù)元素的 、數(shù)據(jù)信息在計(jì)算機(jī)中的 以及一組相關(guān)的運(yùn)算等的課程。 A操作對(duì)象計(jì)算方法邏輯結(jié)構(gòu)數(shù)據(jù)映象 A存儲(chǔ)結(jié)構(gòu) 關(guān)系 運(yùn)算 算法2. 數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為DS=（D，R），其中D是 的有限集合，R是D上的 有限集合。 A算法 數(shù)據(jù)元素 數(shù)據(jù)操作 數(shù)據(jù)對(duì)象 A操作 映象 存儲(chǔ) 關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。A動(dòng)態(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. 算法分析的目的是 ，算法分析的兩個(gè)主要方面是

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

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

4、;i<n;i+) for (j=0;j<n; j+) Aij=0;8. 分析下面算法（程序段），給出最大語(yǔ)句頻度 ，該算法的時(shí)間復(fù)雜度是_ _。for (i=0;i<n;i+) for (j=0; j<i; j+)Aij=0;9. 分析下面算法（程序段），給出最大語(yǔ)句頻度 ，該算法的時(shí)間復(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. 分析下面算法（程序段）給出最大語(yǔ)句頻度 ，該算法的時(shí)間復(fù)雜度是_ _。i=s=0;while (s<

5、n) i+; s+=i; /s=s+i 11. 分析下面算法（程序段）給出最大語(yǔ)句頻度 ，該算法的時(shí)間復(fù)雜度是_ _。i=1;while (i<=n) i=i*2;1.3 算法設(shè)計(jì)題1. 試寫一算法,自大到小依次輸出順序讀入的三個(gè)數(shù)X,Y和Z的值.2. 試寫一算法,求出n個(gè)數(shù)據(jù)中的最大值。寫出最大語(yǔ)句頻度，該算法的時(shí)間復(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ù)、任意多個(gè) 4. 任意多個(gè) 5. 一對(duì)一、一對(duì)多、多對(duì)多 6. 有窮性、確

6、定性、可行性、輸入、輸出 7. 最大語(yǔ)句頻度：n2 ， 時(shí)間復(fù)雜度：. O (n2) 8. 最大語(yǔ)句頻度：n (n+1)/2 ， 時(shí)間復(fù)雜度：. O (n2) 9. 最大語(yǔ)句頻度：n3 ， 時(shí)間復(fù)雜度：. O (n3)10. 最大語(yǔ)句頻度：n ， 時(shí)間復(fù)雜度：. O (n) 11. 最大語(yǔ)句頻度：log2n， 時(shí)間復(fù)雜度：. O (log2n )習(xí)題2 線性表2.1 單項(xiàng)選擇題1. 一個(gè)向量（即一批地址連續(xù)的存儲(chǔ)單元）第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是_ _。 A. 110 B. 108 C. 100 D. 1202. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種_ _的存儲(chǔ)

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

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

9、C. p->next= =head D. p= =head 10. 在雙向循環(huán)鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是_。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->right->le

10、ft=s;D. s->left=p; s->right=p->right; p->right->left=s; p->right=s; 11. 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(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. 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，

11、在p之后插入s所指結(jié)點(diǎn)，則執(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. 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行_。A. p->next= p->next->next； B. p= p->next; p->next= p->next->next；C. p->next= p->next; D. p= p-

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

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

14、xt=_ _和p->next=_的操作。 6. 對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_ _；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_ _。2.3 算法設(shè)計(jì)題: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&&i>=

15、0;i-) va.elemi+1=va.elemi; va.elemi+1=x; return OK; 2.試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表（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. 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時(shí)釋放被刪除結(jié)點(diǎn)空間。void

16、 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. 試寫一算法，實(shí)現(xiàn)單鏈表的就地逆置(要求在原鏈表上進(jìn)行)。void converse(NODEPTR L)  NODEPTR p,q;  p=L->next; q=p->

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

18、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é)點(diǎn)、后繼結(jié)點(diǎn) 3. s, p 4. q->next, q 5. p->next, s 6. O (1) , O (n)習(xí)題3 棧和隊(duì)列3.1 單項(xiàng)選擇題1. 一個(gè)棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是_。 A. edcba B. decba C. dceab D. abcde 2. 若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為_。 A. i B. n=i

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

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

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

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

23、n的向量中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng)_個(gè)元素。4. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有_個(gè)元素。 習(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. 線性、任何、棧頂、隊(duì)尾、隊(duì)首 2. n-i+1 3. n-i 4. n-1 習(xí)題6 樹和二叉樹6.1 單項(xiàng)選擇題1. 由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說法_。A. 正確 B. 錯(cuò)誤2. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。 A15 B16 C1

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

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

26、dbehfca12. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_。A. 只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)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為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是 。

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

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

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

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

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

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

33、一棵二叉樹,統(tǒng)計(jì)葉子的個(gè)數(shù)。3試編寫算法，對(duì)一棵二叉樹根結(jié)點(diǎn)不變，將左、右子樹進(jìn)行交換，樹中每個(gè)結(jié)點(diǎn)的左、右子樹進(jìn)行交換。7. 假設(shè)用于通訊的電文僅有八個(gè)字母(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。試為這八個(gè)字母設(shè)計(jì)哈夫曼編碼。使用0-7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。8. 試編寫算法，對(duì)一棵以孩子-兄弟鏈表表示的樹統(tǒng)計(jì)葉子的個(gè)數(shù)。假設(shè)一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請(qǐng)畫出該樹。 習(xí)題答

34、案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é)點(diǎn)個(gè)數(shù)至少為1(不同教材規(guī)定不同)，而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0；樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2；樹的結(jié)點(diǎn)無(wú)左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分；3. 樹可采用孩子-兄弟鏈

35、表（二叉鏈表）做存儲(chǔ)結(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. 只有一個(gè)結(jié)點(diǎn)的樹；空的二叉樹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（左）所示；后序線索二叉樹如圖6.13（

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

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

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

39、,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 一個(gè)無(wú)向圖11已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖7.2所示。12345324524圖7.2 一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_。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)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2

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

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

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

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

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