數(shù)據(jù)結(jié)構(gòu)各章習(xí)題集與答案解析

1、 68/68 數(shù)據(jù)結(jié)構(gòu)習(xí)題及解答第1章 概述【例1-1】分析以下程序段的時間復(fù)雜度。for(i=0;in;i+)for(j=0;jm;j+) Aij=0;解：該程序段的時間復(fù)雜度為O(m*n)?！纠?-2】分析以下程序段的時間復(fù)雜度。i=s=0; while(sn) i+; s+=i; 解：語句為賦值語句，其執(zhí)行次數(shù)為1次，所以其時間復(fù)雜度為O(1)。語句和語句構(gòu)成while循環(huán)語句的循環(huán)體，它們的執(zhí)行次數(shù)由循環(huán)控制條件中s與n的值確定。假定循環(huán)重復(fù)執(zhí)行x次后結(jié)束，則語句和語句各重復(fù)執(zhí)行了x次。其時間復(fù)雜度按線性累加規(guī)則為O(x)。此時s與n滿足關(guān)系式：sn，而s=1+2+3+x。所以有：1+

2、2+3+xn，可以推出：x=x與n之間滿足x=f(），所以循環(huán)體的時間復(fù)雜度為O()，語句與循環(huán)體由線性累加規(guī)則得到該程序段的時間復(fù)雜度為O(）?！纠?-3】分析以下程序段的時間復(fù)雜度。i=1; while(i=n) i=2*i; 解：其中語句的執(zhí)行次數(shù)是1，設(shè)語句的執(zhí)行次數(shù)為f(n)，則有：。得：T（n）=O()【例1-4】有如下遞歸函數(shù)fact(n)，分析其時間復(fù)雜度。fact(int n) if(n=1) return(1); else return(n*fact(n-1); 解：設(shè)fact（n）的運(yùn)行時間函數(shù)是T(n)。該函數(shù)中語句的運(yùn)行時間是O(1)，語句的運(yùn)行時間是T(n-1)+

3、O(1)，其中O(1)為常量運(yùn)行時間。由此可得fact（n）的時間復(fù)雜度為 O(n)。習(xí)題1一、單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（1. A ）。A.數(shù)據(jù)元素的組織形式B.數(shù)據(jù)類型C.數(shù)據(jù)存儲結(jié)構(gòu) D.數(shù)據(jù)定義2. 數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（2. C ）。A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu) C.鏈?zhǔn)酱鎯Y(jié)構(gòu)D.順序存儲結(jié)構(gòu)3. 樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（3. D ）。A.一對一關(guān)系B.多對多關(guān)系 C.多對一關(guān)系D.一對多關(guān)系4. 設(shè)語句x+的時間是單位時間，則以下語句的時間復(fù)雜度為（4. B）。for(i=1; i=n; i+)for(j=i; j=n; j+)x+

4、;A.O(1)B.O()C.O(n)D.O()5. 算法分析的目的是（5. C、），算法分析的兩個主要方面是（A）。（1） A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中的輸入和輸出關(guān)系C.分析算法的效率以求改進(jìn) D.分析算法的易懂性和文檔性（2） A.空間復(fù)雜度和時間復(fù)雜度 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6. 計算機(jī)算法指的是（ 6. C、），它具備輸入，輸出和（B）等五個特性。（1） A.計算方法 B.排序方法C.解決問題的有限運(yùn)算序列 D.調(diào)度方法（2） A.可行性，可移植性和可擴(kuò)充性 B.可行性，確定性和有窮性C.確定性，有窮性和穩(wěn)定性 D.易讀性，穩(wěn)定性和

5、安全性7. 數(shù)據(jù)在計算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲方式，在存儲空間使用的靈活性上，鏈?zhǔn)酱鎯Ρ软樞虼鎯σ?7. B）。A.低 B.高 C.相同D.不好說8. 數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程出現(xiàn)是在（ 8. D）年。A.1946B.1953C.1964 D.19689. 數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點（9. B ）。A.正確B.錯誤C.前半句對，后半句錯D.前半句錯，后半句對10. 計算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（10. B ）。A.數(shù)據(jù) B.數(shù)據(jù)元素C.數(shù)據(jù)項D.數(shù)據(jù)庫二、填空題1.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是_和_。1. 線性結(jié)構(gòu)，非線性結(jié)構(gòu)2.數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本

6、形態(tài)，分別是_、_、_和_。2. 集合，線性，樹，圖3.線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是_的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是_的。3. 一對一，一對多或多對多4.一個算法的效率可分為_效率和_效率。4. 時間，空間5.在樹型結(jié)構(gòu)中，樹根結(jié)點沒有_結(jié)點，其余每個結(jié)點的有且只有_個前趨驅(qū)結(jié)點；葉子結(jié)點沒有_結(jié)點；其余每個結(jié)點的后續(xù)結(jié)點可以_。5. 前趨，一，后繼，多6.在圖型結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以_。6. 有多個7.線性結(jié)構(gòu)中元素之間存在_關(guān)系；樹型結(jié)構(gòu)中元素之間存在_關(guān)系；圖型結(jié)構(gòu)中元素之間存在_關(guān)系。7. 一對一，一對多，多對多8.下面程序段的時間復(fù)雜度是_。8. O()

