數(shù)據(jù)結(jié)構(gòu)形成性考核冊(cè)答案

1、數(shù)據(jù)結(jié)構(gòu)（本）形成性考核作業(yè)答案作業(yè)1（本部分作業(yè)覆蓋教材第1-2章的內(nèi)容）一、單項(xiàng)選擇題I. C2. D3. B4. C5. D6. C7. B8. C9. A10. BII. C12. D13. C14. A15. B16. C17. C18. B19. B20. D二、填空題1. n-i+12. n-i3. 集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)4. 物理結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)5. 線性結(jié)構(gòu)非線性結(jié)構(gòu)6. 有窮性 確定性 可形性有零個(gè)或多個(gè)輸入 有零個(gè)或多個(gè)輸岀7. 圖狀結(jié)構(gòu)&樹形結(jié)構(gòu)9. 線性結(jié)構(gòu)10. n-1 O（n）11. s->next=p->next;12. head13. q

2、>ncxi=p>ncxt;14. p->next=head;15. 單鏈表16. 順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)17. 存儲(chǔ)結(jié)構(gòu)1&兩個(gè) 直接后繼 直接前驅(qū) 尾結(jié)點(diǎn) 頭結(jié)點(diǎn)19. 頭結(jié)點(diǎn)的指針指向第一個(gè)結(jié)點(diǎn)的指針20. 鏈?zhǔn)芥湵砣?、問答題1. 簡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O(shè)計(jì)與實(shí)現(xiàn)？答：若用結(jié)點(diǎn)表示某個(gè)數(shù)據(jù)元素，則結(jié)點(diǎn)與結(jié)點(diǎn)之間的邏輯關(guān)系就稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)在計(jì)算 機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)?？梢?，數(shù)據(jù)的邏借結(jié)構(gòu)是反映數(shù)據(jù)之間的固有關(guān)系，而數(shù)據(jù)的存儲(chǔ) 結(jié)構(gòu)是數(shù)據(jù)在訃算機(jī)中的存儲(chǔ)表示。盡管因采用的存儲(chǔ)結(jié)構(gòu)不同，邏輯上相鄰的結(jié)點(diǎn)，英物理地址未

3、必相 同，但可通過結(jié)點(diǎn)的內(nèi)部信息，找到其相鄰的結(jié)點(diǎn)，從而保留了邏借結(jié)構(gòu)的特點(diǎn)。采用的存儲(chǔ)結(jié)構(gòu)不同， 對(duì)數(shù)據(jù)的操作在靈活性，算法復(fù)雜度等方面差別較大。2. 解釋順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，并比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。答：順序結(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中 存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：一般情況下，存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)：（1）在做插入和刪除操作時(shí)，需移動(dòng)大量元素：（2）由于難以估計(jì)，必須預(yù)先分配較大的空間， 往往使存儲(chǔ)空間不能得到充分利用：（3）表的容量難以擴(kuò)充。鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，所占空

4、間分為兩部分，一部分存放結(jié)點(diǎn)值，另一部分存 放表示結(jié)點(diǎn)間關(guān)系的指針。優(yōu)點(diǎn)：插入和刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率低。3. 什么情況下用順序表比鏈表好？答：順序表適于做查找這樣的靜態(tài)操作，鏈表適于做插入和刪除這樣的動(dòng)態(tài)操作。如果線性表的變化 長度變化不大，且其主要操作是査找，則采用順序表：如果線性表的長度變化較大，且其主要操作是插入、 刪除操作，則采用鏈表。4. 解釋頭結(jié)點(diǎn)、第一個(gè)結(jié)點(diǎn)（或稱首元結(jié)點(diǎn)）、頭指針這三個(gè)概念的區(qū)別？答：頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)：第一個(gè)結(jié)點(diǎn)（或稱首元結(jié)點(diǎn)）是鏈表中存儲(chǔ)第一個(gè) 數(shù)據(jù)元素的結(jié)點(diǎn)；頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)?/p>

