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

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)題(含答案)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ì)象B .計(jì)算方法 C.邏輯結(jié)構(gòu)D.數(shù)據(jù)映象A.存儲(chǔ)結(jié)構(gòu)B .關(guān)系C.運(yùn)算D.算法2.數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為DS= (D, R),其中D是的有限集合，R是D上的有限集合。A.算法B .數(shù)據(jù)元素C .數(shù)據(jù)操作D.數(shù)據(jù)對(duì)象1 / 62A.操作B .映象C.存儲(chǔ)D.關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成OA.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B .緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

2、4.算法分析的目的是 ,算法分析的兩個(gè)主要方面是OA.找出數(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è)特性。2 / 62A,計(jì)算方法B.排序方法C.解決問題的有限運(yùn)算序列D.調(diào)度方法A,可行性、可移植性和可擴(kuò)充性.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D,易讀性、穩(wěn)定性和安全性.2填空題（將正確的答案填在相應(yīng)的空中）1.數(shù)據(jù)邏輯結(jié)構(gòu)包括、和三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為O.在線性結(jié)構(gòu)中，

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

4、,該算法的時(shí)間復(fù)雜度是Ofor (i=0;ii+)for (j=0; j j+) Aij=0; 9,分析下面算法(程序段)，給出最 大語句頻度,該算法的時(shí)間復(fù)雜度是Os=0; for (i=0;ii+)for (j=0;jj+)for (k=0;kk+)s=s+Bijk; sum=s; 10,分析下面算法(程序段)給出最大 語句頻度,該算法的時(shí)間復(fù)雜度是Oi=s=0; while (sn) i+;s+=i;/s=s+i5 / 6211.分析下面算法(程序段)給出最大語句頻度,該算法的時(shí)間復(fù)雜度是Oi=1; while (i=n)i=i*2; 1.3算法設(shè)計(jì)題1.試寫一算法，自大到小依次輸出順序

5、讀入的三個(gè)數(shù)X,Y和Z的值.2.試寫一算法，求出n個(gè)數(shù)據(jù)中的 最大值。寫出最大語句頻度，該算法的時(shí)間復(fù)雜度。習(xí)題答案1.1C , AB,DCC, AC,B 1.2.線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)，非線性結(jié)構(gòu).沒有、1、沒有、1.前驅(qū)、1、后續(xù)、任意多個(gè).任意多個(gè). 一對(duì)一、一對(duì)多、多對(duì)多.有窮性、確定性、可行性、輸入、輸出6 / 62.最大語句頻度：n2 ,時(shí)間復(fù)雜度：.O (n2).最大語句頻度：n (n+1)/2 ,時(shí)間復(fù)雜度：.O (n2).最大語句頻度：n3 ,時(shí)間復(fù)雜度：.O (n3) 10.最大語 句頻度：n ,時(shí)間復(fù)雜度：.O (n)11.最大語句頻度：10g2n ,時(shí)間復(fù)雜度：.

6、O (log2n )習(xí)題2線性表2.1單項(xiàng)選擇題1. 一個(gè)向量(即一批地址連續(xù)的存 儲(chǔ)單元)第一個(gè)元素的存儲(chǔ)地址是 100,每個(gè)元素的長(zhǎng)度為2, 則第5個(gè)元素的地址是O110108100120 2.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 _用存儲(chǔ)結(jié)構(gòu)，而 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種J勺存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.索引存取C.順序存取7 / 62D.散列存取3.線性表的邏輯順序與存儲(chǔ)順序總是一致的， 這種說法OA.正確B.不正確4.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址OA.必須是連續(xù)的B.部分地址必須是連續(xù)的 C. 一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以5.在以下的敘述中，正確的是 _OA.線性表的

7、順序存儲(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)都具備三個(gè)基本運(yùn)算：插入、刪除和查找，這種說法OA.正確B.不正確7.不帶頭結(jié)點(diǎn)的單鏈表 head為空的判定條件是8 / 62head= =NULLhead-next= =NULL C. head-next= =headD. head!=NULL 8.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件head= =NULLhead-next= =NULL C. head-next= =headD. he

