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

數(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．存儲(chǔ)結(jié)構(gòu)Ｂ．關(guān)系Ｃ．運(yùn)算Ｄ．算法2.數(shù)據(jù)結(jié)構(gòu)DS(DataStruct)能夠被形式地定義為DS=〔D，R〕，其中D是①的有限會(huì)合，R是D上的②有限集合。①A．算法Ｂ．?dāng)?shù)據(jù)元素Ｃ．?dāng)?shù)據(jù)操作Ｄ．?dāng)?shù)據(jù)對象②A．操作Ｂ．映象Ｃ．存儲(chǔ)Ｄ．關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上能夠把數(shù)據(jù)結(jié)構(gòu)分紅。A．動(dòng)向結(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)動(dòng)方法②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ì)題1.試寫一算法,自傲到小依次輸出次序讀入的三個(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)沒有、1、沒有、1前驅(qū)、1、后續(xù)、隨意多個(gè)隨意多個(gè)一對一、一對多、多對多有窮性、確定性、可行性、輸入、輸出最大語句頻度：n2，時(shí)間復(fù)雜度：.O(n2)8.最大語句頻度：n(n+1)/2，時(shí)間復(fù)雜度：.O(n2)9.最大語句頻度：n3，時(shí)間復(fù)雜度：.O(n3)1110.最大語句頻度：n2，時(shí)間復(fù)雜度：.O(n2)11.最大語句頻度：logn，時(shí)間復(fù)雜度：.O(logn)22習(xí)題2線性表2.1單項(xiàng)選擇題1.一個(gè)向量〔即一批地點(diǎn)連續(xù)的存儲(chǔ)單元〕第一個(gè)元素的存儲(chǔ)地點(diǎn)是100，每個(gè)元素的長度為2，那么第5個(gè)元素的地點(diǎn)是____。A.110B.108C.100D.1202.線性表的次序存儲(chǔ)結(jié)構(gòu)是一種___的存儲(chǔ)結(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ǔ)單元的地點(diǎn)___。A.必須是連續(xù)的B.局部地點(diǎn)必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都能夠在以下的表達(dá)中，正確的選項(xiàng)是___。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ù)元素的情況線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于次序存儲(chǔ)結(jié)構(gòu)6.每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)根本運(yùn)算：插入、刪除和查找，這種說法___。A.正確B.不正確精選不帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL非空的循環(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)，那么履行____。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)，那么履行____。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)，那么履行____。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)的空中〕單鏈表能夠做____的鏈接存儲(chǔ)表示。2.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向______，另一個(gè)指向_____。3.在一個(gè)單鏈表中p所指結(jié)點(diǎn)以前插入一個(gè)s(值為e)所指結(jié)點(diǎn)時(shí)，可履行如下操作：q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=;//填空s->next=;//填空在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)履行以下操作：q=p->next;p->next=____;//填空delete;//填空5.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)履行s->next=____和p->next=____的操作。6.關(guān)于一個(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插入到次序表的適合地點(diǎn)上，以保持該表的有序性。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)次序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表〔a1,a2,.nn,an-1,.,1)。a〕逆置為(aavoidreverse(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.線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(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;}試寫一算法，實(shí)現(xiàn)單鏈表的就地逆置(要求在原鏈表上進(jìn)行)。voidconverse(NODEPTRL){NODEPTRp,q;p=L->next;q=p->next;L->next=NULL;while(p)/*關(guān)于目前結(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棧和行列3.1單項(xiàng)選擇題一個(gè)棧的入棧序列a，b，c，d，e，那么棧的不可能的輸出序列是____。A.edcbaB.decbaC.dceabD.abcde假定一個(gè)棧的入棧序列是1，2，3，，n，其輸出序列為p1，p2，p3，，pn，假定p1=n，那么pi為____。A.iB.n=iC.n-i+1D.不確定棧結(jié)構(gòu)往常采用的兩種存儲(chǔ)結(jié)構(gòu)是____。次序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)散列方式和索引方式鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)判斷一個(gè)次序棧ST〔最多元素為m0〕為空的條件是____。A.top!=0B.top==0C.top!=m0D.top==m0-1判斷一個(gè)次序棧ST〔最多元素為m0〕為棧滿的條件是____。A.top！=0B.top==0C.top！=m0D.top==m0-1棧的特點(diǎn)是____，行列的特點(diǎn)是____。A.先進(jìn)先出B.先進(jìn)后出7.向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，那么履行____。(不帶空的頭結(jié)點(diǎn))HS—＞next=s;s—＞next=HS—＞next;HS—＞next=s;s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞next;8.從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保留被刪結(jié)點(diǎn)的值，那么履行____。(不帶空的頭結(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è)行列的數(shù)據(jù)入列序列是1，2，3，4，那么行列的出隊(duì)時(shí)輸出序列是____。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，1判斷一個(gè)循環(huán)行列QU〔最多元素為m0〕為空的條件是____。A.rear-front==m0B.rear-front-1==m0C.front==rearD.front==rear+111.判斷一個(gè)循環(huán)行列QU〔最多元素為m0,m0==Maxsize-1〕為滿行列的條件是____。A.((rear-front)+Maxsize)%Maxsize==m0B.rear-front-1==m0C.front==rearD.front==rear+112.循環(huán)行列用數(shù)組A[0，m-1]寄存其元素值，其頭尾指針分別是front和rear，那么目前行列中的元素個(gè)數(shù)是____。(rear-front+m)%mrear-front+1C.rear-front-1rear-front棧和行列的共同點(diǎn)是____。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)精選3.2填空題〔將正確的答案填在相應(yīng)的空中〕向量、棧和行列都是____結(jié)構(gòu)，能夠在向量的____地點(diǎn)插入和刪除元素；關(guān)于棧只能在____插入和刪除元素；關(guān)于行列只能在____插入元素和____刪除元素。2.向一個(gè)長度為n的向量的第i個(gè)元素〔1≤i≤n+1〕以前插入一個(gè)元素時(shí)，需向后移動(dòng)____個(gè)元素。3.向一個(gè)長度為n的向量中刪除第i個(gè)元素〔1≤i≤n〕時(shí)，需向前移動(dòng)____個(gè)元素。4.在擁有n個(gè)單元的循環(huán)行列中，隊(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．15B．16C．17D．473.按照二叉樹的定義，擁有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有____種。A.3B.4C.5D.64.按照二叉樹的定義，擁有3個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有____種。A.5B.6C.30D.32深度為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+1對一個(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.defbagcaabcbdgcdeef圖6.1ghf14.一棵二叉樹如圖6.2所示，其中序遍歷的序列為____。A.圖6.2abdgcefhB.dgbaechfaD.C.gdbehfcaabcdefgh精選15．設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是。A．a(chǎn)在b的右方B．a(chǎn)在b的左方C．a(chǎn)是b的祖先D．a(chǎn)是b的后代某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是____。A.acbedB.decabC.deabcD.cedba17.實(shí)現(xiàn)隨意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最正確方案是二叉樹采用____存儲(chǔ)結(jié)構(gòu)。A.二叉鏈表B.廣義表存儲(chǔ)結(jié)構(gòu)C.三叉鏈表D.次序存儲(chǔ)結(jié)構(gòu)如圖6.3所示的4棵二叉樹，____不是完全二叉樹。(A)(B)(C)(D)圖6.3在線索化二叉樹中，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ò)誤擁有五層結(jié)點(diǎn)的二叉平衡樹起碼有____個(gè)結(jié)點(diǎn)。A.10B.12C.15D.17樹的根本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的根本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)變獲得的二叉樹叫做這棵數(shù)對應(yīng)的二叉樹。結(jié)論____是正確的。樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對樹最適合用來表示____。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間擁有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.2填空題〔將正確的答案填在相應(yīng)的空中〕有一棵樹如圖6.5所示，回復(fù)下面的問題：⑴這棵樹的根結(jié)點(diǎn)是____；⑵這棵樹的葉子結(jié)點(diǎn)是____；⑶結(jié)點(diǎn)k3的度是____；⑷這棵樹的度是____；⑸這棵樹的深度是____；⑹結(jié)點(diǎn)k3的兒女是____；⑺結(jié)點(diǎn)k3的父結(jié)點(diǎn)是__

