《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)習(xí)題及參考答案1》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)習(xí)題及參考答案1（55頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、習(xí)題1一、單項(xiàng)選擇題A1. 數(shù)據(jù)結(jié)構(gòu)是指（ ）。A.數(shù)據(jù)元素的組織形式B.數(shù)據(jù)類(lèi)型C.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) D.數(shù)據(jù)定義C2. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱(chēng)之為（ C ）。A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu) C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)D3. 樹(shù)形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ D ）。A.一對(duì)一關(guān)系B.多對(duì)多關(guān)系 C.多對(duì)一關(guān)系D.一對(duì)多關(guān)系B4. 設(shè)語(yǔ)句x+的時(shí)間是單位時(shí)間，則以下語(yǔ)句的時(shí)間復(fù)雜度為（ B）。for(i=1; i=n; i+)for(j=i; j=n; j+)x+;A.O(1)B.O()C.O(n)D.O()CA5. 算法分析的目的是（1C），算法分析的兩個(gè)主

2、要方面是（2A）。（1） A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中的輸入和輸出關(guān)系C.分析算法的效率以求改進(jìn) D.分析算法的易懂性和文檔性（2） A.空間復(fù)雜度和時(shí)間復(fù)雜度 B.正確性和簡(jiǎn)明性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6. 計(jì)算機(jī)算法指的是（1），它具備輸入，輸出和（2B）等五個(gè)特性。（1） A.計(jì)算方法 B.排序方法C.解決問(wèn)題的有限運(yùn)算序列 D.調(diào)度方法（2） A.可行性，可移植性和可擴(kuò)充性 B.可行性，確定性和有窮性C.確定性，有窮性和穩(wěn)定性 D.易讀性，穩(wěn)定性和安全性7. 數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上，鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要（ B

3、）。A.低 B.高 C.相同D.不好說(shuō)8. 數(shù)據(jù)結(jié)構(gòu)作為一門(mén)獨(dú)立的課程出現(xiàn)是在（ ）年。A.1946B.1953C.1964D.19689. 數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀(guān)點(diǎn)（B ）。A.正確B.錯(cuò)誤C.前半句對(duì)，后半句錯(cuò)D.前半句錯(cuò)，后半句對(duì)10. 計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（B ）。A.數(shù)據(jù) B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.數(shù)據(jù)庫(kù)授課：XXX二、填空題 1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，分別是_和_。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是_、_、_和_。3. 線(xiàn)性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是_的，非線(xiàn)性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是_的。4. 一個(gè)算法的效率可分為_(kāi)效率和

4、_效率。5. 在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有_結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有_個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有_結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以_。6. 在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_。7. 線(xiàn)性結(jié)構(gòu)中元素之間存在_關(guān)系；樹(shù)型結(jié)構(gòu)中元素之間存在_關(guān)系；圖型結(jié)構(gòu)中元素之間存在_關(guān)系。8. 下面程序段的時(shí)間復(fù)雜度是_n*n_。for(i=0;in;i+)for(j=0;jn;j+)Aij=0;9. 下面程序段的時(shí)間復(fù)雜度是_。i=s=0;while(sn) i+; s+=i;10. 下面程序段的時(shí)間復(fù)雜度是_n*n_。s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=

5、Bij;sum=s;11. 下面程序段的時(shí)間復(fù)雜度是_。i=1;while(i=n)i=i*3;12. 衡量算法正確性的標(biāo)準(zhǔn)通常是_。13. 算法時(shí)間復(fù)雜度的分析通常有兩種方法，即_和_的方法，通常我們對(duì)算法求時(shí)間復(fù)雜度時(shí)，采用后一種方法。三、求下列程序段的時(shí)間復(fù)雜度。1. x=0;授課：XXXfor(i=1;in;i+)for(j=i+1;j=n;j+)x+;2. x=0;for(i=1;in;i+)for(j=1;j=n-i;j+) x+;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-;retur