5、頭結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。5. 解釋帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別。答：帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別主要體現(xiàn)在其結(jié)構(gòu)上和算法操作上。在結(jié)構(gòu)上，帶頭結(jié)點(diǎn)的單鏈表，不管鏈表是否為空，均含有一個(gè)頭結(jié)點(diǎn)，不帶頭結(jié)點(diǎn)的單鏈表不含頭 結(jié)點(diǎn)。在操作上，帶頭結(jié)點(diǎn)的單鏈表的初始化為申請(qǐng)一個(gè)頭結(jié)點(diǎn)。無論插入或刪除的位置是地第一個(gè)結(jié)點(diǎn)還 是其他結(jié)點(diǎn)，算法步驟都相同。不帶頭結(jié)點(diǎn)的單鏈表，英算法步驟要分別考慮插入或刪除的位程是第一個(gè) 結(jié)點(diǎn)還是其他結(jié)點(diǎn)。因?yàn)閮煞N情況的算法步驟不同。四、程序填空題1.(1 ) p-xiata=i(2) p->next=NULL(3) q->next=

6、p(4) q=p2.(1 ) head=p(2) q=p(3) p->next=NULL(4) p->next=q->next<5) q->next=p3.(1 ) p=q->next(2) q->next=p->next五. 完成：實(shí)驗(yàn)1一 一線性表根據(jù)實(shí)驗(yàn)要求(見教材P2OI-2O2)認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。作業(yè)2答案(本部分作業(yè)覆蓋教材第3-5章的內(nèi)容)一、單項(xiàng)選擇題I. C 2. B 3. A 4. C 5. B 6. A 7. B 8. C 9. A 10. CII. B12. C13. B14. B15. A 16.C 17.

7、 B18. A 19. C 20. D21. B22. D23. C24. B25. D26. A 27. C 28.D 29. D 30. C 31.A 32. D二、填空題1. 后進(jìn)先岀2. 下一個(gè)3. 增1增14. 假上溢5.棧是否滿 s->top=MAXSIZE-l 棧頂指針 棧頂對(duì)應(yīng)的數(shù)組元素棧是否空 s->top=-l棧頂元素修改棧頂指針5. bceda6. 終止條件遞歸部分7. LU->front=LU->rear8. 運(yùn)算符 操作數(shù) ab+c/fde/-9. s->next=h:10. h=h->next;11. r->next=s;1

8、2. f=f->next;13. 字符14. 順序存儲(chǔ)方式鏈?zhǔn)酱鎯?chǔ)方式15. 0空格字符的個(gè)數(shù)16. 特殊稀疏1& () () 219. ( (d,e,f)20. 串長度相等且對(duì)應(yīng)位置的字符相等21. i(i-l)/2+j22. 行下標(biāo)、列下標(biāo)、非零元素值三、問答題1. 簡述棧和一般線性表的區(qū)別。答：棧是一種先進(jìn)后出的線性表，棧的插入和刪除操作都只能在棧頂進(jìn)行，而一般的線性表可以任線 性表的任何位置進(jìn)行插入和刪除操作。2. 簡述隊(duì)列和一般線性表的區(qū)別。隊(duì)列是一種先進(jìn)先出的線性表，隊(duì)列的插入只能在隊(duì)尾進(jìn)行，隊(duì)列的刪除只能在隊(duì)頭進(jìn)行，而一般的 線性表可以在線性表的任何位垃進(jìn)行插入和刪

9、除操作。3. 鏈棧中為何不設(shè)頭結(jié)點(diǎn)？答：因?yàn)殒湕Ｖ辉阪滎^插入和刪除結(jié)點(diǎn)，不可能在鏈表中間插入和刪除結(jié)點(diǎn)，算法實(shí)現(xiàn)很簡單，所以 一般不設(shè)垃頭結(jié)點(diǎn)。4. 利用一個(gè)棧，則:（1）如果輸入序列由A, B, C組成，試給出全部可能的輸出序列和不可能的輸岀序列。（2）如果輸入序列由A, B, C, D組成，試給出全部可能的輸出序列和不可能的輸岀序列。答：（1）棧的操作特點(diǎn)是后進(jìn)先岀，因此輸岀序列有：A入，A出，BN, B出，C入C出，輸岀序列為A BC。A入，A岀，BN, C入，C出，B出，輸出序列為A CB。A入，BN, B出，A岀，C入，C出，輸出序列為BACoA入，BN, B出，C入，C岀，A岀，輸

