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

..數(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．操作對象Ｂ．計(jì)算方法Ｃ．邏輯結(jié)構(gòu)Ｄ．?dāng)?shù)據(jù)映象②A．存儲結(jié)構(gòu)Ｂ．關(guān)系Ｃ．運(yùn)算Ｄ．算法2.數(shù)據(jù)結(jié)構(gòu)DS<DataStruct>可以被形式地定義為DS=〔D,R,其中D是①的有限集合,R是D上的②有限集合。①A．算法Ｂ．?dāng)?shù)據(jù)元素Ｃ．?dāng)?shù)據(jù)操作Ｄ．?dāng)?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.算法分析的目的是①,算法分析的兩個(gè)主要方面是②。①A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性②A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡明性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)合稱為。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.分析下面算法〔程序段,給出最大語句頻度,該算法的時(shí)間復(fù)雜度是____。for<i=0;i<n;i++>for<j=0;j<n;j++>A[i][j]=0;8.分析下面算法〔程序段,給出最大語句頻度,該算法的時(shí)間復(fù)雜度是____。for<i=0;i<n;i++>for<j=0;j<i;j++>A[i][j]=0;9.分析下面算法〔程序段,給出最大語句頻度,該算法的時(shí)間復(fù)雜度是____。s=0;for<i=0;i<n;i++>for<j=0;j<n;j++>for<k=0;k<n;k++>s=s+B[i][j][k];sum=s;10.分析下面算法〔程序段給出最大語句頻度,該算法的時(shí)間復(fù)雜度是____。i=s=0;while<s<n>{i++;s+=i;//s=s+i}11.分析下面算法〔程序段給出最大語句頻度,該算法的時(shí)間復(fù)雜度是____。i=1;while<i<=n>i=i*2;1.3算法設(shè)計(jì)題試寫一算法,自大到小依次輸出順序讀入的三個(gè)數(shù)X,Y和Z的值.試寫一算法,求出n個(gè)數(shù)據(jù)中的最大值。寫出最大語句頻度,該算法的時(shí)間復(fù)雜度。習(xí)題答案1.11.C,A2.B,D3.C4.C,A5.C,B1.21.線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu),非線性結(jié)構(gòu)2.沒有、1、沒有、13.前驅(qū)、1、后續(xù)、任意多個(gè)4.任意多個(gè)5.一對一、一對多、多對多6.有窮性、確定性、可行性、輸入、輸出7.最大語句頻度：n2,時(shí)間復(fù)雜度：.O<n2>8.最大語句頻度：n<n+1>/2,時(shí)間復(fù)雜度：.O<n2>9.最大語句頻度：n3,時(shí)間復(fù)雜度：.O<n3>10.最大語句頻度：n,時(shí)間復(fù)雜度：.O<n>11.最大語句頻度：log2n,時(shí)間復(fù)雜度：.O<log2n>習(xí)題2線性表2.1單項(xiàng)選擇題1.一個(gè)向量〔即一批地址連續(xù)的存儲單元第一個(gè)元素的存儲地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址是____。A.110B.108C.100D.1202.線性表的順序存儲結(jié)構(gòu)是一種___的存儲結(jié)構(gòu),而鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種___的存儲結(jié)構(gòu)。A．隨機(jī)存取B．索引存取C．順序存取D．散列存取3.線性表的邏輯順序與存儲順序總是一致的,這種說法___。A.正確B.不正確4.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲單元的地址___。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以5.在以下的敘述中,正確的是___。線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)6.每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找,這種說法___。A.正確B.不正確7.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL8.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL9.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)〔由p所指向滿足____。A.p->next==NULLB.p==NULLC.p->next==headD.p==head10.在雙向循環(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->left=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),在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->next->next；14.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí),在查找成功的情況下,需平均比較____個(gè)結(jié)點(diǎn)。A.nB.n/2C.<n-1>/2D.<n+1>/215.在一個(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.單鏈表可以做____的鏈接存儲表示。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=newNode;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=____和p->next=____的操作。6.對于一個(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)位置上,以保持該表的有序性。StatusInsert_SqList<SqList&va,intx>{if<va.length+1>maxsize>returnERROR;va.length++;for<i=va.length-1;va.elem[i]>x&&i>=0;i-->va.elem[i+1]=va.elem[i];va.elem[i+1]=x;returnOK;}2.試寫一算法,實(shí)現(xiàn)順序表的就地逆置,即利用原表的存儲空間將線性表〔a1,a2,….an逆置為<an,an-1,….,a1>。voidreverse<inta[],intsize>{inti,j,tmp;for<i=0,j=size-1;i<j;i++,j-->{tmp=a[i];a[i]=a[j];a[j]=tmp;}}3.已知線性表中的元素以值遞增有序排列,并以單鏈表作存儲結(jié)構(gòu)。試寫一算法,刪除表中所有大于x且小于y的元素〔若表中存在這樣的元素同時(shí)釋放被刪除結(jié)點(diǎn)空間。voiddel<LinkListL,elemtypea,elemtypeb>

{

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)行>。voidconverse<NODEPTRL>

{

NODEPTRp,q;

p=L->next;q=p->next;

L->next=NULL;

while<p>

/*對于當(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.11.B2.A,C3.B4.D5.C6.A7.A8.B9.C10.D11.B12.B13.A14.D15.B16.C2.21.線性結(jié)表2.前驅(qū)結(jié)點(diǎn)、后繼結(jié)點(diǎn)3.s,p4.q->next,q5.p->next,s6.O<1>,O<n>習(xí)題3棧和隊(duì)列3.1單項(xiàng)選擇題1.一個(gè)棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是____。A.edcbaB.decbaC.dceabD.abcde2.若已知一個(gè)棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為____。A.iB.n=iC.n-i+1D.不確定3.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是____。A.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)散列方式和索引方式鏈表存儲結(jié)構(gòu)和數(shù)組線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)4.判定一個(gè)順序棧ST〔最多元素為m0為空的條件是____。A.top!=0B.top==0C.top!=m0D.top==m0-5.判定一個(gè)順序棧ST〔最多元素為m0為棧滿的條件是____。A.top！=0B.top==0C.top！=m0D.top==m0-16.棧的特點(diǎn)是____,隊(duì)列的特點(diǎn)是____。A.先進(jìn)先出B.先進(jìn)后出7.向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí),則執(zhí)行____。<不帶空的頭結(jié)點(diǎn)>HS—＞next=s;B.s—＞next=HS—＞next;HS—＞next=s;C.s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞next;8.從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用x保存被刪結(jié)點(diǎn)的值,則執(zhí)行____。<不帶空的頭結(jié)點(diǎn)>A.x=HS;HS=HS—＞next;B.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í)輸出序列是____。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,110.判定一個(gè)循環(huán)隊(duì)列QU〔最多元素為m0為空的條件是____。A.rear-front==m0B.rear-front-1==m0C.front==rearD.front==rear+111.判定一個(gè)循環(huán)隊(duì)列QU〔最多元素為m0,m0==Maxsize-1為滿隊(duì)列的條件是____。A.<<rear-front>+Maxsize>%Maxsize==m0B.rear-front-1==m0C.front==rearD.front==rear+112.循環(huán)隊(duì)列用數(shù)組A[0,m-1]存放其元素值,已知其頭尾指針分別是front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是____。A.<rear-front+m>%mB.rear-front+1C.rear-front-1D.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ì)列只能在____插入元素和____刪除元素。2.向一個(gè)長度為n的向量的第i個(gè)元素〔1≤i≤n+1之前插入一個(gè)元素時(shí),需向后移動____個(gè)元素。3.向一個(gè)長度為n的向量中刪除第i個(gè)元素〔1≤i≤n時(shí),需向前移動____個(gè)元素。4.在具有n個(gè)單元的循環(huán)隊(duì)列中,隊(duì)滿時(shí)共有____個(gè)元素。習(xí)題答案3.11.C2.C3.A4.B5.D6.BA7.C8.B9.C10.C11.A12.A13.C3.21.線性、任何、棧頂、隊(duì)尾、隊(duì)首2.n-i+13.n-i4.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è)。A．15 B．16 C．17 D．473.按照二叉樹的定義,具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有____種。A.3B.4C.5D.64.按照二叉樹的定義,具有3個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有____種。A.5B.6C.30D.325.深度為5的二叉樹至多有____個(gè)結(jié)點(diǎn)。A.16B.32C.31D.106.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn),則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為____。 A.2hB.2h-1C.2h+1D.h+17.對一個(gè)滿二叉樹,m個(gè)樹葉,n個(gè)結(jié)點(diǎn),深度為h,則____。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-18.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序____。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對9.如果某二叉樹的前根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs,那么該二叉樹的后序?yàn)開___。A.uwvtsB.vwutsC.wuvtsD.wutsv10.二叉樹的前序遍歷序列中,任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面,這種說法____。A.正確B.錯(cuò)誤11.某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問順序是____。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca12.在一非空二叉樹的中序遍歷序列中,根結(jié)點(diǎn)的右邊____。A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)13.如圖6.1所示二叉樹的中序遍歷序列是____。A.abcdgefB.dfebagcC.dbaefcgD.defbagcggcefdbaaagedbchf圖6.2圖6.1a14.一棵二叉樹如圖6.2所示,其中序遍歷的序列為____。aA.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgha15．設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn),在中序遍歷時(shí),a在b前的條件是。aA．a(chǎn)在b的右方 B．a(chǎn)在b的左方C．a(chǎn)是b的祖先 D．a(chǎn)是b的子孫16.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是____。A.acbedB.decabC.deabcD.cedba17.實(shí)現(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><A><B><C><D>圖6.320.在線索化二叉樹中,t所指結(jié)點(diǎn)沒有左子樹的充要條件是____。A.t—＞left=NULLB.t—＞ltag=1C.t—＞ltag=1且t—＞left=NULLD.以上都不對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.10B.12C.15D.1724.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里,我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對應(yīng)的二叉樹。結(jié)論____是正確的。A.樹的先根遍歷序列與其對應(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所示,回答下面的問題：k111k111kkkkkk2143567⑵這棵樹的葉子結(jié)點(diǎn)是____；⑶結(jié)點(diǎn)k3的度是____；圖6.5一棵樹⑷這棵樹的度是____；圖6.5一棵樹⑸這棵樹的深度是____；⑹結(jié)點(diǎn)k3的子女是____；⑺結(jié)點(diǎn)k3的父結(jié)點(diǎn)是__2.指出樹和二叉樹的三個(gè)主要差別____、____、____。__；3.從概念上講,樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu),將樹轉(zhuǎn)化為二叉樹的基本目的是____。12345678123456789101112131415161718192021eafdgcjlhb圖6.6一棵二叉樹的順序存儲數(shù)組t5.深度為k的完全二叉樹至少有____個(gè)結(jié)點(diǎn)。至多有____個(gè)結(jié)點(diǎn),若按自上而下,從左到右次序給結(jié)點(diǎn)編號〔從1開始,則編號最小的葉子結(jié)點(diǎn)的編號是____。6.在一棵二叉樹中,度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則有n0=____。7.一棵二叉樹的第i〔i≥1層最多有____個(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所示的二叉樹,回答以下問題：iae iae d bchHf圖6.7一棵二叉樹i⑵其前序遍歷序列為____；⑶其后序遍歷序列為____；6.3簡答題1.根據(jù)二叉樹的定義,具有三個(gè)結(jié)點(diǎn)的二叉樹有5種不同的形態(tài),請將它們分別畫出。2.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。gcgcefdba圖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é)點(diǎn)權(quán)值,畫出構(gòu)造Huffman樹的每一步圖示,計(jì)算其帶權(quán)路徑長度為。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．試編寫算法,對一棵二叉樹,統(tǒng)計(jì)葉子的個(gè)數(shù)。3．試編寫算法,對一棵二叉樹根結(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)制表示形式是另一種編碼方案。對于上述實(shí)例,比較兩種方案的優(yōu)缺點(diǎn)。8.試編寫算法,對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計(jì)葉子的個(gè)數(shù)。假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請畫出該樹。習(xí)題答案6.11.B2.B3.C4.C5.C6.A7.D8.A9.C10.A11.D2.A13.B14.B15.B16.D17.C18.C19.B20.B21.B22.B23.B24.A25.C6.21.⑴k1⑵k2,k5,k7,k4⑶2⑷3⑸4⑹k5,k6⑺k1eaEfjcdeaEfjcdlghb圖6.9樹中結(jié)點(diǎn)的最大度數(shù)沒有限制,而二叉樹結(jié)點(diǎn)的最大度數(shù)為2；樹的結(jié)點(diǎn)無左、右之分,而二叉樹的結(jié)點(diǎn)有左、右之分；3.樹可采用孩子-兄弟鏈表〔二叉鏈表做存儲結(jié)構(gòu),目的并利用二叉樹的已有算法解決樹的有關(guān)問題。4.如圖6.9所示5.2k-1、2k-1、2k-2+16.n2+17.2i-12[log2n+1]-12[log2n+1]–18.只有一個(gè)結(jié)點(diǎn)的樹；空的二叉樹9.5；如圖6.10所示a圖6.10樹形5種aaaaa圖6.10樹形5種aaaacccccbbbbbb6.31.5種,圖6.11EBEFEBEFAECDKGHIJ圖6.12圖6.11樹形5種3.中序線索二叉樹如圖6.13〔左所示；后序線索二叉樹如圖6.13〔右所示；該二叉樹轉(zhuǎn)換后的的森林如圖6.14所示。圖6.13圖6.13aa11dhjbkc圖6.14對應(yīng)的森林iefababcedig圖6.15一棵樹的孩子兄弟表示5.畫出構(gòu)造Huffman樹如圖6.16所示,計(jì)算其帶權(quán)路徑長度為。6.一棵含有N個(gè)結(jié)點(diǎn)的k叉樹,可能達(dá)到的最大深度h=N-k+1,最小深度各為:logkN+1。62623725191813121096745圖6.16Huffman樹習(xí)題7圖7.1單項(xiàng)選擇題1．在一個(gè)圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的____倍。A.1/2B.1C.2D.42．任何一個(gè)無向連通圖的最小生成樹。A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在3．在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的____倍。A.1/2B.1C.2D.44．一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有____條邊。A.nB.n<n-1>C.n<n-1>/2D.2n5．具有4個(gè)頂點(diǎn)的無向完全圖有____條邊。A.6B.12C.16D.206．具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有____條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.87．在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中,要連通全部頂點(diǎn)至少需要____條邊。A.nB.n+1C.n-1D.n/28．對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖,若采用鄰接矩陣表示,則該矩陣的大小是____。A.nB.<n-1>2C.n-1D.n9．對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖,若采用鄰接表表示,則表頭向量的大小為_①___；所有鄰接表中的接點(diǎn)總數(shù)是_②___。①A.nB.n+1C.n-1D.n+e②A.e/2B.eC.2eD.n+e10．已知一個(gè)圖如圖7.1所示,若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷,則可能得到的一種頂點(diǎn)序列為__①__；按寬度搜索法進(jìn)行遍歷,則可能得到的一種頂點(diǎn)序列為__②__。①A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,bbaebaecdf圖7.1一個(gè)無向圖圖7.1一個(gè)無向圖11．已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖7.2所示。112345324524^^^^^圖7.2一個(gè)有向圖的鄰接表存儲結(jié)構(gòu)圖7.2一個(gè)有向圖的鄰接表存儲結(jié)構(gòu)⑴根據(jù)有向圖的深度優(yōu)先遍歷算法,從頂點(diǎn)v1出發(fā),所得到的頂點(diǎn)序列是____。A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2⑵根據(jù)有向圖的寬度優(yōu)先遍歷算法,從頂點(diǎn)v1出發(fā),所得到的頂點(diǎn)序列是____。A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v212．采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的____。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷13．采用鄰接表存儲的圖的寬度優(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)的最長路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長的回路D.最短的回路16．下面不正確的說法是?！?在AOE網(wǎng)中,減小一個(gè)關(guān)鍵活動上的權(quán)值后,整個(gè)工期也就相應(yīng)減小；〔2AOE網(wǎng)工程工期為關(guān)鍵活動上的權(quán)之和；〔3在關(guān)鍵路徑上的活動都是關(guān)鍵活動,而關(guān)鍵活動也必在關(guān)鍵路徑上。A.〔1 B.〔2 C.〔3 D.〔1、〔217．用DFS遍歷一個(gè)無環(huán)有向圖,并在DFS算法退棧返回時(shí)打印出相應(yīng)的頂點(diǎn),則輸出的頂點(diǎn)序列是。A.逆拓樸有序的 B.拓樸有序的 C.無序的18．在圖7.3所示的拓樸排列的結(jié)果序列為。A.125634 B.516234 C.123456 D.521634圖7.3有向圖圖7.3有向圖19．一個(gè)有n個(gè)頂點(diǎn)的無向連通圖,它所包含的連通分量個(gè)數(shù)為。A.0 B.1 C.n D.n+120．對于一個(gè)有向圖,若一個(gè)頂點(diǎn)的入度為k1,、出度為k2,則對應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為。A.k1 B.k2 C.k1-k2 D.k1+k221．對于一個(gè)有向圖,若一個(gè)頂點(diǎn)的入度為k1,、出度為k2,則對應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為。A.k1 B.k2 C.k1-k2 D.k1+k27.2填空題〔將正確的答案填在相應(yīng)餓空中1．n個(gè)頂點(diǎn)的連通圖至少____條邊。2．在無權(quán)圖G的鄰接矩陣A中,若<vi,vj>或＜vi,vj＞屬于圖G的邊集合,則對應(yīng)元素A[i][j]等于____,否則等于____。3．在無向圖G的鄰接矩陣A中,若A[i][j]等于1,則A[j][i]等于____。4．已知圖G的鄰接表如圖7.4所示,其從頂點(diǎn)v1出發(fā)的深度有限搜索序列為____,其從頂點(diǎn)v1出發(fā)的寬度優(yōu)先搜索序列為____。v1v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3圖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è)非連通無向圖,共有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．若無向圖G的頂點(diǎn)度數(shù)最小值大于等于時(shí),G至少有一條回路。13．根據(jù)圖的存儲結(jié)構(gòu)進(jìn)行某種次序的遍歷,得到的頂點(diǎn)序列是的。7.3綜合題15156243〔1每個(gè)頂點(diǎn)的入/出度；〔2鄰接距陣；〔3鄰接表；〔4逆鄰接表；〔5強(qiáng)連通分量。圖7。5一個(gè)有向圖圖7。5一個(gè)有向圖babadcef16111515151613141221〔1圖7.661261213212495201516106154372圖7.73．試列出圖7.8中全部的拓?fù)渑判蛐蛄小?123456圖7.84．請用圖示說明圖7.9從頂點(diǎn)a到其余各頂點(diǎn)之間的最短路徑。5543223356abdfce圖7.95．已知AOE網(wǎng)有9個(gè)結(jié)點(diǎn)：V1,V2,V3,V4,V5,V6,V7,V8,V9,其鄰接矩陣如下：<1>請畫出該AOE圖。<2>計(jì)算完成整個(gè)計(jì)劃需要的時(shí)間。<3>求出該AOE網(wǎng)的關(guān)鍵路徑?！?45∝∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝∝97∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝習(xí)題答案7.1 1.C 2.B 3.B 4.C 5.A 6.A 7.C8.D 9.AC 10.DB 11.CB 12.A 13.D 14.D 15.A 16.A 17.A 18.B 19.B 20.B 21.A7.21.n-12.1;03.14.v1,v2,v3,v6,v5,v4；v1,v2,v5,v4,v3,v65.求矩陣第i列非零元素之和6.將矩陣第i行全部置為零7.n8.99.對每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程；O〔e〔e為圖中的邊數(shù)；O〔e；遍歷圖的順序不同；DFS采用棧存儲訪問過的結(jié)點(diǎn),BFS采用隊(duì)列存儲訪問過的結(jié)點(diǎn)。10．鄰接矩陣鄰接表11．一個(gè)結(jié)點(diǎn)可能有若干個(gè)前驅(qū),也可能有若干個(gè)后繼12．213．唯babadce1115131412f6612495106154372〔23．152364152634156234561234516234512634512364W=3W=7W=3W=7W=9W=6W=543233abdfce5．<1>該AOE圖為：<2>完成整個(gè)計(jì)劃需要18天。<3>關(guān)鍵路徑為：〔V1,V2,V5,V7,V9和〔V1,V2,V5,V8,V9,習(xí)題8查找8.1單項(xiàng)選擇題1.順序查找法適合于存儲結(jié)構(gòu)為____的線性表。A.散列存儲B.順序存儲或鏈接存儲C.壓縮存儲D.索引存儲2.對線性表進(jìn)行二分查找時(shí),要求線性表必須____。A.以順序方式存儲B.以鏈接方式存儲C.以順序方式存儲,且結(jié)點(diǎn)按關(guān)鍵字有序排序D.以鏈接方式存儲,且結(jié)點(diǎn)按關(guān)鍵字有序排序3.采用順序查找方法查找長度為n的線性表時(shí),每個(gè)元素的平均查找長度為____.A.nB.n/2C.<n+1>/2D.<n-1>/24.采用二分查找方法查找長度為n的線性表時(shí),每個(gè)元素的平均查找長度為____。A．O〔n2B.O<nlog2n>C.O<n>D.O<log2n>5.二分查找和二叉排序樹的時(shí)間性能____。A.相同B.不相同6.有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值82為的結(jié)點(diǎn)時(shí),____次比較后查找成功。A.1B.2C.4D.87.設(shè)哈希表長m=14,哈希函數(shù)H<key>=key%11。表中已有4個(gè)結(jié)點(diǎn)：addr<15>=4;addr<38>=5;addr<61>=6;addr<84>=7如用二次探測再散列處理沖突,關(guān)鍵字為49的結(jié)點(diǎn)的地址是____。A.8B.3C.5D.98.有一個(gè)長度為12的有序表,按二分查找法對該表進(jìn)行查找,在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為____。A.35/12B.37/12C.39/12D.43/129．對于靜態(tài)表的順序查找法,若在表頭設(shè)置崗哨,則正確的查找方式為。A.從第0個(gè)元素往后查找該數(shù)據(jù)元素B.從第1個(gè)元素往后查找該數(shù)據(jù)元素C.從第n個(gè)元素往開始前查找該數(shù)據(jù)元素D.與查找順序無關(guān)10．解決散列法中出現(xiàn)的沖突問題常采用的方法是。A.數(shù)字分析法、除余法、平方取中法B.數(shù)字分析法、除余法、線性探測法C.數(shù)字分析法、線性探測法、多重散列法D.線性探測法、多重散列法、鏈地址法11．采用線性探測法解決沖突問題,所產(chǎn)生的一系列后繼散列地址。A.必須大于等于原散列地址B.必須小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小沒有具體限制12．對于查找表的查找過程中,若被查找的數(shù)據(jù)元素不存在,則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于。A.靜態(tài)查找表 B.動態(tài)查找表 C.靜態(tài)查找表與動態(tài)查找表 D兩種表都不適合13.散列表的平均查找長度。A.與處理沖突方法有關(guān)而與表的長度無關(guān)B.與處理沖突方法無關(guān)而與表的長度有關(guān)C.與處理沖突方法有關(guān)而與表的長度有關(guān)D.與處理沖突方法無關(guān)而與表的長度無關(guān)8.2填空題〔將正確的答案填在相應(yīng)的空中1.順序查找法的平均查找長度為____；折半查找法的平均查找長度為____；哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長度為____。2.在各種查找方法中,平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是____。3.折半查找的存儲結(jié)構(gòu)僅限于____,且是____。4.假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找,則比較一次查找成功的結(jié)點(diǎn)數(shù)為____,則比較二次查找成功的結(jié)點(diǎn)數(shù)為____,則比較三次查找成功的結(jié)點(diǎn)數(shù)為____,則比較四次查找成功的結(jié)點(diǎn)數(shù)為____,則比較五次查找成功的結(jié)點(diǎn)數(shù)為____,平均查找長度為____。5.對于長度為n的線性表,若進(jìn)行順序查找,則時(shí)間復(fù)雜度為____；若采用折半法查找,則時(shí)間復(fù)雜度為____；6．已知有序表為〔12,18,24,35,47,50,62,83,90,115,134,當(dāng)用折半查找90時(shí),需進(jìn)行次查找可確定成功；查找47時(shí),需進(jìn)行次查找成功；查找100時(shí),需進(jìn)行次查找才能確定不成功。7．二叉排序樹的查找長度不僅與有關(guān),也與二叉排序樹的有關(guān)。8．一個(gè)無序序列可以通過構(gòu)造一棵樹而變成一個(gè)有序樹,構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。9．平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是、或。10．法構(gòu)造的哈希函數(shù)肯定不會發(fā)生沖突。11．在散列函數(shù)H<key>=key%p中,p應(yīng)取____。12．在散列存儲中,裝填因子的值越大,則____；的值越小,則____。8.3綜合練習(xí)題:1.畫出對長度為10的有序表進(jìn)行折半查找的判定樹,并求其等概率時(shí)查找成功的平均查找長度。4.選取哈稀函數(shù)H〔k=〔3kMOD11。用開放定址法處理沖突,di=i〔〔7kMOD10+1〔I=1,2,3,….試在0-10的散列地址空間中對關(guān)鍵字序列〔22,41,53,46,30,13,01,67造哈希表,并求等概率情況下查找成功時(shí)的平均查找長度。5.已知一組關(guān)鍵字{49,38,65,97,76,13,27,44,82,35,50},畫出由此生成的二叉排序樹,注意邊插入邊平衡。習(xí)題答案8.11．B2．C3．C4．D5．B6．C7．D8．B9．C10．D11．C12．B13．C8.21.〔n+1/2、<<n+1>*log2<n+1>>/n-1、1+〔為裝填因子2.哈希表查找法3.順序存儲結(jié)構(gòu)、有序的4.1、2、4、8、5、3．7〔依題意,構(gòu)造一棵有序二叉樹,共12個(gè)結(jié)點(diǎn),第一層1個(gè)結(jié)點(diǎn),第二層2個(gè)結(jié)點(diǎn),第三層4個(gè)結(jié)點(diǎn),第四層5個(gè)結(jié)點(diǎn),則：ASL=〔1*1+2*2+3*4+4*5/12=37/125.O〔n、O<log2n>6．2、4、37．結(jié)點(diǎn)個(gè)數(shù)n、生成過程8．二叉排序樹9．0、1、-110．直接定址11．素?cái)?shù)12．存取元素時(shí)發(fā)生沖突的可能性就越大、存取元素時(shí)發(fā)生沖突的可能性就越小習(xí)題9排序9.1單項(xiàng)選擇題1.在所有排序方法中,關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是____。A.希爾排序B.起泡排序C.插入排序D.選擇排序2.設(shè)有1000個(gè)無序的元素,希望用最快的速度挑選出其中前10個(gè)最大的元素,最好選用____排序法。A.起泡排序B.快速排序C.堆排序D.基數(shù)排序3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是____。A.插入排序B.選擇排序C.快速排序D.歸并排序4.一組記錄的排序碼為〔46,79,56,38,40,84,則利用堆排序的方法建立的初始堆為____。A.79,46,56,38,40,80B.38,46,56,79,40,84,C.84,79,56,46,40,38D.84,56,79,40,46,385.一組記錄的關(guān)鍵碼為〔46,79,56,38,40,84,則利用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為____。A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,796.一組記錄的排序碼為〔25,48,16,35,79,82,23,40,36,72,其中含有5個(gè)