6、n (i);5. fact(n) if(n=1) return (1); else return (n*fact(n-1);習(xí)題1參考答案一、單項(xiàng)選擇題1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B二、填空題1. 線(xiàn)性結(jié)構(gòu)，非線(xiàn)性結(jié)構(gòu)2. 集合，線(xiàn)性，樹(shù)，圖3. 一對(duì)一，一對(duì)多或多對(duì)多4. 時(shí)間，空間5. 前趨，一，后繼，多6. 有多個(gè)7. 一對(duì)一，一對(duì)多，多對(duì)多8. O()授課：XXX9. O()10. O()11. O(logn)12. 程序?qū)τ诰脑O(shè)計(jì)的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。13. 事后統(tǒng)計(jì)，事前估計(jì)三、算法設(shè)

7、計(jì)題1. O() 2. O() 3. O(n) 4. O(n) 5. O(n)習(xí)題2一、單項(xiàng)選擇題 1. 線(xiàn)性表是_。A一個(gè)有限序列，可以為空B一個(gè)有限序列，不可以為空C一個(gè)無(wú)限序列，可以為空D一個(gè)無(wú)限序列，不可以為空2. 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(0=inext=s; s-prior=p; p-next-prior=s; s-next=p-next;B s-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=

8、p; s-next=p-next; p-next-prior=s; p-next=s; 6. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為_(kāi)。Ap-next=p-next-next;Bp=p-next;Cp=p-next-next; Dp-next=p; 7. 在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(0 inext=p-next; p-next=sBq-next=s; s-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q9. 以下關(guān)于線(xiàn)性表的說(shuō)法不正確的是_。 A線(xiàn)性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類(lèi)

9、型。B線(xiàn)性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C線(xiàn)性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D存在這樣的線(xiàn)性表：表中各結(jié)點(diǎn)都沒(méi)有直接前趨和直接后繼。10. 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種_的存儲(chǔ)結(jié)構(gòu)。 A隨機(jī)存取B順序存取C索引存取D散列存取11. 在順序表中，只要知道_，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A基地址B結(jié)點(diǎn)大小 C向量大小 D基地址和結(jié)點(diǎn)大小12. 在等概率情況下，順序表的插入操作要移動(dòng)_結(jié)點(diǎn)。 A全部 B一半 C三分之一 D四分之一13. 在_運(yùn)算中，使用順序表比鏈表好。 A插入 B刪除 C根據(jù)序號(hào)查找 D根據(jù)元素值查找14. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新

10、結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是_。 AO(1) BO(n) CO(n2) DO(log2n)15. 設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳, B, C, D, E,下列是不可能的出棧序列_。AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 16. 在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為_(kāi)。Atop不變 Btop=0 Ctop- Dtop+17. 向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行_。Ahs-next=s; Bs-next=hs; hs=s

11、;Cs-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next; 18. 在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿(mǎn)的條件為授課：XXX_。Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front 19. 在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為_(kāi)。Arearn= = front Bfront+l= rearCrear= = front D(rea

12、r+l)n= front20. 在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為_(kāi)。Afront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next二、填空題 1. 線(xiàn)性表是一種典型的_結(jié)構(gòu)。2. 在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移_個(gè)元素。3. 順序表中邏輯上相鄰的元素的物理位置_。4. 要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需_一個(gè)位置，移動(dòng)過(guò)程是從_向_依次移動(dòng)每一個(gè)元素。5. 在線(xiàn)性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)_決定的；在線(xiàn)性表

13、的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)_決定的。6. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_結(jié)點(diǎn)，另一個(gè)指向_結(jié)點(diǎn)。7. 當(dāng)對(duì)一個(gè)線(xiàn)性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用_存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用_存儲(chǔ)結(jié)構(gòu)為宜。8. 順序表中邏輯上相鄰的元素，物理位置_相鄰，單鏈表中邏輯上相鄰的元素，物理位置_相鄰。9. 線(xiàn)性表、棧和隊(duì)列都是_結(jié)構(gòu)，可以在線(xiàn)性表的_位置插入和刪除元素；對(duì)于棧只能在_位置插入和刪除元素；對(duì)于隊(duì)列只能在_位置插入元素和在_位置刪除元素。10. 根據(jù)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_(kāi)和_；而根據(jù)指

14、針的聯(lián)接方式，鏈表又可分為_(kāi)和_。11. 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_。12. 對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)。 13. 對(duì)于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_(kāi)，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_(kāi)，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明棧的可用最大容量為_(kāi)。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的_分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_時(shí)才產(chǎn)生上溢。14. 設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過(guò)push, push, po

