數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題整理PPT課件

1、20、在一個(gè)單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作： s-next=_； p-next=s； t= p-data； p-data=_； s-data=_； SP解答：解答：因?yàn)檫@是一個(gè)單鏈表，需要向p點(diǎn)之前插入一個(gè)數(shù)字，而單鏈表只有向后的箭頭，而沒(méi)有向前的箭頭，所以不能直接插入，可以采用如下方法：在p所指結(jié)點(diǎn)的后面插入一個(gè)結(jié)點(diǎn)s，然后把p和s所指的結(jié)點(diǎn)上面的數(shù)字調(diào)換位置，即可達(dá)到預(yù)期的效果。所以答案為： s-next=p-next；/將s結(jié)點(diǎn)插入到p結(jié)點(diǎn)的后面 p-next=s； t= p-data；/將p所指結(jié)點(diǎn)的數(shù)字保存在變量 t 上 p-data=s-data；/將

2、s結(jié)點(diǎn)數(shù)字放在p結(jié)點(diǎn)上面 s-data=t； /將變量 t 上面的數(shù)字放在s結(jié)點(diǎn)上第1頁(yè)/共14頁(yè)1.一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線(xiàn)性表中，向第i個(gè)元素（1=i=n+1）之前插入一個(gè)新元素時(shí)，需要從后向前依次后移（ ）個(gè)元素An-i Bn-i+1 Cn-i-1 DI2.一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線(xiàn)性表中，刪除第i個(gè)元素（1=inext Bx = HS-data CHS=HS-next; x = HS-data Dx = HS-data; HS=HS-next第2頁(yè)/共14頁(yè)16、在一鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算是（B）Af-next=s;f=s Br-next =s; r

3、=s Cs-next = r; r =s Ds-next = f; f = s解釋?zhuān)翰迦朐嘏c隊(duì)頭沒(méi)有關(guān)系19、在一鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一結(jié)點(diǎn)的運(yùn)算是（ C）Ar=f-next Br=r-next Cf=f-next Df=r-next 刪除元素與隊(duì)尾沒(méi)有關(guān)系9、向一個(gè)棧頂指針為T(mén)op的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，其操作步驟是（B）ATop-next=s Bs-next= Top-next; Top-next=s Cs-next= Top; Top =s Ds-next= Top; Top = Top-next解答：如圖所示：datanexttop棧頂棧底s所以答案為：

4、 s-next= Top-next; Top-next=s 選B第3頁(yè)/共14頁(yè)12容量是10的循環(huán)隊(duì)列的頭指針的位置Sq-front= 2，則隊(duì)列的頭元素的位置是（A）A2 B3 C1 D013、循環(huán)隊(duì)列的隊(duì)滿(mǎn)條件是（C）A(Sq.rear+1)%maxsize= =(Sq.front+1)%maxsize B(Sq.rear+1)%maxsize= =Sq.front+1 C(Sq.rear+1)%maxsize= =Sq.front DSq.rear = =Sq.front2、如果進(jìn)棧元素序列為A，B，C，D，則所有可能得到的出棧序列為多少？答案：ABCD,ABDC,ACBD,ACDB,

5、ADCB, BACD,BADC,BCAD,BCDA,BDCA, CBAD,CBDA,CDBA, DCBA 一共有十四種。6、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（A）、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（B）A、head= =null B、head-next= =null C、head-next= =head D、head! =null10、判斷一個(gè)棧ST（最多元素為m0）為空的條件是_ST.front=ST.rear_ 11、判斷一個(gè)隊(duì)列QU（最多元素為m0）為空的條件是_QU.front=QU.rear第4頁(yè)/共14頁(yè)7.赫夫曼樹(shù)是訪(fǎng)問(wèn)葉結(jié)點(diǎn)的外部路徑長(zhǎng)（ ）A. 最短 B.