7、for(i=0;in;i+)for(j=0;jn;j+)Aij=0;9.下面程序段的時間復(fù)雜度是_。9. O()i=s=0;while(sn) i+; s+=i;10.下面程序段的時間復(fù)雜度是_。10. O()s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;11.下面程序段的時間復(fù)雜度是_。11. O(logn)i=1;while(i=n)i=i*3;12.衡量算法正確性的標(biāo)準(zhǔn)通常是_。12. 程序?qū)τ诰脑O(shè)計的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。13.算法時間復(fù)雜度的分析通常有兩種方法，即_和_的方法，通常我們對算法求時間復(fù)雜度時，采用后一種方法。

8、13. 事后統(tǒng)計，事前估計三、求下列程序段的時間復(fù)雜度。1.x=0;for(i=1;in;i+)for(j=i+1;j=n;j+)x+;1. O() 2.x=0;for(i=1;in;i+)for(j=1;j=n-i;j+) x+;2. O()3.int i,j,k;for(i=0;in;i+)for(j=0;j=n;j+) cij=0;for(k=0;k=0)&Ai!=k)j-;return (i); 4. O(n)5.fact(n) if(nmaxlen-1) printf(overflow);exit (0); i=0; j=0; /i和j分別作為掃描順序表A和B的指針k=0; /k指示