10、出序列為BCAoA入，BN, C入，C岀，B岀，A出，輸岀序列為CBAo由A, B, C組成的數(shù)據(jù)項(xiàng)，除上述五個(gè)不同的組合外，還有一個(gè)C, A, B組合。但不可能先把C岀 棧，再把A岀棧，（A不在棧頂位苣），最后耙B出棧，所以序列CAB不可能由輸入序列A, B, C通過 棧得到。（2）按照上述方法，可能的輸出序列有：ABCD, ABDC, ACBD, ACDB, ADCB, BACD, BADC, BCAD, BCDA, BDCA, CBAD, CBDA, CDBA, DCBAo不可能的輸岀序列有：DABC, ADBC, DACB, DBAC, BDAC, DBCA, DCAB, CDAB,

11、CADB, CABD5. 用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234,為了得到1342出棧順序，相應(yīng)的 S和X操作串是什么？答：應(yīng)是SXSSXSXX。各操作結(jié)果如下：S1入棧X1出棧輸出序列：1S2入棧S3入棧X3岀棧輸出序列：13S4入棧X4岀棧輸出序列：134X2岀棧輸出序列:13426. 有5個(gè)元素，苴入棧次序?yàn)椋篈、B、C、D、E,在各種可能的出棧次序中，以元素C、D最先的 次序有哪幾個(gè)？答：從題中可知，要使C第一個(gè)且D第二個(gè)岀棧，應(yīng)是A入棧，B入棧，C入棧，C岀棧，D入棧。 之后可以有以下幾種情況：（1）B出棧，A岀棧，E入棧，E出棧，輸岀序列為：CDBAE.（2）B

12、出棧，E入棧，E出棧，A出棧，輸岀序列為CDBEA。<3） E入棧，E岀棧，B出棧，A出棧，輸出序列為CDEBA所以可能的次序有：CDBAE, CDBEA, CDEBA7. 寫出以下運(yùn)算式的后綴算術(shù)運(yùn)算式（1）3x2+x-l/x+5（A+B）*C-D/（E+F）+G答；對(duì)應(yīng)的后綴算術(shù)運(yùn)算式（1）3x2*x+lx/-5+ AB-C*DEF+/-G+8. 簡述廣義表和線性表的區(qū)別和聯(lián)系。答：廣義表是線性表的的推廣，它也是n（n>0）個(gè)元素如an的有限序列，其中缶或者是原子或 者是一個(gè)廣義表。所以，廣義表是一種遞歸數(shù)據(jù)結(jié)構(gòu)，而線性表沒有這種特性，線性表可以看成廣義表的 特殊情況，當(dāng)去都是

13、原子時(shí)，廣義表退化成線性表。四、程序填空題1（1）q->front->next=p->next;（2）free（p）;（3）q->rear=q->front五、綜合題1答：出隊(duì)序列是e2, e4, e3, e6, e5, el的過程：el入棧（棧底到棧頂元素是el）e2入棧（棧底到棧頂元素是el,e2）e2出棧（棧底到棧頂元素是el）e3入棧（棧底到棧頂元素是el,e3）e4入棧（棧底到棧頂元素是el,e3,e4）e4岀棧（棧底到棧頂元素是el,e3）e3岀棧（棧底到棧頂元素是el）e5入棧（棧底到棧頂元素是el,e5）亡6入棧（棧底到棧頂元素是el,e5,e6）

