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

1、第一章緒論一選擇題1數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R），其中K是的有限集合，R是K上的的有限集合。A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu) A 操作B 映象C.存儲D 關(guān)系2.算法分析的目的是，算法分析的兩個主要方面是。 A找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D分析算法的易懂性和文檔性 A空間復(fù)雜性和時間復(fù)雜性8 .正確性和簡明性C.可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性9 在計算機存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為A邏輯結(jié)構(gòu)B順序存儲結(jié)構(gòu)C.鏈表存儲結(jié)構(gòu)D.以上都不對4數(shù)據(jù)結(jié)構(gòu)中，在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：（）。A.動態(tài)結(jié)

2、構(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)5以下屬于順序存儲結(jié)構(gòu)優(yōu)點的是（）。A存儲密度大B插入運算方便C.刪除運算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示6數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容是（）。A數(shù)據(jù)的邏輯結(jié)構(gòu)B數(shù)據(jù)的存儲結(jié)構(gòu)C.建立在相應(yīng)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)上的算法D.包括以上三個方面）。7鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間（A分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針B.只有一部分，存放結(jié)點值C只有一部分，存儲表示結(jié)點間關(guān)系的指針D分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)8計算機算法指的是（1），它具備輸入，輸出和（2）等五個特性。

3、B. 排序方法D. 調(diào)度方法B.可行性，確定性和有窮性D. 易讀性，穩(wěn)定性和安全性1 ）A.計算方法C.解決問題的有限運算序列2 ）A.可行性，可移植性和可擴充性C.確定性，有窮性和穩(wěn)定性9以下關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中正確的是（）。A數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述B數(shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計算機中的存儲方式C數(shù)據(jù)的邏輯結(jié)構(gòu)分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)D數(shù)據(jù)的邏輯結(jié)構(gòu)分為靜態(tài)結(jié)構(gòu)和動態(tài)結(jié)構(gòu)10算法分析的主要任務(wù)是（）。A探討算法的正確性和可讀性B探討數(shù)據(jù)組織方式的合理性C為給定問題尋找一種性能良好的解決方案D研究數(shù)據(jù)之間的邏輯關(guān)系11計算機內(nèi)部數(shù)據(jù)處理的基本單位是（）。A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)

4、據(jù)項D.數(shù)據(jù)庫二、填空題1 .下面程序段的時間復(fù)雜度是。for(I=1;I<n;I+)for(j=1;j<n;j+)x+;for(k=1;k<n;k+)x+;2 下面程序段的時間復(fù)雜度是s=0;for(i=0；i<n；i+)for(j=0;j<n;j+)s+=b皿；sum=s;3 .數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是和。4 .一個算法的效率可分為效率和效率。5 .設(shè)n為正整數(shù)。下列程序段中前置以記號的語句的頻度為。i=1;k=0;while(i<=n-1)k+=10*i;i+；6算法時間復(fù)雜度的分析通常有兩種方法，即和的方法，通常我們對算法求時間復(fù)雜度時

5、，采用后一種方法。第二次作業(yè)1.對以下單鏈表分別執(zhí)行下列各程序段，畫出結(jié)果示意圖。LPRQ=P->next;(2) S=P->next->next;(3) R->data=P->data;(4) R->data=P->next->data;(5) T=P；while(T!=NULL)T->data=T->data*2;T=T->next;2.簡述以下算法的功能。StatusA(LinkListL)/L是無表頭結(jié)點的單鏈表if(L&&L->next)Q=L;L=L->next;P=L;while(P-&

6、gt;next)P=P->next;P->next=Q;Q->next=NULL;returnOK;/A3. 寫一算法在帶頭結(jié)點的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作LOCATE（L,x）。（求x在單鏈表L中的位序）4. 寫一算法在帶頭結(jié)點的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作LENGTH（L）。（求單鏈表L中的元素個數(shù)）5. 選擇題（1）對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（）A.head=NULLB.heacHnext=NULLC.headfnext=headD.head!=NULL2）完成在雙循環(huán)鏈表結(jié)點p之后插入s的操作是（）Ap->next=s;s-

7、>prior=p;p->next->prior:=s;s->next=p->next;Bp->next->prior=s;p->next=s;s->prior=p;s->next:=p->next;Cs->prior=p;s->next:=p->next;p->next=s;p->next->prior=s;Ds->prior=p;s->next:=p->next;p->next->prior=s;p->next=s;（ 3）線性表是具有n個（）的有限序列。