9、順序表C中當(dāng)前位置 while (i=m)&(j=n) if(*A).elemi(*B).elemj) (*C).elemk(*A)elemi; i+; k+; else (*C).elemk(*B)elemj; j+; k+; while(i=m) /表B已結(jié)束，表A沒有結(jié)束，鏈入表A的剩余部分 (*C).elemk(*A).elemi; i+; k+; while(jnext; q-next=head; head=q; 【例2-3】假設(shè)有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針，已知p為指向鏈表中某結(jié)點的指針，設(shè)計在鏈表中刪除p所指結(jié)點的前趨結(jié)點的算法。解：可引入一個指針q，當(dāng)

10、q-next=p時，說明此時q所指的結(jié)點為p所指結(jié)點的前趨結(jié)點，從而可得算法如下：void delete (LinkList *p) /在鏈表中刪除p所指結(jié)點的前趨結(jié)點LinkList *q,*t; q=p; while(q-next-next!=p) /q-next不是p的前趨結(jié)點 q=q-next; t=q-next; /t指向要刪除結(jié)點 q-next=p; /刪除t結(jié)點 free(t);【例2-4】試設(shè)計實現(xiàn)刪除單鏈表中值相同的多余結(jié)點的算法。解：該例可以這樣考慮，先取開始結(jié)點的值，將它與其后的所有結(jié)點值一一比較，發(fā)現(xiàn)相同的就刪除掉，然后再取第二結(jié)點的值，重復(fù)上述過程直到最后一個結(jié)點。設(shè)

11、單鏈表（其類型為LinkList）的頭指針head指向頭結(jié)點，則可按下列步驟執(zhí)行：首先，用一個指針p指向單鏈表中第一個表結(jié)點，然后用另一個指針q查找鏈表中其余結(jié)點元素，由于是單鏈表，故結(jié)束條件為p= =NULL，同時讓指針s指向q所指結(jié)點的前趨結(jié)點，當(dāng)查找到結(jié)點具有q-data= =p-data時刪除q所指的結(jié)點，然后再修改q，直到q為空；然后使p指針后移（即p=p-next），重復(fù)進(jìn)行，直到p為空時為止。算法描述如下：del(LinkList *head) /刪除單鏈表中值相同的多余結(jié)點 LinkList *p, *s, *q; p=head-next;while(p!=NULL & p-n

12、ext!=NULL) s=p; /s指向要刪除結(jié)點的前趨q=p-next; while (q!=NULL) if (q-data= =p-data) /查找值相同的結(jié)點并刪除 s-next=q-next; free(q); q=s-next; else s=q; q=q-next; p=p-next;習(xí)題2一、單項選擇題1.線性表是_。1A A一個有限序列，可以為空B一個有限序列，不可以為空C一個無限序列，可以為空D一個無限序列，不可以為空2.在一個長度為n的順序表中刪除第i個元素(0=inext=s; s-prior=p; p-next-prior=s; s-next=p-next;B s-

13、prior=p; s-next=p-next; p-next=s; p-next-prior=s;C p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; 6.設(shè)單鏈表中指針p指向結(jié)點m，若要刪除m之后的結(jié)點（若存在），則需修改指針的操作為_。6A Ap-next=p-next-next;Bp=p-next;Cp=p-next-next; Dp-next=p; 7.在一個長度為n的順序表中向第i個元素(0 inext=p-next; p-n

14、ext=sBq-next=s; s-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q9. 以下關(guān)于線性表的說法不正確的是_。9C A線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。C線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。D存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。10.線性表的順序存儲結(jié)構(gòu)是一種_的存儲結(jié)構(gòu)。 10A A隨機(jī)存取B順序存取C索引存取D散列存取11. 在順序表中，只要知道_，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。11D A基地址B結(jié)點大小 C向量大小 D基地址

15、和結(jié)點大小12.在等概率情況下，順序表的插入操作要移動_結(jié)點。 12B A全部 B一半 C三分之一 D四分之一13.在_運(yùn)算中，使用順序表比鏈表好。 13C A插入 B刪除 C根據(jù)序號查找 D根據(jù)元素值查找14.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持該表有序的時間復(fù)雜度是_。 14B AO(1) BO(n) CO(n2) DO(log2n)15. 設(shè)有一個棧，元素的進(jìn)棧次序為A, B, C, D, E,下列是不可能的出棧序列_。15C AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 16.在一個具有n個單元的順

16、序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為_。16C Atop不變 Btop=0 Ctop- Dtop+17.向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應(yīng)執(zhí)行_。17B Ahs-next=s; Bs-next=hs; hs=s;Cs-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next; 18.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為_。18D Arearn= = front B（front+l）n= = rearCrearn -1=

17、 = front D(rear+l)n= = front 19.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為_。19CArearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front20. 在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為_。20AAfront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next二、填空題1. 線性表是一種典型的_結(jié)構(gòu)。1線性2.在一個長度

18、為n的順序表的第i個元素之前插入一個元素，需要后移_個元素。2n-i+1 3.順序表中邏輯上相鄰的元素的物理位置_。3相鄰4.要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需_一個位置，移動過程是從_向_依次移動每一個元素。4前移，前，后5.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_決定的；在線性表的存儲中，元素之間的邏輯關(guān)系是通過_決定的。5物理存儲位置，鏈域的指針值6. 在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向_結(jié)點，另一個指向_結(jié)點。6前趨，后繼7.當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用_存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時

19、，則采用_存儲結(jié)構(gòu)為宜。7順序，8.順序表中邏輯上相鄰的元素，物理位置_相鄰，單鏈表中邏輯上相鄰的元素，物理位置_相鄰。8一定，不一定9.線性表、棧和隊列都是_結(jié)構(gòu)，可以在線性表的_位置插入和刪除元素；對于棧只能在_位置插入和刪除元素；對于隊列只能在_位置插入元素和在_位置刪除元素。9線性，任何，棧頂，隊尾，隊頭10.根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為_和_；而根據(jù)指針的聯(lián)接方式，鏈表又可分為_和_10單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11.在單鏈表中設(shè)置頭結(jié)點的作用是_。11使空表和非空表統(tǒng)一；算法處理一致12.對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一

20、個新結(jié)點的時間復(fù)雜度為_，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_。12O(1)，O(n) 13.對于一個棧作進(jìn)棧運(yùn)算時，應(yīng)先判別棧是否為_，作退棧運(yùn)算時，應(yīng)先判別棧是否為_，當(dāng)棧中元素為m時，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明棧的可用最大容量為_。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的_分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_時才產(chǎn)生上溢。13棧滿，?？眨琺，棧底，兩個棧的棧頂在?？臻g的某一位置相遇14.設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push, push, pop, push, pop, push, push后，輸出

21、序列是_。142、315.無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完犃衼碚f，進(jìn)行插入或刪除運(yùn)算的時間復(fù)雜度均相同為_。15O(1)三、簡答題1. 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，表頭結(jié)點。1頭指針是指向鏈表中第一個結(jié)點（即表頭結(jié)點）的指針；在表頭結(jié)點之前附設(shè)的結(jié)點稱為頭結(jié)點；表頭結(jié)點為鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點。若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2. 線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？2線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元

22、素的大量移動，因而降低效率：而在存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作較簡單。3. 對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？3應(yīng)選用存儲結(jié)構(gòu)，因為鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運(yùn)算是不需要移動元素的，只需修改指針即可，所以很容易實現(xiàn)表的容量的擴(kuò)充。4. 對于線性表的兩種存儲結(jié)構(gòu)，若線性

23、表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。4應(yīng)選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?5設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，

24、則開始結(jié)點和終端結(jié)點的位置分別是rear-next-next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。6. 假定有四個元素A, B, C, D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。6共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7. 什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。7在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front，隊尾指針為rear，隊列的容量（即存儲的空間大?。閙ax

25、num。當(dāng)有元素要加入隊列（即入隊）時，若rear=maxnum，則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現(xiàn)象，隊列某余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊列解決。一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費(fèi)存儲空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動元素的方法。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當(dāng)刪去一個隊頭元素，則可依次移動隊列

26、中的元素總是使front指針指向隊列中的第一個位置。第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運(yùn)算時仍遵循“先進(jìn)先出”的原則。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L) / L是無頭結(jié)點的單鏈表LinkList *q,*p;if(L&L-next) q=L; L=L-next; p=L;while (p-next) p=p-next; p-next=q; q-next=NULL;return (L);8該算法的功能是：將開始結(jié)點摘下到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個

27、結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。四、算法設(shè)計題1. 設(shè)計在無頭結(jié)點的單鏈表中刪除第i個結(jié)點的算法。1算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)in-1時，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時，刪除第一個結(jié)點：（3）當(dāng)in時，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點時，須用指針記住該結(jié)點的前趨結(jié)點。算法描述如下：delete(LinkList *q,int i) /在無頭結(jié)點的單鏈表中刪除第i個結(jié)點 LinkList *p,*s; int j; if(inext; free(s); else j=0; s=q; while(jnext;j+;if (s= =NULL) printf(Ca

28、ntt delete); else p-next=s-next; free(s); 2. 在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運(yùn)算。2由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法描述如下：int ListLength ( LinkList *L ) /求帶頭結(jié)點的單鏈表的表長 int len=0; ListList *p; p=L; while ( p-next!=NULL ) p=p-next;len+; return (len);3. 設(shè)計將帶表頭的鏈表逆置算法。3設(shè)單循環(huán)鏈表的頭指針為head，類型為LinkList。逆置時需將每一

29、個結(jié)點的指針域作以修改，使其原前趨結(jié)點成為后繼。如要更改q結(jié)點的指針域時，設(shè)s指向其原前趨結(jié)點，p指向其原后繼結(jié)點，則只需進(jìn)行q-next=s;操作即可，算法描述如下：void invert(LinkList *head) /逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist *p, *q, *s; q=head; p=head-next; while (p!=head) /當(dāng)表不為空時，逐個結(jié)點逆置 s=q; q=p; p=p-next; q-next=s; p-next=q; 4. 假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head，每個結(jié)點含三個域：data, next和prior。其中da

30、ta為整型數(shù)域，next和prior均為指針域?，F(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編一個算法，利用prior域（此域初值為NULL）把所有結(jié)點按照其值從小到大的順序起來。4定義類型LinkList如下：typedef struct node int data; struct node *next,*prior;LinkList;此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點，用q搜索已由prior域的有序表找到合適位置將p結(jié)點鏈入。算法描述如下：insert (LinkList *head) LinkList *p,*s,*q; p=head-next; /p指向待插入的結(jié)點，初始時指向

31、第一個結(jié)點 while(p!=NULL) s=head; / s指向q結(jié)點的前趨結(jié)點 q=head-prior; /q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點 while(q!=NULL) & (p-dataq-data) /查找插入結(jié)點p的合適的插入位置 s=q; q=q-prior; s-prior=p; p-prior=q; /結(jié)點p插入到結(jié)點s和結(jié)點q之間 p=p-next;5. 已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。5算法描述如下：delete(LinkList *head

32、, int max, int min) linklist *p, *q; if (head!=NULL) q=head; p=head-next; while(p!=NULL) & (p-datanext;while(p!=NULL) & (p-datanext; q-next=p;6. 已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。設(shè)計一個刪除表中所有值小于max但大于min的元素的算法。6算法描述如下：delete(LinkList *head, int max, int min) LinkList *p,*q; q=head; p=head-next; while (p!=

33、NULL) if(p-datadata=max) q=p; p=p-next; else q-next=p-next;free(p);p=q-next; 7.假定用一個單循環(huán)鏈表來表示隊列（也稱為循環(huán)隊列），該隊列只設(shè)一個隊尾指針，不設(shè)隊首指針，試編寫下列各種運(yùn)算的算法：（1）向循環(huán)鏈隊列插入一個元素值為x的結(jié)點；（2）從循環(huán)鏈隊列中刪除一個結(jié)點。7本題是對一個循環(huán)鏈隊列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點的值和不需要回收結(jié)點，算法描述如下：（1）插入（即入隊）算法：insert(LinkList *rear, elemtype x) /設(shè)循環(huán)鏈隊列的隊尾指針為rear,x為待插入的元素

34、LinkList *p;p=(LinkList *)malloc(sizeof(LinkList);if(rear= =NULL) /如為空隊，建立循環(huán)鏈隊列的第一個結(jié)點 rear=p;rear-next=p; /成循環(huán)鏈表else /否則在隊尾插入p結(jié)點 p-next=rear-next;rear-next=p; rear=p;（2）刪除（即出隊）算法：delete(LinkList *rear) /設(shè)循環(huán)鏈隊列的隊尾指針為rearif (rear= =NULL) /空隊 printf(underflown); if(rear-next= =rear) /隊中只有一個結(jié)點rear=NULL;

35、elserear-next=rear-next-next; /rear-next指向的結(jié)點為循環(huán)鏈隊列的隊頭結(jié)點8. 設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。8只要從終端結(jié)點開始往前找到第一個比x大(或相等)的結(jié)點數(shù)據(jù)，在這個位置插入就可以了。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ) int i;if ( (*L).len= maxlen) printf(“overflow);return(0);for ( i=(*L).len ; i0 & (*L).elem i-1 x ; i-) (*L).

36、elem i =(*L).elem i-1 ; / 比較并移動元素 (*L).elem i =x; (*L).len+;return(1);第3章 串【例3-1】已知字符串：a=“an apple”，b=“other hero”，c=“her”，求：（1）concat(substr(a,1,2),b)。（2）replace(a,substr(a,5,1),c)。（3）index(a,c)和index(b,c)。解：（1）返回值為“another hero”，其中substr(a,1,2)的返回值為“an”。（2）返回值為“an aherherle”，其中sub(a,5,1)的返回值為“p”。（

37、3）返回值分別為0和3。3串的順序存儲結(jié)構(gòu)（順序串）串的順序存儲方式類似于線性表的順序存儲方式，其存儲結(jié)構(gòu)用C語言描述為：typedef struct strnode char datamaxlen;int len;SeqString; /定義順序串類型【例3-2】設(shè)定串采用順序存儲結(jié)構(gòu)，寫出對串s1和串s2比較大小的算法。串值大小按字典排序（升序）方式，返回值等于-1，0和1分別表示s1s2。解：算法思想：（1）比較s1和s2共同長度X圍內(nèi)的對應(yīng)字符：若s1的字符s2的字符，返回；若s1的字符后者時，返回1；前者后者時，返回-1；算法描述如下：#define MAXLEN 256struct

38、 strnodechar dataMAXLEN;int len;SeqString; /定義順序串類型int strcmp(SeqString s1, SeqString s2)/比較串s1和串s2的大小 int len; if (s1.lens2.len) len=s1.len; /求出串s1和串s2的共同長度else len=s2.len;for(i=0;ilen;i+) /在共同長度內(nèi)逐個字符比較 if(s1.chis2.chi) return (-1); /s1s2.chi) return (1); /s1s2if(s1.chi= =s2.chi) return (0); /s1=s2

39、else if(s1.chis2.chi) return (-1); /s1s2習(xí)題3一、單項選擇題1.空串與空格字符組成的串的區(qū)別在于（1B ）。A.沒有區(qū)別 B.兩串的長度不相等C.兩串的長度相等D.兩串包含的字符不相同2. 一個子串在包含它的主串中的位置是指（ 2D）。A.子串的最后那個字符在主串中的位置B.子串的最后那個字符在主串中首次出現(xiàn)的位置C.子串的第一個字符在主串中的位置D.子串的第一個字符在主串中首次出現(xiàn)的位置3. 下面的說法中，只有（3C）是正確的。A.字符串的長度是指串中包含的字母的個數(shù)B.字符串的長度是指串中包含的不同字符的個數(shù)C.若T包含在S中，則T一定是S的一個子串

40、D.一個字符串不能說是其自身的一個子串4. 兩個字符串相等的條件是（4D ）。A.兩串的長度相等 B.兩串包含的字符相同C.兩串的長度相等，并且兩串包含的字符相同D.兩串的長度相等，并且對應(yīng)位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作，則對于S=“BeijingNanjing”，SUBSTR（S，4，5）=（5B）。A.“ijing”B. “jing”C. “ingNa”D. “ingN”6. 若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“BeijingNanjing”，T=“jing”，INDEX（S，T）=（6C

41、）。A.2 B.3 C.4 D.57. 若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對于S=“BeijingNanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（7D）。A. “NanjingShanghai” B. “NanjingNanjing”C. “ShanghaiNanjing” D. “ShanghaiNanjing”8. 在長度為n的字符串S的第i個位置插入另外一個字符串，i的合法值應(yīng)該是（8C）。A.i0 B. in C.1in D.1in+19. 字符串采用結(jié)點大小為1的鏈表作為其存

42、儲結(jié)構(gòu)，是指（9D ）。A.鏈表的長度為1B.鏈表中只存放1個字符C.鏈表的每個鏈結(jié)點的數(shù)據(jù)域中不僅只存放了一個字符D.鏈表的每個鏈結(jié)點的數(shù)據(jù)域中只存放了一個字符二、填空題1. 計算機(jī)軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是_，第二種是_。1. 固定長度，設(shè)置長度指針2. 兩個字符串相等的充要條件是_和_。2. 兩個串的長度相等，對應(yīng)位置的字符相等3. 設(shè)字符串S1= “ABCDEF”，S2= “PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值為_。3. “BCDEDE”4. 串是指_。4. 含n個字符的有限序列（n0）5.

43、 空串是指_，空格串是指_。5. 不含任何字符的串，僅含空格字符的字符串三、算法設(shè)計題1. 設(shè)有一個長度為s的字符串，其字符順序存放在一個一維數(shù)組的第1至第s個單元中（每個單元存放一個字符）?，F(xiàn)要求從此串的第m個字符以后刪除長度為t的子串，ms，t(s-m)，并將刪除后的結(jié)果復(fù)制在該數(shù)組的第s單元以后的單元中，試設(shè)計此刪除算法。1算法描述為：int delete(r,s,t,m) /從串的第m個字符以后刪除長度為t的子串char r ;int s,t,m; int i,j; for(i=1;i=m;i+)rs+i=ri; for(j=m+t-i;jdata!=pt-data) pt=pt-ne

44、xt; if(pt= =NULL) ps=NULL; else ps=ps-next;s=ps; return s; /find第4章 數(shù)組和廣義表【例4-1】二維數(shù)組A的每一個元素是由6個字符組成的串，其行下標(biāo)i=0，1，8，列下標(biāo)j=1，2，10。若A以行為主序存儲元素，A85的物理地址與當(dāng)A按列為主序存儲時的元素（）的物理地址相同。設(shè)每個字符占一個字節(jié)。AA85 BA310 CA58 DA09解：二維數(shù)A是一個9行10列的矩陣，即A910。按行存儲時，A85是第85個元素存儲的元素。而按列存儲時，第85個存儲的元素是A310。即正確答案為B。【例4-2】若對n階對稱矩陣A以行序為主序方式

45、將其下三角形的元素（包括主對角線上所有元素）依次存放于一維數(shù)組Bn（n+1）/2中，則在B中確定的位置k的關(guān)系為（）。A B C D解：如果a按行存儲，那么它的前面有i-1行，其有元素個數(shù)為：1+2+3+（i-1）=i（i-1）/2。同時它又是所在行的第j列，因此它排列的順序還得加上j，一維數(shù)組Bn(n+1)/2中的位置k與其下標(biāo)的關(guān)系是：。因此答案為A?！纠?-3】已知n階下三角矩陣A，按照壓縮存儲的思想，可以將其主對角線以下所有元素（包括主對角線上元素）依次存放于一維數(shù)組B中。請寫出從第一列開始以列序為主序分配方式時在B中確定元素a的存放位置的公式。解：如果a按列存儲，那么它的前面有j-1

46、列，共有元素：n+(n-1)+(n-2)+ +n-(j-2)=(j-1)*n-而它又是所在列的第i行，因此在它前的元素個數(shù)還得加上i。因此它在一維數(shù)組B中的存儲順序為：(j-1)*n-+i【例4-4】已知廣義表L=(x,y,z),a,(u,t,w)，從L表中取出的原子項ASCII碼最大的運(yùn)算是（）。Ahead(tail(tail(L)Btail(head(head(tail(L)Chead(tail(tail(head(L)Dhead(tail(tail(tail(L)解：選項A的結(jié)果是字符串“u”；選項B的結(jié)果是空表，無字符；選項C的結(jié)果是字符“z”；選項D的結(jié)果是字符“t”。從所有選項的結(jié)

47、果可以看出，ASCII碼最大的是字符“z”。因此正確答案是C。習(xí)題4一、單項選擇題1.設(shè)二維數(shù)組A0m-10n-1按行優(yōu)先順序存儲在內(nèi)存中，第一個元素的地址為p，每個元素占k個字節(jié)，則元素aij的地址為（1. A）。A.p +i*n+j-1*kB.p+(i-1)*n+j-1*kC.p+(j-1)*n+i-1*kD.p+j*n+i-1*k2.已知二維數(shù)組A1010中，元素a20的地址為560，每個元素占4個字節(jié)，則元素a10的地址為（2. A）。A.520B.522C.524D.5183.若數(shù)組A0m0n按列優(yōu)先順序存儲，則aij地址為（3. A ）。A.LOC(a00)+j*m+i B. LO

48、C(a00)+j*n+iC.LOC(a00)+(j-1)*n+i-1 D. LOC(a00)+(j-1)*m+i-14. 若下三角矩陣Ann，按列順序壓縮存儲在數(shù)組Sa0(n+1)n/2中，則非零元素aij的地址為（4.B）。（設(shè)每個元素占d個字節(jié)）A. (j-1)*n-+i-1*dB. (j-1)*n-+i*dC(j-1)*n-+i+1*dD(j-1)*n-+i-2*d5.設(shè)有廣義表D=(a,b,D)，其長度為（B），深度為（A）。A.無窮大 B.3C.2 D.56. 廣義表A=（a），則表尾為（6. C）。A.a B.( )C.空表 D.(a)7. 廣義表A=(x,(a,B),(x,(a,

49、B),y)，則運(yùn)算head(head(tail(A)的結(jié)果為（7. A ）。A.x B.(a,B) C.(x,(a,B) D.A8.下列廣義表用圖來表示時，分支結(jié)點最多的是（8. A）。A.L=(x,(a,B),(x,(a,B),y)B.A=(s,(a,B)C.B=(x,(a,B),y)D.D=(a,B),(c,(a,B),D)9. 通常對數(shù)組進(jìn)行的兩種基本操作是（9. C）。A.建立與刪除B.索引和修改 C.查找和修改 D.查找與索引10. 假定在數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（10.

50、 C）。A.80B.100C.240D.27011. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為（11. C ）。A.SA+141B.SA+144C.SA+222D.SA+22512.稀疏矩陣一般的壓縮存儲方法有兩種，即（12. C ）。A.二維數(shù)組和三維數(shù)組 B.三元組和散列C.三元組和十字鏈表 D.散列和十字鏈表13.若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點（13. B ）。A.正確B.不正確14.一個廣義表的表頭總是

51、一個（14. D）。A.廣義表B.元素C.空表D.元素或廣義表15.一個廣義表的表尾總是一個（15.A）。A.廣義表B.元素C.空表 D.元素或廣義表16.數(shù)組就是矩陣，矩陣就是數(shù)組，這種說法（16.B）。A.正確 B.錯誤 C.前句對，后句錯 D.后句對二、填空題1.一維數(shù)組的邏輯結(jié)構(gòu)是_，存儲結(jié)構(gòu)是_；對于二維或多維數(shù)組，分為_和_兩種不同的存儲方式。1. 線性結(jié)構(gòu)，順序結(jié)構(gòu)，以行為主序，以列為主序2.對于一個二維數(shù)組Amn，若按行序為主序存儲，則任一元素Aij相對于A00的地址為_。2. in+j個元素位置3.一個廣義表為(a,(a,b),d,e,(i,j),k)，則該廣義表的長度為_，

52、深度為_。3. 5，34.一個稀疏矩陣為，則對應(yīng)的三元組線性表為_。4.（0，2，2），（1，0，3），（2，2，-1），（2，3，5）5. 一個nn的對稱矩陣，如果以行為主序或以列為主序存入內(nèi)存，則其容量為_。5. n(n+1)/26. 已知廣義表A=(a,b,c),(d,e,f)，則運(yùn)算head(tail(tail(A)=_。6. e7. 設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，a為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a的地址為_。7.418. 已知廣義表Ls=(a,(b,c,d),e)，運(yùn)用head和tail函數(shù)取出Ls中的原子b的運(yùn)算是_。

53、8. head(head(tail(Ls)9. 三維數(shù)組Rc1d1,c2d2,c3d3共含有_個元素。（其中：c1d1,c2d2,c3d3）9.（d-c+1）（d-c+1）（d-c+1）10. 數(shù)組A110，-26，28以行優(yōu)先的順序存儲，設(shè)第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A5，0，7的存儲地址為_。10. 913三、判斷題1. 數(shù)組可看作基本線性表的一種推廣，因此與線性表一樣，可以對它進(jìn)行插入、刪除等操作。（1. ）2. 多維數(shù)組可以看作數(shù)據(jù)元素也是基本線性表的基本線性表。（2.）3. 以行為主序或以列為主序?qū)τ诙嗑S數(shù)組的存儲沒有影響。（3.）4. 對于不

54、同的特殊矩陣應(yīng)該采用不同的存儲方式。（4. ）5. 采用壓縮存儲之后，下三角矩陣的存儲空間可以節(jié)約一半。（5.）6. 在一般情況下，采用壓縮存儲之后，對稱矩陣是所有特殊矩陣中存儲空間節(jié)約最多的。（6.）7. 矩陣不僅是表示多維數(shù)組，而且是表示圖的重要工具。（7.）8. 距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類型。（8.）9. 矩陣中的行列數(shù)往往是不相等的。（9.）10. 廣義表的表頭可以是廣義表，也可以是單個元素。（10.）11. 廣義表的表尾一定是一個廣義表。（11.）12. 廣義表的元素可以是子表，也可以是單元素。（12.）13. 廣義表不能遞歸定義。（13. ）14. 廣義表實際上是基本線性表

55、的推廣。（14.）15. 廣義表的組成元素可以是不同形式的元素。（15. ）第5章 樹【例5-1】寫出如圖5-1所示的樹的葉子結(jié)點、非終端結(jié)點、每個結(jié)點的度及樹深度。ABCDEFGHIJ圖5-1解：（1）葉子結(jié)點有：B、D、F、G、H、I、J。（2）非終端結(jié)點有：A、C、E。（3）每個結(jié)點的度分別是：A的度為4，C的度為2，E的度為3，其余結(jié)點的度為0。（4）樹的深度為3?！纠?-2】一棵度為2的樹與一棵二叉樹有什么區(qū)別？解：度為2的樹有兩個分支，但分支沒有左右之分；一棵二叉樹也有兩個分支，但有左右之分，左右子樹的次序不能交換?！纠?-3】樹與二叉樹有什么區(qū)別？解：區(qū)別有兩點：（1）二叉樹的一

56、個結(jié)點至多有兩個子樹，樹則不然；（2）二叉樹的一個結(jié)點的子樹有左右之分，而樹的子樹沒有次序。【例5-4】分別畫出具有3個結(jié)點的樹和三個結(jié)點的二叉樹的所有不同形態(tài)。解：如圖5-2(a)所示，具有3個結(jié)點的樹有兩種不同形態(tài)。圖5-2(a)如圖5-2(b)所示，具有3個結(jié)點的二叉樹有以下五種不同形態(tài)。圖5-2(b)【例5-5】在一棵度為m樹中，度為1的結(jié)點數(shù)為n1，度為2的結(jié)點數(shù)為n2，度為m的結(jié)點數(shù)為nm，則該數(shù)中含有多少個葉子結(jié)點？有多少個非終端結(jié)點？解：設(shè)度為0的結(jié)點（即終端結(jié)點）數(shù)目為n0，樹中的分支數(shù)為B，樹中總的結(jié)點數(shù)為N，則有：（1）從結(jié)點的度考慮：N= n0+n1+ n2+nm（2）

57、從分支數(shù)目考慮：一棵樹中只有一個根結(jié)點，其他的均為孩子結(jié)點，而孩子結(jié)點可以由分支數(shù)得到。所以有：N=B+1=0n0+1n1+2n2+mnm+1由以上兩式，可得n0+n1+ n2+nm=0n0+1n1+2n2+mnm+1從而可導(dǎo)出葉子結(jié)點的數(shù)目為：n0=0n1+1n2+（m-1）nm+1=1+從而可以得到非終端結(jié)點的數(shù)目為N- n0= n1+ n2+nm=【例5-6】一棵含有n個結(jié)點的k叉樹，可能達(dá)到的最大深度和最小深度各為多少？解：（1）當(dāng)k叉樹中只有一層的分支數(shù)為k，其它層的分支數(shù)均為1時，此時的樹具有最大的高度，為：n-k+1。（2）當(dāng)該k叉樹為完全k叉樹時，其深度最小。參照二叉樹的性質(zhì)4

58、可知，其深度為：+1?！纠?-7】證明任何一棵滿二叉樹T中的分支數(shù)B滿足B=2(n0-1)（其中n0為葉子結(jié)點數(shù)）。證明：T為滿二叉樹不存在度為1的結(jié)點設(shè)該二叉樹中總的結(jié)點數(shù)為n，度為2的結(jié)點總數(shù)為n2，分支數(shù)為B則有nn0+ n2又除了根結(jié)點外，其余n-1個結(jié)點都有一個分支進(jìn)入，即有n個結(jié)點的二叉樹共有n-1條邊n=B+1由、兩式，可得B+1n0+ n2又由二叉樹的性質(zhì)3可知n2n0-1由、兩式可知B= n0+ n0-1-1=2(n0-1)求證成立。abcdefg圖5-3【例5-8】如圖5-3所示的二叉樹，試分別寫出它的順序表示和表示（二叉鏈表）。解：（1）順序表示。123456789101

59、1abcdefg（2）該二叉樹的二叉鏈表表示如圖5-4所示。abcdefg圖5-4【例5-9】試找出滿足下列條件的所有二叉樹：（1）先序序列和中序序列相同；（2）中序序列和后序序列相同；（3）先序序列和后序序列相同。解：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點的二叉樹。bacdef圖5-5【例5-10】如圖5-5所示的二叉樹，要求：（1）寫出按先序、中序、后序遍歷得到的結(jié)點序列。（2）畫出該二叉樹的后序線索二叉樹。解：

60、（1）先序遍歷序列：ABDEFC中序遍歷序列：DEFBAC后序遍歷序列：FEDBCA（2）其后序線索二叉樹如圖5-6所示。NULLcabdef圖5-6A圖5-7BCDEFGHIKLMJ【例5-11】將圖5-7所示的樹轉(zhuǎn)換為二叉樹。解：第一步，加線。第二步，抹線。第三步，旋轉(zhuǎn)。過程如圖5-8所示。A圖5-8(a) 第一步加線BCDEFGHIKLMJA圖5-8(b) 第二步抹線BCDEFGHIKLMJAB圖5-8(c) 第三步旋轉(zhuǎn)CFDKGELHMIJABCDEFHIJ圖5-9【例5-12】將如圖5-9所示的二叉樹轉(zhuǎn)換為樹。解：第一步，加線。第二步，抹線。第三步，調(diào)整。過程如圖5-10所示。ABD