14、00） e6出棧（棧底到棧頂元素是el,e5）（ID e5出棧（棧底到棧頂元素是el）el出棧（棧底到棧頂元素是空）棧中最多時(shí)有3個(gè)元素，所以棧S的容量至少是3。2.算法設(shè)計(jì)如下：/*只有一個(gè)指針rear的鏈?zhǔn)疥?duì)的基本操作*/Sinclude <stdio. h>typedef char elemtype;struct node /*定義鏈隊(duì)列結(jié)點(diǎn)*/elemtype data;struct node *next;；typedef struct queue /*肚義鏈隊(duì)列數(shù)據(jù)類型*/struct node *rear; LinkQueue;void initqueue (LinkQ

15、ueue *Q)/*初始化隊(duì)列*/0=(struct queue *)malloc(sizeof(struct queue): Q->rear=NULL;void enqueue (LinkQueue *Q, elemtype x)/*入隊(duì)算法*/struct node *s,*p;s=(struct node *)malloc(sizeof(struct node); s->data=x;辻(Q->rear=NULL)/*原為空隊(duì)時(shí)*/Q->rear=s;s->next=s;else/*原隊(duì)不為空時(shí)*/p=Q->rear->next; /*p 指向第

16、一個(gè)結(jié)點(diǎn)*/Q->rear->next=s; /*將 s 鏈接到隊(duì)尾*/Q->rear=s;/*Q->rear 指向隊(duì)尾*/s->next=p;void delqueue (LinkQueue *Q) 出隊(duì)算法*/struct node *t;辻(Q->rear=NULL)printf ("隊(duì)列為空！ n");return(0);else if (Q->rear->next=Q->rear)tQ-ear;Q->rear=NULL;else /*有多個(gè)結(jié)點(diǎn)時(shí)*/t二Q-Arear-next; Q->rear-&

17、gt;next=t->next;free(t);/*只有一個(gè)結(jié)點(diǎn)時(shí)*/*t指向第一個(gè)結(jié)點(diǎn)*/*引成循環(huán)鏈*/elemtype gethead(LinkQueue *Q)/*取隊(duì)首元素算法*/if (Q->rear=NULL) printf C*隊(duì)列為空！ n");else return(Q->rear->next->data);int emptyqueue(LinkQueue *Q)/*判斷隊(duì)列是否為空算法*/if (Q->rear=NULL) return(1);/*為空，則返回 true*/else return(0); /*不為空,則返回 f

18、lase*/ _ _void dispqueue(LinkQueue *Q)/*顯示隊(duì)列中元素算法*/struct node *p=Q->rear->next;printf (，?隊(duì)列元素:");while (p!:zQ->rear)printf (/z%c "、p->data);p=p->next;printfp->data);六、完成：實(shí)驗(yàn)2一棧、隊(duì)列、遞歸程序設(shè)計(jì) 根據(jù)實(shí)驗(yàn)要求(見教材P2O3)認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。作業(yè)3答案（本部分作業(yè)覆蓋教材第6-7章的內(nèi)容）一.單項(xiàng)選擇題1.B2B3D4. C5B6. A7. A 8

19、. C 9. A 10. D11.A12. C13. C14. B15. B16.C17. B 18. C 19. A 20. B21.D22. B23. B24. B25. C26.A27. A 28. C二.填空題1.子樹樹木或后繼結(jié)點(diǎn)數(shù)2 樹中所有結(jié)點(diǎn)的度的最大值3. 分支結(jié)點(diǎn)4. 葉子結(jié)點(diǎn)5. 子樹的根非終端結(jié)點(diǎn)終端結(jié)點(diǎn)后繼結(jié)點(diǎn)孩子結(jié)點(diǎn)6. 祖先7. 樹中結(jié)點(diǎn)的最大層數(shù)8 Llog2nJ+l9 根結(jié)點(diǎn)左子樹右子樹10. 左子樹根結(jié)點(diǎn)右子樹11. 左子樹右子樹根結(jié)點(diǎn)12. 權(quán)13. 帶權(quán)路徑長度之和14. 最優(yōu)二叉樹最小的二叉樹15. 6916. 2m-117. 多對(duì)多1&所有頂

20、點(diǎn)一次19. 先序20. 按層次21. n222. 鄰接矩陣鄰接表23. 2(n-l)24. nl25. 棧三、綜合題1. 寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。答：二叉樹的左義是遞歸的，所以，一棵二叉樹可看作由根結(jié)點(diǎn)，左子樹和右子樹這三個(gè)基本部分組 成，即依次遍歷整個(gè)二叉樹，又左子樹或者右子樹又可看作一棵二叉樹并繼續(xù)分為根結(jié)點(diǎn)、左子樹和右子 樹三個(gè)部分，這樣劃分一直進(jìn)行到樹葉結(jié)點(diǎn)。(1) 先序?yàn)椤案笥摇保刃蛐蛄袨椋篺dbaccgihl(2) 中序?yàn)椤白蟾摇?，中序序列為：abcdefghij(3) 后序?yàn)椤白笥腋鵖后序序列為：acbedhjigf2已知某二叉樹的先序遍歷結(jié)果是