8、A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項（ 4）下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。（5）若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A 順序表B 雙鏈表（ 6 ）線性表是 。A 一個有限序列，可以為空C 一個無限序列，可以為空（ 7 ）鏈表不具有的特點是（C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表B.一個有限序列，不可以為空D.一個無限序列

9、，不可以為空）B 可隨機訪問任一元素A插入、刪除不需要移動元素C.不必事先估計存儲空間D.所需空間與線性長度成正比8） .在運算中，使用順序表比鏈表好。A.插入B.刪除C.根據(jù)序號查找D.根據(jù)元素值查找9） .在一個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點，則須執(zhí)行As->next=p->next;p->next=sBq->next=s;s->next=pCp->next=s->next;s->next=pDp->next=s;s->next=q（10）.在順序表中，只要知道，就可在相同時間內(nèi)求出任一結(jié)點的存儲

10、地址。A.基地址B.結(jié)點大小C.向量大小D.基地址和結(jié)點大?。?11） .以下關(guān)于線性表的說法不正確的是。A.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B.線性表中包含的數(shù)據(jù)元素個數(shù)是任意的。C.線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。D.存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。（ 12） .從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平均比較個元素結(jié)點。An/2BnC（n+1）/2D（n-1）/2第三次作業(yè)一寫出下列程序段的輸出結(jié)果:voidmain()StackS;charx,y;InitStack(S);x=c;y=k;P

11、ush(S,x);Push(S,a);Push(S,y);Pop(S,x);Push(S,t);Push(S,x);Pop(S,x);Push(S,s);While(!StackEmpty(S)Pop(S,y);printf(y);printf(x);二寫出下列程序段的輸出結(jié)果:voidmain()QueueQ;InitQueue(Q);charx=e,y=c;EnQueue(Q,h);EnQueue(Q,r);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,a);While(!QueueEmpty(Q)DeQueue

12、(Q,y);printf(y);printf(x);3、 假設(shè)稱正讀和反讀都相同的字符序列為回文”，例如，“abbaf口“abcba是回文，“abcde"，“abababW不是回文。試寫一個算法判別讀入的一個以旗結(jié)束符的字符序列是否是“回文”。4、 選擇題一、單選題1 .對于棧操作數(shù)據(jù)的原則是（）。A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序2 .在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為（）Atop不變Btop=0Ctop-Dtop+3 .若一個棧的輸入序列為1,2,3，,n,輸出序列的第一個元素是i,則

13、第j個輸出元素是（）。A.i-j-1B.i-jC.j-i+1D.不確定的4 .某堆棧的輸入序列為a,b,c,d,下面的四個序列中，不可能是它的輸出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b6. 用鏈接方式存儲的隊列，在進(jìn)行刪除運算時（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改7 .假設(shè)以數(shù)組Am存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為（）。A（rear-front+m）%mBrear-front+1C（front-rear+m）%mD（rear-front）%m8 .

14、棧和隊列的共同點是（）。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在兩端插入和刪除元素D.沒有共同點9 .設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過棧S,一個元素出棧后即進(jìn)隊列Q,若6個元素出隊的序列是e2,e4,e3,e6,e5,e1則棧S的容量至少應(yīng)該是（）。A6B.4C.3D.210 .若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？（）A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 111 .在作進(jìn)棧運算時，應(yīng)先判別棧是否()，

15、在作出棧運算時應(yīng)先判別棧是否()。當(dāng)棧中元素為n個,作進(jìn)棧運算時發(fā)生上溢,則說明該棧的最大容量為()。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時應(yīng)將兩棧的()分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)()時，才產(chǎn)生上溢。:A.空B.滿C.上溢D.下溢:A.空B.滿C.上溢D.下溢:A.n-1B.nC.n+1D.n/2:A.長度B.深度C.棧頂D.棧底:A.兩個棧的棧頂同時到達(dá)棧空間的中心點.B. 其中一個棧的棧頂?shù)竭_(dá)?？臻g的中心點.C. 兩個棧的棧頂在?？臻g的某一位置相遇.D. 兩個棧均不空,且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底.12. 棧的輸入序列為ABC，輸出序列變