8、ad!=NULL 9.非空的循環(huán)單鏈表 head的尾結(jié)點(diǎn)（由p 所指向）滿足p-next= =NULLp= =NULL C. p-next= =headD. p= =head.在雙向循環(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;9 / 62s-right=p-right;p-right=s;p-right-left=s; D. s-left=p;s-ri

9、ght=p-right;p-right-left=s;p-right=s;.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū) 結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行 s-next=p-next;p-next=s;p-next=s-next;s-next=p; B. q-next=s;s-next=p;p-next=s;s-next=q; 12.在一個(gè)單鏈表中，若 p所指結(jié)點(diǎn)不是最后結(jié) 點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行s-next=p;p-next=s;10 / 62s-next=p-next;p-next=s; C.s-next=p-next;p=s；p-next=s;next=p; 13.

10、在一個(gè)單鏈表中，若刪除 p所指結(jié)點(diǎn)的后續(xù) 結(jié)點(diǎn)，則執(zhí)行p-next= p-next-next ;p= p-next;p-next= p-next-next ; C. p-next= p-next;D. p= p-next-next ; 14.從一個(gè)具有 n個(gè)結(jié)點(diǎn)的單鏈表中 查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 個(gè)結(jié)點(diǎn)。nn/2(n-1)/2(n+1)/2.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并 仍然有序的時(shí)間復(fù)雜度是O11/62O(1)O(n)O (n2)O (nlog2n).給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù) 雜度是OO(1)O(n)O (n2)O (

11、n*10g2n) 2.2填空題(將正確的答案填在相應(yīng)的空中)1.單鏈表可以做的鏈接存儲(chǔ)表示。.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 一另一個(gè)指向。.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)s (值為e)所指 結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：q=head; while (q-next!=p)q=q-next; s= new12 / 62Node;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-next

12、=_口 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ù)遞增有序。試13 / 62寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。Status Insert_SqList(SqList va,int x)if(va.length+1maxsize) return ERROR;va.length+;for(i=va.length-1;va.elemixii-)va.elemi+1=va.elemi;va.elemi+1=x;retur

13、n 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 i+,j-)tmp=ai;ai=aj;aj=tmp;14 / 623,已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一算法，刪除表中所有大于x且小于y的元素(若表中存在這樣的元素)同時(shí)釋放被刪除結(jié)點(diǎn)空間。void del(LinkList L,elemtype a,elemtype b) p= L;q=p-next;w

14、hile(q!=L q-dataa) p=q; q=q-next; while(q!=L q- datab) r=q; q=q-next; free(r); if(p!=q) p-next=q; 4,試寫一算法，實(shí)現(xiàn)單鏈表的就地逆置(要求在原鏈表上進(jìn) 行)。void converse(* L) * p,q; p=L-next; q=p-next;L-next=NULL; while(p) /*對(duì)于當(dāng)前結(jié)點(diǎn)p,用頭插法將結(jié)點(diǎn) p 插入至 U頭結(jié)點(diǎn)之后 */ p-next=L-next; L-next=p; p=q; q=q-next; 習(xí)題答案2.1BA, CBDCA15 / 62ABCD11.

15、B12.B13.A14.D15.B16.C2.2線性結(jié)表前驅(qū)結(jié)點(diǎn)、后繼結(jié)點(diǎn)s, pq-next,qp-next, s6.16 / 62O (1),O (n)習(xí)題3棧和隊(duì)列3.1單項(xiàng)選擇題1. 一個(gè)棧的入棧序列a, b, c, d, e,則棧的 不可能的輸出序列是edcbadecbaC.dceabD. abcde2.若已知一個(gè)棧的入棧序列是1, 2, 3, in,其輸出序列為 pl, p2 , p3 ,，pn ,若 p1=n，則 pi 為in=in-i+1D.不確定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)和非線

16、性存儲(chǔ)結(jié)構(gòu)4.判定一個(gè)順序棧ST (最多元素為m0)為空的條件是top !=017 / 62top= =0top !=m0top= =m0-1 5.判定一個(gè)順序棧 ST （最多元素為 m0）為 棧滿的條件是 Otop ! =0top= =0top ！ =m0top= =m0-1 6. 棧的特點(diǎn)是 隊(duì)列的特點(diǎn)是 oA.先進(jìn)先出B.先進(jìn)后出7.向一個(gè)棧頂指針為 HS的鏈棧中插入一個(gè)s 所指結(jié)點(diǎn)時(shí)，則執(zhí)行 。（不帶空的頭結(jié)點(diǎn)）A. HS- next=s; B. next= HS next;HS next=s; C. next= HS;HS=s; D. next= HS;HS= HS- next; 8