21、：A, B, D, G, C, E, H, L, I, K, M, F和J,它的中序遍歷 結(jié)果是：G, D, B, A, L, H, E, K, I, M, C, F和J,請(qǐng)畫岀這棵二叉樹，并寫出該該二叉樹后續(xù)遍 歷的結(jié)果。(1) 二叉樹圖形表示如下：(2) 該二叉樹后序遍歷的結(jié)果是：G、D、B、L、H、K. M. L E、J. F、C和A°3答（1）已知深度為k的二叉樹最多有2k-l個(gè)結(jié)點(diǎn)（K21）,29-1<892<210.1,故樹的高度為10（2）對(duì)于完全二叉樹來說，度為1的結(jié)點(diǎn)只能是0或1因?yàn)?n=n0+nl+n2 和 n0=n2+l得：設(shè)nl=0, 892=n0

22、+0+n2=2n2+l得n2不為整數(shù)出錯(cuò)設(shè) nl=h 892=n0+1 +n2=2n2+2得 n2 =445-* n0=n2+1=446葉子結(jié)點(diǎn)數(shù)為446。（3）由得單支結(jié)點(diǎn)數(shù)為1（4）對(duì)于n個(gè)結(jié)點(diǎn)的完全二叉樹，最后一個(gè)樹葉結(jié)點(diǎn)，即序號(hào)為n的葉結(jié)點(diǎn)其雙親結(jié)點(diǎn) 即為最后 一個(gè)非終端結(jié)點(diǎn)，序號(hào)為 892/2=446。4.（1）先序序列和中序序列相同的二叉樹為空樹或任一結(jié)點(diǎn)均無左孩子的非空二叉樹（2）中序和后序序列相同的二叉樹為空樹或任一結(jié)點(diǎn)均無右孩子的非空二叉樹（3）先序和后序序列相同的二叉樹為空樹或僅有一個(gè)結(jié)點(diǎn)5.（1）哈夫曼樹如圖B4所示。圖B4(2) 其帶權(quán)路徑長度WPL值為270。(3)

23、每個(gè)字符的哈夫曼編碼為:A: 100, B: 11, C: 1010, D:000, E:0010, F: 10110, G: 1011 h H:0011.1：016答(1) 深度優(yōu)先遍歷:vl,v2,v3,v&v5,v7,v4,v6廣度優(yōu)先通歷：vl,v2,v4,v6,v3,v5,v7,v8(2) G 的拓?fù)湫蛄袨椋簐l,v2,v4,v6,v5,v5,v3,v5,v7,v8(3) 最短路徑為：vl,2v5,v7,v87. gl的圖示和圖gl的鄰接表如下圖所示。vl圖G 圖G的鄰接矩陣如下圖所示：廠0101010011000111110001100丿圖G的鄰接矩陣vlv2v3v4v52

24、4A1445A2I I IJ2圖G的鄰接表 VI、V2、V3、V4、V5 的度分別為：2, 3, 2, 3, 2四、程序分析題1 return cl+1(2) NodeLevel(BT->right,X)(3) (c2>=l) return c2+l2. (l)for(j=0; j<n; j+)(2) dfstree (GA, j, n);五. 算法設(shè)計(jì)題1. 寫一個(gè)將一棵二叉樹復(fù)制給另一棵二叉樹的算法。define NULL 0typedef struct btnodeelemtype data;struct btnode *lchild, *rchild;bitnode,