16、為CBA時，經(jīng)過的棧操作為()A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop13. 設(shè)計一個判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu)B.隊列C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧14最大容量為n的循環(huán)隊列，隊尾指針是rear,隊頭是front,則隊空的條件是()。A.(rear+1)MODn=frontB.rear=frontCrear+1=frontD.(rear-l)MODn=

17、front第五次作業(yè)1. 設(shè)二維數(shù)組a0-m-10i-1按行優(yōu)先順序存儲在內(nèi)存中，第一個元素的地址為p,每個元素占k個字節(jié)，則元素aij的地址是2. 一個廣義表為(a,(a,b),d,e,(i,j),k)，則該廣義表的長度為，深度為。3. 求下列廣義表操作的結(jié)果：GetHead(p,h,w)=GetTail(b,k,p,h)=GetHead(a,b),(c,d)=GetTail(a,b),(c,d)=GetHead(GetTail(a,b),(c,d)=GetTail(GetHead(a,b),(c,d)=4 .按教材中圖5.8所示結(jié)點結(jié)構(gòu)，畫出下列廣義表的存儲結(jié)構(gòu)圖(a),b),(),d),

18、(e,f)5 .已知一個6行5列的稀疏矩陣中非零元的值分別為：-90,41,-76,28,-54,65,-8,它們在矩陣中的列號依次為：1,4,5,1,2,4,5。當(dāng)以帶行表的三元組表作存儲結(jié)構(gòu)時，其行表中的值依次為1,1,3,3,4,6(行列號均從1開始)，寫出該稀疏矩陣。第六次作業(yè)1 .試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。2 .(1)假設(shè)一棵二叉樹的中序序列為DCBGEAHFIJK和后序序列為DCEGBFHKJIA,請畫出該二叉樹。(2)已知一個二叉樹的先序序列為ABDEGCF,中序序列為DBGEACF,畫出該二叉樹。3 .對下圖所示二叉樹進(jìn)行先序線索化，為每個空指