15、p, push, pop, push, push后，輸出序列是_。15. 無(wú)論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來(lái)說(shuō)，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為授課：XXX_。三、簡(jiǎn)答題 1. 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。2. 線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？3. 對(duì)于線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)，如果有n個(gè)線(xiàn)性表同時(shí)并存，而且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線(xiàn)性表的總數(shù)也會(huì)自動(dòng)改變，在此情況下，應(yīng)選用哪一種存儲(chǔ)結(jié)構(gòu)？為什么？4. 對(duì)于線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)，若線(xiàn)性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線(xiàn)性表中的元素，應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)？試說(shuō)明理由

16、。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?6. 假定有四個(gè)元素A, B, C, D依次進(jìn)棧，進(jìn)棧過(guò)程中允許出棧，試寫(xiě)出所有可能的出棧序列。7. 什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡(jiǎn)述之。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L) / L是無(wú)頭結(jié)點(diǎn)的單鏈表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);四、算法設(shè)計(jì)題1. 設(shè)計(jì)在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)的算法。2.

17、 在單鏈表上實(shí)現(xiàn)線(xiàn)性表的求表長(zhǎng)ListLength(L)運(yùn)算。3. 設(shè)計(jì)將帶表頭的鏈表逆置算法。4. 假設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的鏈表，表頭指針為head，每個(gè)結(jié)點(diǎn)含三個(gè)域：data, next和prior。其中data為整型數(shù)域，next和prior均為指針域。現(xiàn)在所有結(jié)點(diǎn)已經(jīng)由next域連接起來(lái)，試編一個(gè)算法，利用prior域（此域初值為NULL）把所有結(jié)點(diǎn)按照其值從小到大的順序鏈接起來(lái)。5. 已知線(xiàn)性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。試編寫(xiě)一個(gè)刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。6. 已知線(xiàn)性表的元素是無(wú)序的，且以帶頭結(jié)點(diǎn)的單鏈表作為

18、存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)一個(gè)刪除表中所有值小于max但大于min的元素的算法。7. 假定用一個(gè)單循環(huán)鏈表來(lái)表示隊(duì)列（也稱(chēng)為循環(huán)隊(duì)列），該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針，不設(shè)隊(duì)首指針，試編寫(xiě)下列各種運(yùn)算的算法：（1）向循環(huán)鏈隊(duì)列插入一個(gè)元素值為x的結(jié)點(diǎn)；授課：XXX（2）從循環(huán)鏈隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。8. 設(shè)順序表L是一個(gè)遞減有序表，試寫(xiě)一算法，將x插入其后仍保持L的有序性。習(xí)題2參考答案一、單項(xiàng)選擇題1A 2A 3D 4C 5D 6A 7B 8B 9C 10A 11D 12B 13C 14B 15C 16C 17B 18D 19C20A二、填空題1線(xiàn)性 2n-i+1 3相鄰 4前移，前，后5物理存儲(chǔ)位置，鏈域的指針

19、值 6前趨，后繼7順序，鏈接 8一定，不一定9線(xiàn)性，任何，棧頂，隊(duì)尾，隊(duì)頭10單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11使空表和非空表統(tǒng)一；算法處理一致12O(1)，O(n)13棧滿(mǎn)，棧空，m，棧底，兩個(gè)棧的棧頂在棧空間的某一位置相遇142、315O(1)三、簡(jiǎn)答題1頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱(chēng)為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線(xiàn)性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線(xiàn)性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2線(xiàn)性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、

20、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。3應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。4應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線(xiàn)性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線(xiàn)性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線(xiàn)性表中的任一個(gè)數(shù)據(jù)

21、元素都可隨機(jī)存取，因此，線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。授課：XXX5設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear-next-next 和 rear, 查找時(shí)間都是O(1)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。6共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，C

22、DBA, DCBA7在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲(chǔ)的空間大?。閙axnum。當(dāng)有元素要加入隊(duì)列（即入隊(duì)）時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。 一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動(dòng)元素的

23、方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。 第二種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。 第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。8該算法的功能是：將開(kāi)始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開(kāi)始結(jié)點(diǎn)，返回新鏈表的頭指針。四、算法設(shè)計(jì)題 1算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)in-1時(shí)，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時(shí)，刪除第一個(gè)結(jié)點(diǎn)：（3）當(dāng)