17、.從一個(gè)棧頂指針為 HS的鏈棧中刪除一 個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行18 / 62_O （不帶空的頭結(jié)點(diǎn)）x=HS;HS= HS-next;x=HS data; C. HS= HS next; x=HS data;D.x=HS data; HS= HS next; 9. 一個(gè)隊(duì)列的數(shù)據(jù)入列序 列是1, 2, 3, 4,則隊(duì)列的出隊(duì)時(shí)輸出序列是 o TOC o 1-5 h z A.4,3,2,1123414323,2,4,110.判定一個(gè)循環(huán)隊(duì)列 QU （最多元素為m0）為空的條件是 Orear - front= =m0rear-front-1= =m0 C. front= = rea

18、rD. front= = rear+1 11. 判定一個(gè)循環(huán)隊(duì)列 QU （最多元素為 m0, m0= =Maxsize-1 ）為滿隊(duì)列的條件是A. （rear- front）+ Maxsize）% Maxsize = =m0 B. rear-front-1 = =m0front= =rear19 / 62front= = rear+1 12,循環(huán)隊(duì)列用數(shù)組 A0, m-1存放其元 素值，已知其頭尾指針分別是 front和rear,則當(dāng)前隊(duì)列中的元 素個(gè)數(shù)是 o（rear-front+m）%mrear-front+1 C.rear-front-1D. rear-front 13.棧和隊(duì)列的共同點(diǎn)

19、是 A,都是先進(jìn)后出B,都是先進(jìn)先出 C,只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)3.2填空題（將正確的答案填在相應(yīng)的空中）1.向量、棧和隊(duì)列都是結(jié)構(gòu)，可以在向量的位置插入和刪除元素；對(duì)于棧 只能在插入和刪除元素；對(duì)于隊(duì)列只能在插入元素和 刪除元素。.向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素（1&i wn+1）之前 插入一個(gè)元素時(shí)，需向后移動(dòng) 一個(gè)元素。.向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素（1WiWn）時(shí)， 需向前移動(dòng)個(gè)元素。.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有一個(gè)元素。習(xí)題答案3.1C20 / 62CABDBACBCCAAC3.2線性、任何、棧頂、隊(duì)尾、隊(duì)首n-i+1n-in-1習(xí)題6樹和二

20、叉樹6.1單項(xiàng)選擇題1.由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2,所以21 / 62 二叉樹是一種特殊的樹，這種說法A,正確B.錯(cuò)誤2.假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分 支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為個(gè)。15161747 3,按照二叉樹的定義，具有 3個(gè)結(jié)點(diǎn)的不同形狀的 二叉樹有種。3456 4,按照二叉樹的定義，具有 3個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同 的二叉樹有種。563032 5,深度為5的二叉樹至多有個(gè)結(jié)點(diǎn)。A, 1622 / 62323110 6.設(shè)高度為h的二叉樹上只有度為 0和度為2的結(jié) 點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為2h2h-1C.2h+1D. h+1 7.對(duì)一個(gè)滿二叉樹，m

21、個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為 h,貝 U。n=h+mh+m=2nm=h-1n=2 h-1 8.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后 序遍歷序列中的相對(duì)次序 A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)9.如果某二叉樹的前根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs,那么該二叉樹的后序?yàn)?23 / 62uwvtsvwutswuvtswutsv 10.二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處 在其子女結(jié)點(diǎn)的前面，這種說法 OA.正確B.錯(cuò)誤11.某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是 abdgcefh ,中序遍歷的結(jié)點(diǎn)訪問順序是 dgbaechf ,則其后序遍歷 的結(jié)點(diǎn)訪問順序是 Obdgce

22、fhagdbecfhabdgaechfgdbehfca 12.在一非空二叉樹的中序遍歷序列中，根結(jié) 點(diǎn)的右邊 OA.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)13.如圖6.1所示二叉樹的中序遍歷序列是 Oabcdgefdfebagc24 / 62C. dbaefcgD. defbagc g c e f d b aa g e d b c h f 圖 6.2圖6.1a 14. 一棵二叉樹如圖6.2所示，其中序遍歷的序列為 _Oabdgcefhdgbaechfgdbehfcaabcdefgh a 15 .設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中

