數(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ù)字，而單鏈表只有向后的箭頭，而沒有向前的箭頭，所以不能直接插入，可以采用如下方法：在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頁/共14頁1.一個(gè)長度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素（1=i=n+1）之前插入一個(gè)新元素時(shí)，需要從后向前依次后移（ ）個(gè)元素An-i Bn-i+1 Cn-i-1 DI2.一個(gè)長度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素（1=inext Bx = HS-data CHS=HS-next; x = HS-data Dx = HS-data; HS=HS-next第2頁/共14頁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解釋：插入元素與隊(duì)頭沒有關(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ì)尾沒有關(guān)系9、向一個(gè)棧頂指針為Top的鏈棧中插入一個(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頁/共14頁12容量是10的循環(huán)隊(duì)列的頭指針的位置Sq-front= 2，則隊(duì)列的頭元素的位置是（A）A2 B3 C1 D013、循環(huán)隊(duì)列的隊(duì)滿條件是（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頁/共14頁7.赫夫曼樹是訪問葉結(jié)點(diǎn)的外部路徑長（ ）A. 最短 B.

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

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

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

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

10、選項(xiàng)排除。如圖所示，若高度 為k=3，則結(jié)點(diǎn)數(shù)為5，從而把A排除， 答案為：C5.樹最適合用來表示（D） A元素之間無聯(lián)系的數(shù)據(jù) B有序數(shù)據(jù)元素 C無序數(shù)據(jù)元素 D元素之間具有分支層次關(guān)系的數(shù)據(jù)對(duì)一棵滿二叉樹，有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頁/共14頁16.觀察如圖所示的樹，回答下列問題。 哪些是H的祖先？ /沿H往上走到根節(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)都是他的祖先，答案：E,B,A 結(jié)點(diǎn)J的兄弟是那些？ /和她同一個(gè)雙親的都是

11、兄弟，答案： F,G 樹的深度是多少？/就是他的層次 ，答案： 4 樹的度是多少？ /某個(gè)結(jié)點(diǎn)最多有幾個(gè)孩子，那個(gè)數(shù)字就是度，答案： 3 結(jié)點(diǎn)H和結(jié)點(diǎn)J的層次分別是多少？ /答案：4 ,3ABCDEFGJHI第9頁/共14頁20.畫出如圖所示二叉樹對(duì)應(yīng)的森林解答：如圖所示ABEDHGCFIJ第10頁/共14頁low mid high 5131921375664758088921234567891011找找21high low mid low high mid 第11頁/共14頁第第 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)定簡單選擇排序簡單選擇排序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頁/共14頁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,