6、最長(zhǎng) C. 可變 D. 不定解答：赫夫曼樹(shù)又稱(chēng)最優(yōu)二叉樹(shù)，他的一個(gè)特點(diǎn)就是帶權(quán)路徑長(zhǎng)度最短。所以答案為：D8.以下說(shuō)法錯(cuò)誤的是（ ）A. 赫夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上的權(quán)值較大的結(jié)點(diǎn)離根較近 B. 已知二叉樹(shù)的前序遍歷和后序遍歷不能唯一確定這棵樹(shù)，因?yàn)椴荒艽_定樹(shù)的根結(jié)點(diǎn) C. 在前序遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)的后繼結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)之后 D. 若一個(gè)二叉樹(shù)的樹(shù)葉是某子樹(shù)的中序遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的后序遍歷序列中的第一個(gè)結(jié)點(diǎn)解答：A，這句話(huà)，是最優(yōu)二叉樹(shù)的特點(diǎn)，記下來(lái)就好。B，已知二叉樹(shù)的前序遍歷和后序遍歷的確不能確定這棵樹(shù)，但是卻不是因?yàn)椴荒艽_定根節(jié)點(diǎn)，

7、相反的，他只能確定根節(jié)點(diǎn)，而左右孩子卻不能確定，所以不能確定這個(gè)樹(shù)。C，前序遍歷是根左右，所以任何結(jié)點(diǎn)的子樹(shù)的后繼結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)之后 。D，中序遍歷是左根右，后序遍歷是左右根，他們第一個(gè)都是左，所以，該選項(xiàng)也是正確的。所以答案選:B第5頁(yè)/共14頁(yè)9.設(shè)森林中有三棵樹(shù)，第一、二、三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別是n1，n2，n3，那么當(dāng)把森林轉(zhuǎn)換成一棵二叉樹(shù)后，其根結(jié)點(diǎn)的右子樹(shù)有（ ）個(gè)結(jié)點(diǎn)A. n1 B. n1+ n2 C. n1+ n2+n3 D. n2+n3解答：森林與二叉樹(shù)的轉(zhuǎn)換對(duì)應(yīng)關(guān)系如下例子；ABCDEFGHIJABCDEFGHIJ森林 樹(shù)只要是兄弟就放在右邊。只要是孩子就放在左邊，圖

8、中，AEG是兄弟，所以都放在右邊，排成一排。其他的也都是如此排列。題中問(wèn)其根節(jié)點(diǎn)的右子樹(shù)有多少結(jié)點(diǎn)，其右子樹(shù)都是根節(jié)點(diǎn)在森林中的兄弟或者兄弟的孩子。所以答案為n2+n3，所以選：D第6頁(yè)/共14頁(yè)12.二叉樹(shù)通常有_存儲(chǔ)結(jié)構(gòu)和_存儲(chǔ)結(jié)構(gòu)兩類(lèi)存儲(chǔ)結(jié)構(gòu)。解答：二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩部分。所以該題的答案是：順序、鏈?zhǔn)?5.有m個(gè)葉子結(jié)點(diǎn)的赫夫曼樹(shù)上的結(jié)點(diǎn)數(shù)是_。 解答：因?yàn)楹辗蚵鼧?shù)中沒(méi)有度為1的結(jié)點(diǎn)，則一顆又n個(gè)葉子結(jié)點(diǎn)的赫夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)，可以存儲(chǔ)在一個(gè)大小為2n-1的一維數(shù)組中。所以該題的答案為：2m-110.設(shè)有13個(gè)值，用它們組成一棵赫夫曼樹(shù)，則該赫夫曼樹(shù)中共有（

9、）個(gè)結(jié)點(diǎn)解答：該類(lèi)型的題，公式：2*n-1，即2*13-1=25，也即有13個(gè)葉子結(jié)點(diǎn)的赫夫曼樹(shù)中共有（ ）個(gè)結(jié)點(diǎn)課本P1556、由樹(shù)轉(zhuǎn)化得到的二叉樹(shù)是非空的二叉樹(shù)，則二叉樹(shù)形狀是 根結(jié)點(diǎn)無(wú)右子樹(shù)的二叉樹(shù) 解答：因?yàn)闃?shù)的根結(jié)點(diǎn)是不存在兄弟的，所以由樹(shù)轉(zhuǎn)化而成的二叉樹(shù)就不存在右子樹(shù) 第7頁(yè)/共14頁(yè)1.設(shè)高度為K的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為（ ）AK+1 B2K C2K-1 D2K+1解答：這個(gè)題不知道該怎么做，但是可以用排除法，因?yàn)檫@個(gè)二叉樹(shù)只有度為0和度為2的結(jié)點(diǎn)，所以這個(gè)二叉樹(shù)是最簡(jiǎn)單的那種，如圖所示，若高度為k=2，結(jié)點(diǎn)數(shù)為3，所 以可以把B，D