25、 *bitree;bitree *CopyTree( bitnode *p )/*復(fù)制一棵二叉樹*/bitnode *t:if ( p!=NULL ) t=(bitnode *)malloc (sizeof (bitnode): t->data=p->data;t->lchild=CopyTree(p->lchild);t->rchild=CopyTree(p->rchild); return(t);elsereturn(NULL);/*CopyTree*/int BTreeLeafCount(struct BTreeNode* BT)if(BT=NULL)

26、 return 0;else if(BT->left=NULL && BT->nght=NULL) return 1;else return BTreeLeafCount(BT">left)+BTreeLeafCount(BT->right);六、完成：實(shí)驗(yàn)3一棧、隊(duì)列、遞歸程序設(shè)計(jì) 實(shí)驗(yàn)4圖的存儲(chǔ)方式和應(yīng)用根據(jù)實(shí)驗(yàn)要求（見教材P2O3）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。作業(yè)4答案（本部分作業(yè)覆蓋教材第8-9章的內(nèi)容）一、單項(xiàng)選擇題1. D2C3B4. C 5 D6 A7C8D9. B10D11C12. C13. A14. C 15. D 16.

27、 B17. B18. D19. D20. A21D22. D23. A24. A 25. C 26. C27. B28. A29. B30. C二、填空題1. 哈希表查找法2. 數(shù)據(jù)項(xiàng)的值記錄3. 主關(guān)鍵字4. 數(shù)學(xué)期望值5. 順序6. 二分查找升序或降序排列7. 順序存儲(chǔ)結(jié)構(gòu)&索引順序査找順序査找9. 均小于根結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值二叉排序樹10. 自變量 函數(shù)值11. 9, 14,16 , 1712. 內(nèi)部排序外部排序13. 交換排序14. 315. 4 816. 堆排序快速排序17. 主關(guān)鍵字18. 關(guān)鍵字相等的記錄19.19. 堆尾堆頂向下三、綜合題1. 已知序列(70, 8

28、3, 100, 65, 10, 32, 7. 9),請(qǐng)寫岀對(duì)此序列采用插入排序法進(jìn)行升序排序時(shí) 各趟的結(jié)果。答：原始序列：(70), 83, 100, 65, 10, 32, 7, 9第 1 趟：(70, 83), 100, 65, 10, 32, 7, 9第2趟:(70,83,100), 65, 10,32,7,9第3趟：(65,70,83,100), 10,32,7,9第4趟：(10,65,70,83, 100),32,7,9第5趟：(10,32,65,70, 83, 100),7,9第6趟：(7,10,32,65, 70, 83,100),9第7趟:(7,9, 10, 32, 65, 7

29、0,83,100)2. 已知序列(10, 18, 4, 3, 6, 12, h 9, 15, 8),請(qǐng)寫出對(duì)此序列采用歸并排序法進(jìn)行升序排序 時(shí)各趟的結(jié)果。答：原始序列：10, 18, 4, 3, 6, 12, 1, 9, 15, 8第 1 趟：10, 183, 46, 121, 98, 15第 2 趟:3, 4, 10, 18, 1, 6, 9, 128, 15第 3 趟：3, 4, 10, 1& 1, 6, 8, 9, 12, 15第 4 趟：L 3, 4, 6, 8, 9, 10, 12, 15, 18J3已知序列(17, 18, 60, 40, 7, 32, 73, 65, 8

30、5)采用冒泡排序法排序的各趟的結(jié)果如下:原始初始：17, 18, 60, 40, 7, 32, 73, 65, 85第1趟：17,18,40,7,32, 60,65,73,85第2趟：17,18,7,32,40, 60,65,73,85第3趟：17,7,18,32,40, 60,65,73,85第4趟：7,17,18,32,40, 60,65,73,85第5趟：7,17,18,32,40, 60,65,73,854. 已知序列(503, 87, 512, 61, 908, 170, 897, 275, 653, 462)請(qǐng)給出釆用快速排序法對(duì)該序 列作升序排列時(shí)的每一趟結(jié)果。原始序列：503,

31、 87, 512, 61, 908, 170, 897, 275, 653, 462第 1 趟：462, 87, 275, 61, 170)503(897, 908, 653, 512第 2 趟：170, 87, 275, 61 462, 503(897, 908, 653, 512第 3 趟：87, 61170275 462> 503(897, 908, 653, 512第 4 趟：61 87170275 462, 503(897, 908, 653, 512第 5 趟:61 , 87, 170, 275 462, 503(897, 908, 653, 512第6趟：61 ,87. 170, 275, 462, 503(897, 908, 653, 512第7趟：61 ,87, 170, 275, 462, 503(512, 653897908第8趟：61 ,87, 170, 275, 462, 503, 512, 653 897(908第9趟：61 ,87, 170, 275, 462, 503, 653, 897(