24、in時(shí)，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：delete(LinkList *q,int i) /在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn) LinkList *p,*s; int j; if(inext;授課：XXX free(s); else j=0; s=q; while(jnext;j+;if (s= =NULL) printf(Cantt delete); else p-next=s-next; free(s); 2由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來(lái)數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。算法描述如下：int ListLength ( Li

25、nkList *L ) /求帶頭結(jié)點(diǎn)的單鏈表的表長(zhǎng) int len=0; ListList *p; p=L; while ( p-next!=NULL ) p=p-next;len+; return (len);3設(shè)單循環(huán)鏈表的頭指針為head，類(lèi)型為L(zhǎng)inkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行q-next=s;操作即可，算法描述如下：void invert(LinkList *head) /逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist *p, *q, *s; q=head;

26、 p=head-next;授課：XXX while (p!=head) /當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置 s=q; q=p; p=p-next; q-next=s; p-next=q; 4定義類(lèi)型LinkList如下：typedef struct node int data; struct node *next,*prior;LinkList;此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點(diǎn)鏈入。算法描述如下：insert (LinkList *head) LinkList *p,*s,*q; p=head-next; /p指向待插入的結(jié)點(diǎn)，

27、初始時(shí)指向第一個(gè)結(jié)點(diǎn) while(p!=NULL) s=head; / s指向q結(jié)點(diǎn)的前趨結(jié)點(diǎn) q=head-prior; /q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點(diǎn) while(q!=NULL) & (p-dataq-data) /查找插入結(jié)點(diǎn)p的合適的插入位置 s=q; q=q-prior; s-prior=p; p-prior=q; /結(jié)點(diǎn)p插入到結(jié)點(diǎn)s和結(jié)點(diǎn)q之間 p=p-next;5算法描述如下：delete(LinkList *head, int max, int min) linklist *p, *q; if (head!=NULL) q=head; p=head-next

28、; while(p!=NULL) & (p-datanext;while(p!=NULL) & (p-datanext; q-next=p;6算法描述如下：delete(LinkList *head, int max, int min) LinkList *p,*q; q=head; p=head-next; while (p!=NULL) if(p-datadata=max) q=p; p=p-next; else q-next=p-next;free(p);p=q-next; 7本題是對(duì)一個(gè)循環(huán)鏈隊(duì)列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)，算法描述如下：（1）插入（即

29、入隊(duì)）算法：insert(LinkList *rear, elemtype x) /設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rear,x為待插入的元素 LinkList *p;p=(LinkList *)malloc(sizeof(LinkList);if(rear= =NULL) /如為空隊(duì)，建立循環(huán)鏈隊(duì)列的第一個(gè)結(jié)點(diǎn) rear=p;rear-next=p; /鏈接成循環(huán)鏈表else /否則在隊(duì)尾插入p結(jié)點(diǎn) p-next=rear-next;rear-next=p; rear=p;授課：XXX（2）刪除（即出隊(duì)）算法：delete(LinkList *rear) /設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rearif (r

30、ear= =NULL) /空隊(duì) printf(underflown); if(rear-next= =rear) /隊(duì)中只有一個(gè)結(jié)點(diǎn)rear=NULL;elserear-next=rear-next-next; /rear-next指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)8只要從終端結(jié)點(diǎn)開(kāi)始往前找到第一個(gè)比x大(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ) int i;if ( (*L).len= maxlen) printf(“overflow);return(0);for ( i=(*L).

31、len ; i0 & (*L).elem i-1 x ; i-) (*L).elem i =(*L).elem i-1 ; / 比較并移動(dòng)元素 (*L).elem i =x; (*L).len+;return(1);習(xí)題3一、單項(xiàng)選擇題1. 空串與空格字符組成的串的區(qū)別在于（ ）。A.沒(méi)有區(qū)別 B.兩串的長(zhǎng)度不相等C.兩串的長(zhǎng)度相等D.兩串包含的字符不相同2. 一個(gè)子串在包含它的主串中的位置是指（ ）。A.子串的最后那個(gè)字符在主串中的位置B.子串的最后那個(gè)字符在主串中首次出現(xiàn)的位置C.子串的第一個(gè)字符在主串中的位置D.子串的第一個(gè)字符在主串中首次出現(xiàn)的位置3. 下面的說(shuō)法中，只有（ ）是正確的

32、。授課：XXXA.字符串的長(zhǎng)度是指串中包含的字母的個(gè)數(shù)B.字符串的長(zhǎng)度是指串中包含的不同字符的個(gè)數(shù)C.若T包含在S中，則T一定是S的一個(gè)子串D.一個(gè)字符串不能說(shuō)是其自身的一個(gè)子串4. 兩個(gè)字符串相等的條件是（ ）。A.兩串的長(zhǎng)度相等 B.兩串包含的字符相同C.兩串的長(zhǎng)度相等，并且兩串包含的字符相同D.兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中從第i個(gè)字符開(kāi)始的連續(xù)k個(gè)字符組成的子串的操作，則對(duì)于S=“BeijingNanjing”，SUBSTR（S，4，5）=（ ）。A. “ijing”B. “jing” C. “ingNa”D. “ingN”6. 若

33、INDEX（S，T）表示求T在S中的位置的操作，則對(duì)于S=“BeijingNanjing”，T=“jing”，INDEX（S，T）=（ ）。A.2 B.3 C.4 D.57. 若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對(duì)于S=“BeijingNanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。A. “NanjingShanghai” B. “NanjingNanjing”C. “ShanghaiNanjing” D. “ShanghaiNanjing”8. 在長(zhǎng)度為n的字符串S的第i個(gè)位置插

34、入另外一個(gè)字符串，i的合法值應(yīng)該是（ ）。A.i0 B. in C.1in D.1in+19. 字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)結(jié)構(gòu)，是指（ ）。A.鏈表的長(zhǎng)度為1B.鏈表中只存放1個(gè)字符C.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中不僅只存放了一個(gè)字符D.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中只存放了一個(gè)字符二、填空題1. 計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長(zhǎng)度的方法：一種是_，第二種是_。2. 兩個(gè)字符串相等的充要條件是_和_。3. 設(shè)字符串S1= “ABCDEF”，S2= “PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值為_(kāi)。4. 串是指_。5

35、. 空串是指_，空格串是指_。三、算法設(shè)計(jì)題1. 設(shè)有一個(gè)長(zhǎng)度為s的字符串，其字符順序存放在一個(gè)一維數(shù)組的第1至第s個(gè)單元中（每個(gè)單元存放一個(gè)字符）?，F(xiàn)要求從此串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串，ms，t(s-m)，并將刪除后的結(jié)果復(fù)制在該數(shù)組的第s單元以后的單元中，試設(shè)計(jì)此刪除算法。授課：XXX2. 設(shè)s和t是表示成單鏈表的兩個(gè)串，試編寫(xiě)一個(gè)找出s中第1個(gè)不在t中出現(xiàn)的字符（假定每個(gè)結(jié)點(diǎn)只存放1個(gè)字符）的算法。習(xí)題3參考答案一、單項(xiàng)選擇題1B2D3C4D5B6C7D8C9D二、填空題1. 固定長(zhǎng)度，設(shè)置長(zhǎng)度指針2. 兩個(gè)串的長(zhǎng)度相等，對(duì)應(yīng)位置的字符相等3. “BCDEDE”4. 含n個(gè)字符

36、的有限序列 （n0）5. 不含任何字符的串，僅含空格字符的字符串三、算法設(shè)計(jì)題1算法描述為：int delete(r,s,t,m) /從串的第m個(gè)字符以后刪除長(zhǎng)度為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-next;授課：XXX if(pt= =NULL) ps=NULL; else ps=ps-next;s=ps; return s; /find習(xí)題4一、單項(xiàng)選擇題1. 設(shè)二維數(shù)組A0m-10n-1按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，第一個(gè)元素的地址為p，每個(gè)元素占

37、k個(gè)字節(jié)，則元素aij的地址為（ ）。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，每個(gè)元素占4個(gè)字節(jié)，則元素a10的地址為（ ）。A.520B.522C.524D.5183. 若數(shù)組A0m0n按列優(yōu)先順序存儲(chǔ)，則aij地址為（ ）。A.LOC(a00)+j*m+i B. LOC(a00)+j*n+iC.LOC(a00)+(j-1)*n+i-1 D. LOC(a00)+(j-1)*m+i-14. 若下三角矩陣Ann，按列順序壓縮存儲(chǔ)在數(shù)組Sa0(n+1)n/2中

38、，則非零元素aij的地址為（ ）。（設(shè)每個(gè)元素占d個(gè)字節(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)，其長(zhǎng)度為（ ），深度為（ ）。A.無(wú)窮大 B.3C.2 D.56. 廣義表A=（a），則表尾為（ ）。A.a B.( )C.空表 D.(a)7. 廣義表A=(x,(a,B),(x,(a,B),y)，則運(yùn)算head(head(tail(A)的結(jié)果為（ ）。A.x B.(a,B) C.(x,(a,B) D.A授課：XXX8. 下列廣義表用圖來(lái)表示時(shí)，分支結(jié)點(diǎn)最多的是（ ）。A.L=(

39、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. 通常對(duì)數(shù)組進(jìn)行的兩種基本操作是（ ）。A.建立與刪除B.索引和修改 C.查找和修改 D.查找與索引10. 假定在數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（ ）。A.80B.100C.240D.27011. 數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A85的起始地址為（ ）

40、。A.SA+141B.SA+144C.SA+222D.SA+22512. 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ ）。A.二維數(shù)組和三維數(shù)組 B.三元組和散列C.三元組和十字鏈表 D.散列和十字鏈表13. 若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀(guān)點(diǎn)（ ）。A.正確B.不正確14. 一個(gè)廣義表的表頭總是一個(gè)（ ）。A.廣義表B.元素C.空表D.元素或廣義表15. 一個(gè)廣義表的表尾總是一個(gè)（ ）。A.廣義表B.元素C.空表 D.元素或廣義表16. 數(shù)組就是矩陣，矩陣就是數(shù)組，這種說(shuō)法（ ）。A.正確 B.錯(cuò)誤 C.前句對(duì)，后句錯(cuò) D.

41、后句對(duì)二、填空題1. 一維數(shù)組的邏輯結(jié)構(gòu)是_，存儲(chǔ)結(jié)構(gòu)是_；對(duì)于二維或多維數(shù)組，分為_(kāi)和_兩種不同的存儲(chǔ)方式。2. 對(duì)于一個(gè)二維數(shù)組Amn，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素Aij相對(duì)于A(yíng)00的地址為_(kāi)。3. 一個(gè)廣義表為(a,(a,b),d,e,(i,j),k)，則該廣義表的長(zhǎng)度為_(kāi)，深度為_(kāi)。4. 一個(gè)稀疏矩陣為 ，則對(duì)應(yīng)的三元組線(xiàn)性表為_(kāi)。5. 一個(gè)nn的對(duì)稱(chēng)矩陣，如果以行為主序或以列為主序存入內(nèi)存，則其容量為_(kāi)。6. 已知廣義表A=(a,b,c),(d,e,f)，則運(yùn)算head(tail(tail(A)=_。授課：XXX7. 設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式以行序?yàn)橹餍虼鎯?chǔ)，a

42、為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a的地址為_(kāi)。8. 已知廣義表Ls=(a,(b,c,d),e)，運(yùn)用head和tail函數(shù)取出Ls中的原子b的運(yùn)算是_。9. 三維數(shù)組Rc1d1,c2d2,c3d3共含有_個(gè)元素。（其中：c1d1,c2d2,c3d3）10. 數(shù)組A110，-26，28以行優(yōu)先的順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是100，每個(gè)元素占3個(gè)存儲(chǔ)長(zhǎng)度的存儲(chǔ)空間，則元素A5，0，7的存儲(chǔ)地址為_(kāi)。三、判斷題1. 數(shù)組可看作基本線(xiàn)性表的一種推廣，因此與線(xiàn)性表一樣，可以對(duì)它進(jìn)行插入、刪除等操作。（ ）2. 多維數(shù)組可以看作數(shù)據(jù)元素也是基本線(xiàn)性表的基本線(xiàn)性表。（ ）3

43、. 以行為主序或以列為主序?qū)τ诙嗑S數(shù)組的存儲(chǔ)沒(méi)有影響。（ ）4. 對(duì)于不同的特殊矩陣應(yīng)該采用不同的存儲(chǔ)方式。（ ）5. 采用壓縮存儲(chǔ)之后，下三角矩陣的存儲(chǔ)空間可以節(jié)約一半。（ ）6. 在一般情況下，采用壓縮存儲(chǔ)之后，對(duì)稱(chēng)矩陣是所有特殊矩陣中存儲(chǔ)空間節(jié)約最多的。（ ）7. 矩陣不僅是表示多維數(shù)組，而且是表示圖的重要工具。（ ）8. 距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類(lèi)型。（ ）9. 矩陣中的行列數(shù)往往是不相等的。（ ）10. 廣義表的表頭可以是廣義表，也可以是單個(gè)元素。（ ）11. 廣義表的表尾一定是一個(gè)廣義表。（ ）12. 廣義表的元素可以是子表，也可以是單元素。（ ）13. 廣義表不能遞歸定義

44、。（ ）14. 廣義表實(shí)際上是基本線(xiàn)性表的推廣。（ ）15. 廣義表的組成元素可以是不同形式的元素。（ ）習(xí)題4參考答案一、單項(xiàng)選擇題1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 15.A 16.B 二、填空題1. 線(xiàn)性結(jié)構(gòu)，順序結(jié)構(gòu)，以行為主序，以列為主序2. in+j個(gè)元素位置3. 5，34.（0，2，2），（1，0，3），（2，2，-1），（2，3，5）5. n(n+1)/26. e7. 418. head(head(tail(Ls)授課：XXX9.（d-c+1）（d-c+1）（d-

45、c+1）10. 913三、判斷題1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.習(xí)題5一、單項(xiàng)選擇題1. 在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（ ）個(gè)。A. 4B. 5C. 6D. 72. 假設(shè)在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（ ）個(gè)。A. 15B. 16C. 17D. 473. 假定一棵三叉樹(shù)的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（ ）。A. 3 B. 4C. 5D. 64. 在一棵二叉樹(shù)上第4層的結(jié)點(diǎn)數(shù)最多為（ ）。A. 2B. 4 C.

46、 6D. 85. 用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R1.n，結(jié)點(diǎn)Ri若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（ ）。A. R2i+1B. R2iC. Ri/2D. R2i-16. 由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（ ）。A. 24B. 48C. 72D. 537. 線(xiàn)索二叉樹(shù)是一種（ ）結(jié)構(gòu)。A. 邏輯 B. 邏輯和存儲(chǔ)C. 物理 D. 線(xiàn)性8. 線(xiàn)索二叉樹(shù)中，結(jié)點(diǎn)p沒(méi)有左子樹(shù)的充要條件是（ ）。A. p-lc=NULL B. p-ltag=1 C. p-ltag=1 且p-lc=NULL D. 以上都不對(duì)9. 設(shè)n , m 為一棵二

47、叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（ ）。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孫10. 如果F是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的（ ）。A. 中序B. 前序C. 后序D. 層次序11. 欲實(shí)現(xiàn)任意二叉樹(shù)的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹(shù)采用（ ）存儲(chǔ)結(jié)構(gòu)。A. 三叉鏈表B. 廣義表C. 二叉鏈表 D. 順序12. 下面敘述正確的是（ ）。A. 二叉樹(shù)是特殊的樹(shù)B. 二叉樹(shù)等價(jià)于度為2的樹(shù)授課：XXXC. 完全二叉樹(shù)必為滿(mǎn)二叉樹(shù)D. 二叉樹(shù)的左右子樹(shù)有次序之分13. 任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先

48、序、中序和后序遍歷序列中的相對(duì)次序（ ）。A. 不發(fā)生改變 B. 發(fā)生改變C. 不能確定 D. 以上都不對(duì)14. 已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（ ）。A. 1 B. 2C. 3D. 415. 根據(jù)先序序列ABDC和中序序列DBAC確定對(duì)應(yīng)的二叉樹(shù)，該二叉樹(shù)（ ）。A. 是完全二叉樹(shù) B. 不是完全二叉樹(shù)C. 是滿(mǎn)二叉樹(shù)D. 不是滿(mǎn)二叉樹(shù)二、判斷題1. 二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度不能超過(guò)2，所以二叉樹(shù)是一種特殊的樹(shù)。（）2. 二叉樹(shù)的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。（）3. 線(xiàn)索二叉樹(shù)是一種邏輯結(jié)構(gòu)。（）4. 哈夫曼樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。（）5. 由二叉樹(shù)的先序序列和后序序列可以唯一確定一顆二叉樹(shù)。（）6. 樹(shù)的后序遍歷與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同。（）7.