k1k2k3k4k5k6圖6.5一棵樹k7指出樹和二叉樹的三個(gè)主要差別____、____、____。__；3.從觀點(diǎn)上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)變?yōu)槎鏄涞幕灸康氖莀___。4.一棵二叉樹的結(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開123456789101112131415161718192021eafdgcj精選lhb圖6.6一棵二叉樹的次序存儲(chǔ)數(shù)組t始〕，那么編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是____。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)。結(jié)點(diǎn)最少的樹為____，結(jié)點(diǎn)最少的二叉樹為____?，F(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有____種不同形態(tài)的二叉樹能夠獲得這一遍歷結(jié)果，這些二叉樹分別是____。由如圖6.7所示的二叉樹，回復(fù)以下問題：⑴其中序遍歷序列為____；a⑵其前序遍歷序列為____；⑶后來序遍歷序列為____；bcdefh6.3簡答題i1.根據(jù)二叉樹的定義，擁有三個(gè)結(jié)點(diǎn)的二叉樹有5種不同的形態(tài)，請將它們分別畫出。圖6.7一棵二叉樹2.假定一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請畫出該樹。3.由如圖6.7所示的二叉樹，回復(fù)以下問題：a〔1〕畫出該二叉樹的中序線索二叉樹；〔2〕畫出該二叉樹的后序線索二叉樹；〔3〕畫出該二叉樹對應(yīng)的森林。bcd4.一棵樹如圖6.8所示，轉(zhuǎn)變?yōu)橐豢枚鏄洌硎緸開___。efg圖6.8一棵樹5.以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值，畫出結(jié)構(gòu)Huffman樹的每一步圖示，計(jì)算其帶權(quán)路徑長度為。一棵含有N個(gè)結(jié)點(diǎn)的k叉樹,可能抵達(dá)的最大深度和最小深度各為多少?7.證明:一棵滿k叉樹上的葉子結(jié)點(diǎn)數(shù)n0和非葉子結(jié)點(diǎn)數(shù)n1之間知足以下關(guān)系