23、 序遍歷時(shí)，a在b前的條件是Oa在b的右方a在b的左方C. a是b的祖先D.a是b的子孫16.已知某二叉樹的后序遍歷序列是dabec ,中序遍歷序列是debac,它的前序遍歷序列是 acbeddecabdeabccedba 17.實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而25 / 62不使用棧結(jié)構(gòu)，最佳方案是二叉樹采用存儲(chǔ)結(jié)構(gòu)。A.二叉鏈表B.廣義表存儲(chǔ)結(jié)構(gòu)C.三叉鏈表D.順序存儲(chǔ)結(jié)構(gòu)18.如圖6.3所示的4棵二叉樹，不是完全二叉樹。(D)圖 6.320.在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件tleft=NULLt ltag=1 C. t ltag=1 且 t left=NULLD.以上

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

25、遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對(duì)25.樹最適合用來表示 oA.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù) 6.2填空題（將正確的答案填在相應(yīng)的空中）1.有一棵樹如圖6.5所示，回答下面的問題：k111 k k k27 / 62kkk214 3 5 67(1)這棵樹的根結(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è)主要差別 o 一 3.從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是1 2 3 4 5 6 7 8 9 1

26、0 11 12 13 14 15 16 17 18 19 20 21 e a f dg c j l h b 圖 6.6一棵二叉樹的順序存儲(chǔ)數(shù)組 t 4. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采 用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組 t中，如圖6,6所示，則該二叉樹 的鏈接表示形式為28 / 625,深度為k的完全二叉樹至少有一個(gè)結(jié)點(diǎn)。至多有一個(gè) 結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)(從 1開始)， 則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是 O.在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n 2,則有n0=。. 一棵二叉樹的第i (i 1)層最多有個(gè)結(jié)點(diǎn)；一棵有n(n0)個(gè)結(jié)點(diǎn)的滿二叉樹共有 一個(gè)葉子和個(gè)非

27、終端結(jié)點(diǎn)。8.結(jié)點(diǎn)最少的樹為 結(jié)點(diǎn)最少白二叉樹為 o9,現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc,問有種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是 O10.由如圖6,7所示的二叉樹，回答以下問題：i a e db c h H f圖6.7 一棵二叉樹i 其中序遍歷序列為 其前序遍歷序列為 o其后序遍歷序列為 6.3簡(jiǎn)答題1,根據(jù)二叉樹的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹有5種不同的形態(tài)，請(qǐng)將它們分別畫出。29 / 622.假設(shè)一棵 二叉樹的先序序列為*GIKJ和中序序列為 *HIJK。g c e f d b a 圖6.8 一棵樹請(qǐng)畫出該樹。3,由如圖6.7所示的二叉樹，回答以下問題：(1)畫出該二

28、叉樹的中序線索二叉樹；(2)畫出該二叉樹的后序線索二叉樹；(3)畫出該二叉樹對(duì)應(yīng)的森林。.已知一棵樹如圖6,8所示，轉(zhuǎn)化為一棵二叉樹，表示為.以數(shù)據(jù)集4, 5, 6, 7, 10, 12, 18為結(jié)點(diǎn)權(quán)值，畫出構(gòu) 造Huffman樹的每一步圖示，計(jì)算其帶權(quán)路徑長(zhǎng)度為。. 一棵含有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+1 6.4法設(shè)計(jì)題1.編寫按層次順序(同一層自左至右)遍歷二 叉樹的算法。.試編寫算法，對(duì)一棵二叉樹，統(tǒng)計(jì)葉子的個(gè)數(shù)。.試編寫算法，對(duì)一棵二叉樹根結(jié)點(diǎn)不變，將左、右子

29、樹 進(jìn)行交換，樹中每個(gè)結(jié)點(diǎn)的左、右子樹進(jìn)行交換。假設(shè)用于通訊的電文僅有八個(gè)字母(a,b,c,d,e,f,g,h)組成，30 / 62字母在電文中出現(xiàn)的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03,0.21, 0.10o試為這八個(gè)字母設(shè)計(jì)哈夫曼編碼。使用0-7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí) 例，比較兩種方案的優(yōu)缺點(diǎn)。試編寫算法，對(duì)一棵以孩子-兄弟鏈表表示的樹統(tǒng)計(jì)葉子 的個(gè)數(shù)。假設(shè)一棵二叉樹的先序序列為*GIKJ和中序序列為*HIJK。請(qǐng)畫出該樹。習(xí)題答案6.1BBCCCADACA 11. DAB31 / 62BBDCCBBBBBAC(1) k1 k