19、針建立相應(yīng)的前驅(qū)或后繼線索。4 .給出下圖所示的森林的先序遍歷結(jié)點序列、中序遍歷結(jié)點序列，然后畫出該森林對應(yīng)的二叉樹。AG：KLBCHI；M5 .假設(shè)用于通信白產(chǎn)吵、8個字母組成，六R在電文中出現(xiàn)的崢河0.07,0.19,0.02,0.06,0xD2皿3221,0.10。iJk8個字母設(shè)計哈婭)編碼。(O6 .對下圖所示二叉樹寫出先序遍歷序列、中序遍歷序列、后序遍歷序歹U.八單選題1 .在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（）個。A.4B.5C.6D.72 .假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為15,單分支結(jié)點數(shù)為30個，則葉子

20、結(jié)點數(shù)為（）個。A.15B.16C.17D.473 .假定一棵三叉樹的結(jié)點數(shù)為50,則它的最小高度為（）。A.3B.4C.5D.64 .在一棵二叉樹上第4層的結(jié)點數(shù)最多為（）。A.2B.4C.6D.85 .下面敘述正確的是（）。A.二叉樹是特殊的無序樹B.二叉樹等價于度為2的樹C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次序之分6.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A.24B.48C.72D.537.線索二叉樹是一種（）結(jié)構(gòu)。A.邏輯B.邏輯和存儲C.物理D.線性8.如果F是由有序樹T轉(zhuǎn)換用來的一義樹，那么T中結(jié)點的前序就是A.中序B.前序C

21、.后序D.層次序F中結(jié)點的（）c9.已知一棵完全二叉樹的結(jié)點總數(shù)為9個，則最舟-層的結(jié)點數(shù)為（A.1B.2C.3D.4）。10.用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中若有左孩子，其左孩子的編號為結(jié)點（）。A.R2i+1B.R2iC.Ri/2D.R2i-1R1.n,結(jié)點Ri第七次作業(yè)1.(1)對于一個無向圖(a),假定采用鄰接矩陣表示，試分別寫出從頂點0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。(2)對于一個有向圖(b),假定采用鄰接表表示，并且假定每個頂點單鏈表中的邊結(jié)點是按出邊鄰接點序號從大到小的次序鏈接的，試分別寫出從頂點0出發(fā)按深度優(yōu)先搜索

22、遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。注：每一種序列都是唯一的，因為都是在存儲結(jié)構(gòu)上得到的。(1)(2)2.對下無向帶權(quán)圖:寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。D7=23試對下圖所示的AOE網(wǎng)絡(luò)，解答下列問題。(1) .求每個事件的最早發(fā)生時間vei和最遲發(fā)生時間vli。(2) .求每個活動的最早開始時間e(s)和最遲開始時間l(s)。(3) .指出哪些活動加速可使整個工程提前完成。a4=3a1=3=2四、單選題1 .在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s,則所有頂點的入度數(shù)之和為（）。A.sB.s

23、-1C.s+1D.n2 .在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s,則所有頂點的度數(shù)之和為（）。A.sB.s-1C.s+1D.2s3 .在一個具有n個頂點的無向圖中，若具有e條邊，則所有頂點的度數(shù)之和為（）。A.nB.eC.n+eD.2e4 .在一個具有n個頂點的無向完全圖中，所含的邊數(shù)為（）。A.nB.n（n-1）C.n（n-1）/2D.n（n+1）/25 .在一個具有n個頂點的有向完全圖中，所含的邊數(shù)為（）。A.nB.n（n-1）C.n（n-1）/2D.n（n+1）/26 .在一個無向圖中，若兩頂點之間的路徑長度為k,則該路徑上的頂點數(shù)為（）。A.kB.k+1C.k+2D.

24、2k7 .對于一個具有n個頂點的無向連通圖，它包含的連通分量的個數(shù)為（）。A.0B.1C.nD.n+18 .若要把n個頂點連接為一個連通圖，則至少需要（）條邊。A.nB.n+1C.n-1D.2n9 .對于一個有向圖，若一個頂點的度為k1,出度為k2,則對應(yīng)逆鄰接表中該頂點單鏈表中的邊結(jié)點數(shù)為（）。A.k1B.k2C.k1-k2D.k1+k210 .在一個有向圖的鄰接表中，每個頂點單鏈表中結(jié)點的個數(shù)等于該頂點的（）。A.出邊數(shù)B.入邊數(shù)C.度數(shù)D.度數(shù)減111 .已知一個有向圖的邊集為<a,b>,<a,c>,<a,d>,<b,d>,<b,e&

25、gt;,<d,e>,則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨椋ǎ?。A.a,b,c,d,eB.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e第九次作業(yè)1 .已知一個順序存儲的有序表為（15,26,34,39,45,56,58,63,74,76）,試畫出對應(yīng)的折半查找判定樹，求出其平均查找長度。2 .假定一個待哈希存儲的線性表為（32,75,29,63,48,94,25,46,18,70）,哈希地址空間為HT13,若采用除留余數(shù)法構(gòu)造哈希函數(shù)和線性探測法處理沖突，試求出每一元素在哈希表中的初始哈希地址和最終哈希地址，畫出最后得到的哈希表，求出平均查找長度。兀索初始哈希地址最終

26、哈希地址3275296348942546187001234567891011123 .假定一個線性表為(38,52,25,74,68,16),畫出按線性表中元素的次序生成的一棵二叉排序樹，求出其平均查找長度。4 .假定一個線性表為(38,52,25,74,68,16),畫出按線性表中元素的次序生成的一棵AVL樹,求出其平均查找長度。五、單選題1 .若查找每個元素的概率相等，則在長度為n的順序表上查找任一元素的平均查找長度為()。A.nB.n+1C.(n-1)/2D.(n+1)/22 .若根據(jù)查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個元素第一次計算的哈希地址為d,則下一次的哈

27、希地址為()。A.dB.d+1C.(d+1)/mD.(d+1)%m3 .對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的比較次數(shù)為()。A.3B.4C.5D.64 .對具有n個元素的有序表采用折半查找，則算法的時間復(fù)雜度為()。A.O(n)B.O(n2)C.O(1)D.O(log2n)5 .從具有n個結(jié)點的二叉排序樹中查找一個元素時，在最壞情況下的時間復(fù)雜度為()。A.O(n)B.O(1)C.O(log2n)D.O(n2)6 .在一棵平衡二叉排序樹中，每個結(jié)點的平衡因子的取值范圍是()。A.-1、1B.-22C.12D.0J第十次作業(yè)1.已知一組記錄為(46,74,53,

28、14,26,38,86,65,27,34),給出采用直接插入排序法進(jìn)行排序時每一趟的排序結(jié)果。2 .已知一組記錄為(46,74,53,14,26,38,86,65,27,34),給出采用冒泡排序法進(jìn)行排序時每一趟的排序結(jié)果。3 .已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采用簡單選擇排序法進(jìn)行排序時每一趟的排序結(jié)果。4 .已知一組記錄為(46,74,53,14,26,38,86,65,27,34),給出采用快速排序法進(jìn)行排序時每一趟的排序結(jié)果。5 .已知一組記錄為(46,74,53,14,26,38,86,65,27,34),給出采用2-路歸并排序法進(jìn)行

29、排序時每一趟的排序結(jié)果。、單選題1 .若又n個元素進(jìn)行直接插入排序，在進(jìn)彳T第i趟排序時，假定元素ri+1的插入位置為rj,則需要移動元素的次數(shù)為()。A.j-iB.i-j-1C.i-jD.i-j+12 .在n個元素進(jìn)行簡單選擇排序的過程中，需要進(jìn)行()趟選擇和交換。A.nB.n+1C.n-1D.n/23 .在n個元素進(jìn)行直接插入排序的過程中，共需要進(jìn)行()趟。A. nB. n+1C. n-1D. 2n4 .對n個元素進(jìn)行直接插入排序時間復(fù)雜度為()。A.O(1)B.O(n)C.O(n2)D.O(log2n)5 .在n個元素進(jìn)行冒泡排序的過程中，第一趟排序需要進(jìn)行()對相鄰元素之間的交換。A.

30、 nB. n-1C. n+1D. n/26 .在n個元素進(jìn)行冒泡排序的過程中，最好情況下的時間復(fù)雜度為()。A.0(1)B.O(log2n)C.O(n2)D.O(n)7.在n個元素進(jìn)行冒泡排序的過程中，至少需要()趟完成。A. 1B. n8.下列序列中，構(gòu)成小根堆的是(A. (1, 2, 5, 3, 4, 6, 7, 8, 9, 10)C. (10, 9, 8, 7, 3, 5, 4, 6, 2)C. n-1D. n/2)B. (10, 5, 8, 4, 2, 6, 7, 1, 3)D. (1, 2, 3, 4, 10, 9, 8, 7, 6, 5)9 .假定對元素序列(7,3,5,9,1,1

31、2)進(jìn)行堆排序，并且采用小根堆，則由初始數(shù)據(jù)構(gòu)成的初始堆為()。A.1,3,5,7,9,12B.1,3,5,9,7,12C.1,5,3,7,9,12D.1,5,3,9,12,710 .假定對元素序列(7,3,5,9,1,12,8,15)進(jìn)行快速排序，則進(jìn)行第一次劃分后，得到的左區(qū)間中元素的個數(shù)為()。A.2B.3C.4D.511 .()是穩(wěn)定的排序方法。A.起泡排序B.快速排序C.堆排序D.希爾排序3 .4 .先根序歹U:ABCDEFGHIJKLMNO后根序歹U:BDEFCAHJIGKNOML5.8個字母的哈夫曼編碼依次為:0.07:10100.19:000.02:100000.06:1001

32、0.32:110.03:100010.21:010.1:10116.先序序歹U:ABDCEGF中序序列：DBAEGCF后序序歹U:DBGEFCA單選題：CBCDDDCBBB第七次1,(1)DFS:0128345679BFS:0142738659(2)DFS:047583612BFS:0431756282(1)000000GO90000GO00ao85765400300003oo2oooo2oo6800600-co43oo485535oo5oo55aooo9oo700ooco60000005_GO0054012345673.事件AB:CDEF最早發(fā)生時間vei032668最遲發(fā)生時間vli042678活動ala2a3a4a5a6a7a8最早開始時間ee(i)0033226n6最遲開始時間el(i)10442567關(guān)鍵活動為a2a5a7,加速這些關(guān)鍵活動可使整個工程提前完成。四、單選題ADDCBBBCCAA第九次和第十次1.ASL=2.92.哈希函數(shù)H(key)=key%13初始哈希地址最終哈希地址013275296348942546187010311931275510311941275866哈希表平均查找長度：14/10=1.42994183246704875632523456789101112哈希函數(shù)H(key)=key%11初始哈希地址最終哈希地址013275296348