:n

0=(k-1)n

1+16.4算法設(shè)計(jì)題編寫按層次次序〔同一層自左至右〕遍歷二叉樹的算法。．試編寫算法，對一棵二叉樹,統(tǒng)計(jì)葉子的個(gè)數(shù)。．試編寫算法，對一棵二叉樹根結(jié)點(diǎn)不變，將左、右子樹進(jìn)行互換，樹中每個(gè)結(jié)點(diǎn)的左、右子樹進(jìn)行互換。7.假定用于通訊的電文僅有八個(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)制表示形式是另一種編碼方案。關(guān)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。8.試編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計(jì)葉子的個(gè)數(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⑺k12.樹的結(jié)點(diǎn)個(gè)數(shù)起碼為1(不同教材規(guī)定不同)，而二e叉樹的結(jié)點(diǎn)個(gè)數(shù)能夠?yàn)?；樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2；樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右af之分；3.樹可采用孩子-兄弟鏈表〔二叉鏈表〕做存儲(chǔ)結(jié)構(gòu)，目的并利用二叉樹的已有算法解決樹的有關(guān)問題。dg4.如圖6.9所示cjlh精選b圖6.95.2k-1、2k-1、2k-2+16.n2+17.2i-12[logn+1]-12[logn+1]–122只有一個(gè)結(jié)點(diǎn)的樹；空的二叉樹5；如圖6.10所示ccaabbabcacabcb圖6.10樹形5種10.dgbaechif、abdgcefhi、gdbeihfca、6.31.5種,圖6.112.二叉樹如圖6.12所示。圖6.11樹形5種EBFADH3.中序線索二叉樹如圖6.13〔左〕所示；后序CG線索二叉樹如圖6.13〔右〕所示；該二叉樹變換后的的森林如圖6.14所示。IaaKbcbcacJfNULL圖6.12defdefbehi4.圖6.8的樹轉(zhuǎn)變?yōu)橐豢枚鏄淙缦?，圖d：j6.15ajhjhNULLii