30、2,k5,k7,k4234 k5,k61（不同教k1e aE f j c d l g h b 圖6.9 2.樹的結(jié)點(diǎn)個(gè)數(shù)至少為32 / 62材規(guī)定不同），而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0;樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2;樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分；3.樹可采用孩子-兄弟 鏈表（二叉鏈表）做存儲(chǔ)結(jié)構(gòu)，目的并利用二叉樹的已有算法解 決樹的有關(guān)問題。4.如圖6.9所示5.2 k-1 、2 k-1、2 k-2+1n2+1i-12log2n+1-12log2n+1 T8.只有一個(gè)結(jié)點(diǎn)的樹；空的二叉樹 9.5;如圖6.10所示a圖6.10樹形5種a a a a c

31、c c c c b bb b b b 10. dgbaechif 、abdgcefhi 、gdbeihfca 、 6.31.33 / 625種，圖 6.11 E BE F AE C D K G H I J圖 6.12 圖 6.11 樹形 5 種 2.二叉樹如圖6.12所示。中序線索二叉樹如圖6.13 （左）所示；后序線索二叉樹如圖6.13 （右）所示；該二叉樹轉(zhuǎn)換后的的森林如圖6.14所示。圖 6.13 a 11 d hb k c 圖 6.14對(duì)應(yīng)的森林ie fa bc e d i g 圖 6.15一棵樹的孩子兄弟表示4.圖6.8的樹轉(zhuǎn)化為一棵二叉樹如下，圖6.15:34 / 62.畫出構(gòu)造H

32、uffman樹如圖6.16所示，計(jì)算其帶權(quán)路徑長(zhǎng) 度為O. 一棵含有N個(gè)結(jié)點(diǎn)的k叉樹,可能達(dá)到的最大深度 h=N- k+1 , 最小深度各為:logkN+1 。62 37 25 19 18 13 12 10 9 6 7 4 5 圖 6.16Huffman 樹習(xí)題7圖7.1項(xiàng)選擇題1.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有 邊數(shù)的傍。1/21242.任何一個(gè)無向連通圖的最小生成樹OA.只有一棵B.有一棵或多棵C. 一定有多棵35 / 62D.可能不存在3.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等 于所有頂點(diǎn)的出度之和的 傍。1/2124 4. 一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有 條邊。nn(n-1)n(n

33、-1)/22n 5.具有4個(gè)頂點(diǎn)的無向完全圖有 一條邊。6121620 6.具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有_條邊才能確保 是一個(gè)連通圖。5678 7 .在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn) 至少需要 條邊。36 / 62A. nn+1n-1n/2 8 .對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩 陣表示，則該矩陣的大小是 On(n-1)2n-1n2 9.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用 鄰接表表示，則表頭向量的大小為;所有鄰接表中的接點(diǎn)總數(shù)是。A. nn+1n-1n+e A. e/2B. eC.2eD. n+e10.已知一個(gè)圖如圖7.1所示，若從頂點(diǎn)a出發(fā)按深度搜索 法進(jìn)行遍

34、歷，則可能得到的一種頂點(diǎn)序列為一按寬度搜索37 / 62法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為 。 A. a,b,e,c,d,fe,c,f,e,b,da,e,b,c,f,da,e,d,f,c,b b a e c d f Ad,fe,b,c,e,a,b,c,e,f,da,e,b,c,f,da,c,f,d,e,b圖7.1一個(gè)無向圖11.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖7.2所示。2 3 4 5 3 2 4 5 2 4八八八八八圖7.2一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是v1,v2,v3,v5,v4v1,v2,v3,v4,v5 C. v1,v3