10、選項(xiàng)排除。如圖所示，若高度 為k=3，則結(jié)點(diǎn)數(shù)為5，從而把A排除， 答案為：C5.樹(shù)最適合用來(lái)表示（D） A元素之間無(wú)聯(lián)系的數(shù)據(jù) B有序數(shù)據(jù)元素 C無(wú)序數(shù)據(jù)元素 D元素之間具有分支層次關(guān)系的數(shù)據(jù)對(duì)一棵滿(mǎn)二叉樹(shù)，有m個(gè)葉子結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，深度為h，則（ ）An=h+m Bn=2h-1 C2n=m+h Dm=n-h 解答：這個(gè)題帶入數(shù)字，是最快最準(zhǔn)確的方法了。如圖顯然m=2，n=3，h=2.帶入ABCD中顯然答案為：B第8頁(yè)/共14頁(yè)16.觀察如圖所示的樹(shù)，回答下列問(wèn)題。 哪些是H的祖先？ /沿H往上走到根節(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)都是他的祖先，答案：E,B,A 結(jié)點(diǎn)J的兄弟是那些？ /和她同一個(gè)雙親的都是

11、兄弟，答案： F,G 樹(shù)的深度是多少？/就是他的層次 ，答案： 4 樹(shù)的度是多少？ /某個(gè)結(jié)點(diǎn)最多有幾個(gè)孩子，那個(gè)數(shù)字就是度，答案： 3 結(jié)點(diǎn)H和結(jié)點(diǎn)J的層次分別是多少？ /答案：4 ,3ABCDEFGJHI第9頁(yè)/共14頁(yè)20.畫(huà)出如圖所示二叉樹(shù)對(duì)應(yīng)的森林解答：如圖所示ABEDHGCFIJ第10頁(yè)/共14頁(yè)low mid high 5131921375664758088921234567891011找找21high low mid low high mid 第11頁(yè)/共14頁(yè)第第 9 章章 排序方法排序方法時(shí)間復(fù)雜度時(shí)間復(fù)雜度空間復(fù)雜度空間復(fù)雜度穩(wěn)定性穩(wěn)定性直接插入排序直接插入排序O(n)O

12、(1)穩(wěn)定穩(wěn)定折半插入排序折半插入排序O(n)O(1)穩(wěn)定穩(wěn)定冒泡排序冒泡排序O(n)O(1)穩(wěn)定穩(wěn)定快速排序快速排序O(nlogn) O(n)O(logn)不穩(wěn)定不穩(wěn)定簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序O(n)O(1)不穩(wěn)定不穩(wěn)定堆排序堆排序O(nlogn)O(1)不穩(wěn)定不穩(wěn)定歸并排序歸并排序O(nlogn)O(n)穩(wěn)定穩(wěn)定基數(shù)排序基數(shù)排序O(d(n+rd)O(rd)第12頁(yè)/共14頁(yè)5, 9, 3, 4, 6, 2, 8, 7 直接插入：直接插入： （ ）5, 9, 3, 4, 6, 2, 8, 7 （ ）5, 9, 3, 4, 6, 2, 8, 7 （3）3, 5, 9, 4, 6, 2, 8, 7 （4）3, 4, 5, 9, 6, 2, 8, 7 （6）3, 4, 5, 6, 9, 2, 8, 7 （2）2, 3, 4, 5, 6, 9, 8, 7 （8）2, 3, 4, 5, 6, 8, 9, 7 （7）2, 3, 4, 5, 6, 7, 8, 9冒泡：冒泡： 5, 9, 3, 4, 6, 2, 8, 7 5, 3, 4, 6, 2, 8, 7, 9 3, 4, 5, 2, 6, 7, 8, 9 3, 4, 2, 5, 6, 7, 8, 9 3, 2, 4, 5, 6, 7, 8, 9 2, 3, 4, 5, 6, 7, 8, 9 直接選擇：直接選擇： 5, 9,