圖6.14b對應(yīng)的森林圖8.18中序和后序線索樹圖6.13

cedig圖6.15一棵樹的孩子兄弟表5.畫出結(jié)構(gòu)Huffman樹如圖6.16所示，計(jì)算其帶權(quán)路徑長度為。6.一棵含有N個(gè)結(jié)點(diǎn)的k叉樹,可能抵達(dá)的最大深度h=N-k+1，最小深度各為:logkN+1。623725191813121096745精選圖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．關(guān)于一個(gè)擁有n個(gè)極點(diǎn)的無向圖，假定采用毗鄰矩陣表示，那么該矩陣的大小是____。A.nB.(n-1)2C.n-1D.n29．關(guān)于一個(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,b②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,babecf圖7.1一個(gè)無向圖11．一有向圖的毗鄰表存儲(chǔ)結(jié)構(gòu)如圖7.2所示。132^^345^精選^524^圖7.2一個(gè)有向圖的毗鄰表存儲(chǔ)結(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．采用毗鄰表存儲(chǔ)的圖的深度優(yōu)先遍歷算法近似于二叉樹的____。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷13．采用毗鄰表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法近似于二叉樹的____。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷14．判斷一個(gè)有向圖是否存在回路除了能夠利用拓?fù)渑判蚍椒ㄍ?，還能夠利用____。A.求重點(diǎn)路徑的方法B.求最短路徑的Dijkstra方法C.寬度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法15．重點(diǎn)路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中。A.從源點(diǎn)到匯點(diǎn)的最長路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長的回路D.最短的回路16．下面不正確的說法是。1〕在AOE網(wǎng)中，減小一個(gè)重點(diǎn)活動(dòng)上的權(quán)值后，整個(gè)工期也就相應(yīng)減?。?〕AOE網(wǎng)工程工期為重點(diǎn)活動(dòng)上的權(quán)之和；3〕在重點(diǎn)路徑上的活動(dòng)都是重點(diǎn)活動(dòng)，而重點(diǎn)活動(dòng)也必在重點(diǎn)路徑上。A.〔1〕B.〔2〕C.〔3〕D.〔1〕、〔2〕17．用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印出相應(yīng)的極點(diǎn)，那么輸出的極點(diǎn)序列是。A.逆拓樸有序的B.拓樸有序的C.無序的18．在圖7.3所示的拓樸排列的結(jié)果序列為。A.125634B.516234C.123456D.52163419．一個(gè)有圖7.3有向圖。n個(gè)極點(diǎn)的無向連通圖，它所包含的連通分量個(gè)數(shù)為A.0B.1C.nD.n+120．關(guān)于一個(gè)有向圖，假定一個(gè)極點(diǎn)的入度為k1,、出度為k2，那么對應(yīng)毗鄰表中該極點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為。A.k1B.k2C.k1-k2D.k1+k221．關(guān)于一個(gè)有向圖，假定一個(gè)極點(diǎn)的入度為k1,、出度為k2，那么對應(yīng)逆毗鄰表中該極點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為。A.k1B.k2C.k1-k2D.k1+k27.2填空題〔將正確的答案填在相應(yīng)餓空中〕1．n個(gè)極點(diǎn)的連通圖起碼____條邊。2．在無權(quán)圖G的毗鄰矩陣A中，假定(vi,vj)或＜vi,vj＞屬于圖G的邊會(huì)合，那么對應(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)先搜尋序列為____。v1v2v5v4v2v3v5v3v6精選v4^v5v4v6v3圖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ù)雜度為，兩者不同之處在于，反應(yīng)在數(shù)據(jù)結(jié)構(gòu)上的差別是。10．一個(gè)圖的表示法是唯一的，而表示法是不唯一的。11．有向圖中的結(jié)點(diǎn)前驅(qū)后繼關(guān)系的特點(diǎn)是。12．假定無向圖G的極點(diǎn)度數(shù)最小值大于等于時(shí)，G起碼有一條回路。13．根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種序次的遍歷，獲得的極點(diǎn)序列是的。7.3綜合題1．如圖7.5所示的有向圖，請給出該圖的:〔1〕每個(gè)極點(diǎn)的入/出度；152〕毗鄰距陣；3〕毗鄰表；〔4〕逆毗鄰表；6〔5〕強(qiáng)連通分量。243圖7。5一個(gè)有向圖2．請用克魯斯卡爾和普里姆兩種算法分別為圖7.6、圖7.7結(jié)構(gòu)最小生成樹：〔1〕a161115b15c15d13161412e21f圖7.6〔2〕12161361524167522091012543圖7.7精選3．試列出圖7.8中全部的拓?fù)渑判蛐蛄小?23456圖7.84．請用圖示說明圖7.9從極點(diǎn)a到其余各極點(diǎn)之間的最短路徑。b5d36a232f35ce7.95．AOE網(wǎng)有9個(gè)結(jié)點(diǎn)：V1，V2，V3，V4，V5，V6，V7，V8，V9，其毗鄰矩陣如下：請畫出該AOE圖。計(jì)算達(dá)成整個(gè)方案需要的時(shí)間。求出該AOE網(wǎng)的重點(diǎn)路徑?！?45∝∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝∝97∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝習(xí)題答案7.11.C2.B3.B4.C5.A6.A7.C8.D9.AC10.DB11.CB12.A13.D14.D15.A16.A17.A18.B19.B20.B21.A7.21.n-12.1;03.14.v1,v2,v3,v6,v5,v4；v1,v2,v5,v4,v3,v6求矩陣第i列非零元素之和將矩陣第i行全部置為零7.n8.9對每個(gè)極點(diǎn)查找其毗鄰點(diǎn)的過程；O〔e〕〔e為圖中的邊數(shù)〕；O〔e〕；遍歷圖的次序不同；DFS采用棧存儲(chǔ)接見過的結(jié)點(diǎn)，BFS采用行列存儲(chǔ)接見過的結(jié)點(diǎn)。10．毗鄰矩陣毗鄰表精選11．一個(gè)結(jié)點(diǎn)可能有假定干個(gè)前驅(qū)，也可能有假定干個(gè)后繼12．213．唯一7.31.156242.3(1)．a(chǎn)11b15cd131412ef〔2〕11263．615236445721526349101562345456123435162345126345123644．W=6W=5bd3a23f3W=9ce4W=3W=75．(1)該AOE圖為：21597267114349854264達(dá)成整個(gè)方案需要18天。重點(diǎn)路徑為：〔V1，V2，V5，V7，V9〕和〔V1，V2，V5，V8，V9，〕精選習(xí)題8查找8.1單項(xiàng)選擇題次序查找法適合于存儲(chǔ)結(jié)構(gòu)為____的線性表。A.散列存儲(chǔ)B.次序存儲(chǔ)或鏈接存儲(chǔ)C.壓縮存儲(chǔ)D.索引存儲(chǔ)對線性表進(jìn)行二分查找時(shí)，要求線性表必須____。A.以次序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)以次序方式存儲(chǔ)，且結(jié)點(diǎn)按重點(diǎn)字有序排序以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按重點(diǎn)字有序排序3.采用次序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為____.A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為____。A．O〔n2〕B.O(nlog2n)C.O(n)D.O(log2n)二分查找和二叉排序樹的時(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.8設(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如用二次探測再散列辦理矛盾，重點(diǎn)字為49的結(jié)點(diǎn)的地點(diǎn)是____。A.8B.3C.5D.9有一個(gè)長度為12的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為____。A.35/12B.37/12C.39/12D.43/129．關(guān)于靜態(tài)表的次序查找法，假定在表頭設(shè)置崗哨，那么正確的查找方式為。A.從第0個(gè)元素往后查找該數(shù)據(jù)元素B.從第1個(gè)元素往后查找該數(shù)據(jù)元素C.從第n個(gè)元素往開始前查找該數(shù)據(jù)元素與查找次序無關(guān)10．解決散列法中出現(xiàn)的矛盾問題常采用的方法是。數(shù)字剖析法、除余法、平方取中法數(shù)字剖析法、除余法、線性探測法數(shù)字剖析法、線性探測法、多重散列法線性探測法、多重散列法、鏈地點(diǎn)法11．采用線性探測法解決矛盾問題，所產(chǎn)生的一系列后繼散列地點(diǎn)。必須大于等于原散列地點(diǎn)必須小于等于原散列地點(diǎn)能夠大于或小于但不能等于原散列地點(diǎn)地點(diǎn)大小沒有詳細(xì)限制12．關(guān)于查找表的查找過程中，假定被查找的數(shù)據(jù)元素不存在，那么把該數(shù)據(jù)元素插入到會(huì)合中。這種方式主要適合于。A.靜態(tài)查找表B.動(dòng)向查找表C.靜態(tài)查找表與動(dòng)向查找表D兩種表都不適合13.散列表的平均查找長度。與辦理矛盾方法有關(guān)而與表的長度無關(guān)與辦理矛盾方法無關(guān)而與表的長度有關(guān)與辦理矛盾方法有關(guān)而與表的長度有關(guān)與辦理矛盾方法無關(guān)而與表的長度無關(guān)8.2填空題〔將正確的答案填在相應(yīng)的空中〕次序查找法的平均查找長度為____；折半查找法的平均查找長度為____；哈希表查找法采用鏈接法辦理矛盾時(shí)的平均查找長度為____。2.在各樣查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是____。精選折半查找的存儲(chǔ)結(jié)構(gòu)僅限于____，且是____。4.假定在有序線性表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.關(guān)于長度為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è)無序序列能夠經(jīng)過結(jié)構(gòu)一棵樹而變成一個(gè)有序樹，結(jié)構(gòu)樹的過程即為對無序序列進(jìn)行排序的過程。9．平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是、或。10．法結(jié)構(gòu)的哈希函數(shù)肯定不會(huì)發(fā)生矛盾。11．在散列函數(shù)H(key)=key%p中，p應(yīng)取____。12．在散列存儲(chǔ)中，裝填因子的值越大，那么____；的值越小，那么____。8.3綜合練習(xí)題:畫出對長度為10的有序表進(jìn)行折半查找的判斷樹，并求其等概率時(shí)查找成功的平均查找長度。4.選用哈稀函數(shù)H〔k〕=〔3k〕MOD11。用開放定址法辦理矛盾，di=i〔〔7k〕MOD10+1〕〔I=1，2，3，〕.試在0-10的散列地點(diǎn)空間中對重點(diǎn)字序列〔22,41,53,46,30,13,01,67〕造哈希表，并求等概率情況下查找成功時(shí)的平均查找長度。一組重點(diǎ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+〔為裝填因子〕哈希表查找法次序存儲(chǔ)結(jié)構(gòu)、有序的1、2、4、8、5、3．7〔依題意，結(jié)構(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/12〕5.O〔n〕、O(log2n)6．2、4、3．結(jié)點(diǎn)個(gè)數(shù)n、生成過程．二叉排序樹．0、1、-1．直接定址11．素?cái)?shù)12．存取元素時(shí)發(fā)生矛盾的可能性就越大、存取元素時(shí)發(fā)生矛盾的可能性就越小習(xí)題9排序9.1單項(xiàng)選擇題1.在所有排序方法中，重點(diǎn)字比較的次數(shù)與記錄的初始排列序次無關(guān)的是____。A.希爾排序B.起泡排序C.插入排序D.選擇排序2.設(shè)有1000個(gè)無序的元素，希望用最快的速度精選出其中前10個(gè)最大的元素，最好采用____排序法。A.起泡排序B.迅速排序C.堆排序D.基數(shù)排序3.在待排序的元素序列根本有序的前提下，效率最高的排序方法是____。A.插入排序B.選擇排序C.迅速排序D.合并排序一組記錄的排序碼為〔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，38一組記錄的重點(diǎn)碼為〔46，79，56，38，40，84〕，那么利用迅速排序的方法，以第一個(gè)記錄為基準(zhǔn)獲得的一次區(qū)分結(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，79精選一組記錄的排序碼為〔25，48，16，35，79，82，23，40，36，72〕，其中含有5個(gè)長度為2的有序表，按合并排序的方法對該序列進(jìn)行一趟合并后的結(jié)果為____。16，25，35，48，23，40，79，82，36，7216，25，35，48，7