35、,v4,v5,v2D. v1,v4,v3,v5,v2楣居有向圖的寬度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是38 / 62v1,v2,v3,v4,v5v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4D. v1,v4,v3,v5,v2 12.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷 算法類似于二叉樹的OA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷13.采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法 類似于二叉樹的 OA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷14.判定一個(gè)有向圖是否存在回路除了可以利 用拓?fù)渑判蚍椒ㄍ?，還可以利用 OA.求關(guān)鍵路徑的方法B.求最短路徑的Dijkst

36、ra方法C.寬度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法15.關(guān)鍵路徑是絡(luò)中OA.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長(zhǎng)的回路39 / 62D.最短的回路16.下面不正確的說法是O(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.C.D. (1)、(2) 17.用DFS遍歷一個(gè)無環(huán)有向圖，并在 DFS 算法退棧返回時(shí)打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是OA.逆拓樸有序的B.拓樸有序的C.無序的18.在圖7.3所示的拓樸排列的結(jié)果序列為

37、A.*B.*C.*圖7.3有向圖40 / 6219. 一個(gè)有n個(gè)頂點(diǎn)的無向連通圖，它所包含的連通分量個(gè) 數(shù)為OA.0B.1C.nD.n+1 20.對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2,則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為OA.k1B.k2C.k1-k2D.k1+k2 21 .對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出 度為k2,則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為OA.k1B.k2C.k1-k2D.k1+k2 7.2填空題（將正確的答案填在相應(yīng)餓空中）1. n個(gè)頂點(diǎn)的連通圖至少條邊。41 / 62.在無權(quán)圖G的鄰接矩陣A中，若(vi,vj)或v vi,vj 屬于圖G的邊

38、集合，則對(duì)應(yīng)元素 Aij等于 否則等于.在無向圖G的鄰接矩陣A中，若Aij等于1,則Aji 等于_.已知圖G的鄰接表如圖7.4所示，其從頂點(diǎn)v1出發(fā)的深 度有限搜索序列為 其從頂點(diǎn)v1出發(fā)的寬度優(yōu)先搜索序列為Ov1 v3 v2 v4 v5 v6 v2 v5 v4 v3 v5 八八 v6 v4 v6 v3圖7.4圖G的鄰接表.已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 O.已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是 o.如果含n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則它有棵生成樹。. 一個(gè)非連通無向圖，共有 28條邊，則該圖至少有個(gè)頂點(diǎn)。.遍歷圖的過程實(shí)質(zhì)上是o BFS遍歷圖

39、的時(shí)間復(fù)雜度為42 / 62,DFS遍歷圖的時(shí)間復(fù)雜度為,兩者不同之處在于,反映在數(shù)據(jù)結(jié)構(gòu)上的差別是O. 一個(gè)圖的表示法是唯一的，而表示法是不唯一的。.有向圖中的結(jié)點(diǎn)前驅(qū)后繼關(guān)系的特征是O.若無向圖G的頂點(diǎn)度數(shù)最小值大于等于時(shí)，G至少有一條回路。.根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是的。7.3綜合題1 5 6 2 4 3 1 .已知如圖7.5所示的有向圖，請(qǐng)給出 該圖的：（1）每個(gè)頂點(diǎn)的入/出度；（2）鄰接距陣；（3）鄰接表；（4）逆鄰接表；（5）強(qiáng)連通分量。圖7。5一個(gè)有向圖b a d c e f 16 11 15 15 15 16 13 14 12 21 2.請(qǐng)用克魯斯卡爾

40、和普里姆兩種算法分別為圖 7.6、圖7.7構(gòu)造最小生成樹：43 / 62(1)圖7.661213212495201516106154372 (2)44 / 62圖7.7 3.試列出圖7.8中全部的拓?fù)渑判蛐蛄小? 2 3 4 5 6圖 7.8.請(qǐng)用圖示說明圖7.9從頂點(diǎn)a到其余各頂點(diǎn)之間的最短 路徑。4 3 2 2 3 3 5 6 a b d f ce圖7.9.已知 AOE 網(wǎng)有 9 個(gè)結(jié)點(diǎn)：V1, V2, V3, V4, V5, V6,V7, V8, V9,其鄰接矩陣如下：(1)請(qǐng)畫出該AOE圖。(2)計(jì)算完成整個(gè)計(jì)劃需要的時(shí)間。(3)求出該AOE網(wǎng)的關(guān)鍵路徑。0c 6 4 5 0c 0c 0c 0c 0c 0c 0