數(shù)據(jù)結(jié)構(gòu)(習題二).ppt

數(shù) 據(jù) 結(jié) 構(gòu),習 題 二,第四部分 樹與二叉樹,考點一 樹的概念,本考點主要考查： 樹的基本概念,第四部分 樹與二叉樹,考點一 樹的概念,1. 下列有關(guān)樹的概念錯誤的是 ( ) A. 一棵樹中只有一個無前驅(qū)的結(jié)點 B. 一棵樹的度為樹中各個結(jié)點的度數(shù)之和 C. 一棵樹中，每個結(jié)點的度數(shù)之和等于結(jié)點總數(shù)減 1 D. 一棵樹中每個結(jié)點的度數(shù)之和與邊的條數(shù)相等,【解析】本題考查樹的相關(guān)概念。 一棵樹中只有根結(jié)點沒有前驅(qū)結(jié)點， 除根結(jié)點之外，每個結(jié)點都有一個前驅(qū)結(jié)點， 即父結(jié)點，故而 A 答案正確。 通常我們把一個結(jié)點擁有子樹的個數(shù)稱為該結(jié)點的度數(shù)，所以結(jié)點的度數(shù)之和等于除根結(jié)點外所有結(jié)點的個數(shù)，即每個結(jié)點的度數(shù)之和等于結(jié)點總數(shù)減 1，故而 C 答案正確。 結(jié)點的度等于該結(jié)點子樹的個數(shù)，而結(jié)點與子樹之間是以邊連接的，所以一棵樹中每個結(jié)點的度數(shù)之和與邊的條數(shù)相等， D 答案正確。 一棵樹的度等于結(jié)點中度數(shù)最大的結(jié)點的度數(shù)，而不是樹中各結(jié)點的度數(shù)之和。故而，B 答案錯誤。,B,第四部分 樹與二叉樹,考點一 樹的概念,2. 有一棵樹如右圖所示，回答下面的問題：,(1). 這棵樹的根結(jié)點是_. (2). 這棵樹的葉子結(jié)點是_. (3). 結(jié)點 k3 的度是_. (4). 這棵樹的度是_. (5). 這棵樹的深度是_. (6). 結(jié)點 k3 的孩子結(jié)點是_. (7). 結(jié)點 k3 的父結(jié)點是_.,k1,k2, k5, k7, k4,2,3,4,k5, k6,k1,【解析】由圖可知， (1). 這棵樹的根結(jié)點是結(jié)點 k1。 (2). 這棵樹的葉子結(jié)點是 k2、 k5、 k7、 k4 。 (3). k3 結(jié)點有 2 個孩子結(jié)點 k5 與 k6，故而其度為 2。 (4). 樹的度等于數(shù)中度最大的結(jié)點的度數(shù)，本題中度數(shù)最大的結(jié)點為根結(jié)點，度數(shù)為 3。 故而，樹的度為 3。 (5). 很顯然本題的樹的層數(shù)為 4 層，第一層（層數(shù)我們從 1 開始算）有結(jié)點 k1，第二 層有結(jié)點 k2、 k3 和 k4，第三層有結(jié)點 k5 和 k6，第四層有結(jié)點 k7。因而，樹的深度為 4。 (6). k3 結(jié)點的孩子結(jié)點為 k5、 k6。 (7). k3 結(jié)點的父結(jié)點是結(jié)點 k1。,第四部分 樹與二叉樹,考點一 樹的概念,第四部分 樹與二叉樹,考點二 二叉樹,本考點主要考查： 二叉樹 包括： 1、 二叉樹的定義及其主要特征； 2、 二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)； 3、二叉樹的遍歷； 4、 線索二叉樹的基本概念和構(gòu)造。,第四部分 樹與二叉樹,考點二 二叉樹二叉樹的定義及其主要特征,設高度為 h 的二叉樹上只有度為 0 和度為 2 的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為 （ ） A. 2h B. 2h-1 C. 2h+1 D. h+1,B,【解析】 高度為 h，而且只有度數(shù)為 0 或者 2 的結(jié)點，這是什么樣的樹呢？如下圖所示的二叉樹就是一棵這樣的二叉樹。,由圖可以觀察出，除了第 1 層，其他每一層都是兩個結(jié)點，故而總共有結(jié)點 2 （ h-1）+1=2h-1。,第四部分 樹與二叉樹,考點二 二叉樹二叉樹的定義及其主要特征,2. 以下說法錯誤的是 ( ) A. 存在這樣的二叉樹，對它采用任何次序遍歷其結(jié)點訪問序列均相同 B. 二叉樹是樹的特殊情形 C. 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的 D. 在二叉樹只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹,【解析】 盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形，故而 B 答案錯誤。 對于 A 答案，如果二叉樹中只有一個根結(jié)點，則不管采用什么樣的遍歷算法，所得訪問序列都是一樣的。 對于 C 答案，樹轉(zhuǎn)換成二叉樹時，樹的左孩子為樹的一個孩子，第二個孩子成為其左孩子的右孩子，第三個孩子（如果存在的話）成為其左孩子的右孩子的右孩子。故而，根結(jié)點的右子樹總是空的。 二叉樹是有序樹，其左右孩子有次序之分，即使只有一棵子樹也要明確指出該子樹是左子樹還是右子樹。,B,第四部分 樹與二叉樹,考點二 二叉樹二叉樹的順序和鏈式存儲結(jié)構(gòu),用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中 R1n，結(jié)點 Ri若有左孩子，其左孩子的編號為結(jié)點 ( ),A. R2i+1 B. R2i C. Ri/2 D. R2i-1,B,【解析】 將完全二叉樹存儲在數(shù)組中 R1n中，結(jié)點 Ri若有左孩子，其左孩子的編號為結(jié)點 R2i，若有右孩子，則右孩子的編號為結(jié)點 R2i+1。故而，本題選擇 B 答案。 值得注意的是，一般二叉樹的順序存儲，將每個結(jié)點與完全二叉樹上的結(jié)點相對照，然后存儲在數(shù)組的相應位置中，缺少的結(jié)點用“ 0”補齊。,第四部分 樹與二叉樹,考點二 二叉樹二叉樹的遍歷,1. 該二叉樹結(jié)點的前序遍歷的序列為( ) A. E、 G、 F、 A、 C、 D、 B B. E、 A、 G、 C、 F、 B、 D C. E、 A、 C、 B、 D、 G、 F D. E、 G、 A、 C、 D、 F、 B,C,【解析】 前序遍歷首先訪問根結(jié)點，其次遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹，即遍歷左右子樹時仍然采用前序遍歷方法。 對題中的二叉樹進行前序遍歷，可以得到序列 EACBDGF，故而選擇 C答案。,第四部分 樹與二叉樹,考點二 二叉樹二叉樹的遍歷,2. 該二叉樹結(jié)點的中序遍歷的序列為 ( ) A. A、 B、 C、 D、 E、 G、 F B. E、 A、 G、 C、 F、 B、 D C. E、 A、 C、 B、 D、 G、 F D. B、 D、 C、 A、 F、 G、 E,【解析】 中序遍歷首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結(jié)點，最后遍歷右子樹，即遍歷左右子樹時仍然采用中序遍歷方法。 對題中的二叉樹進行中序遍歷，可以得到序列 ABCDEGF，故而選擇 A答案。,A,第四部分 樹與二叉樹,考點二 二叉樹二叉樹的遍歷,3. 該二叉樹的按層遍歷的序列為 （ ） A. E、 G、 F、 A、 C、 D、 B B. E、 A、 C、 B、 D、 G、 F C. E、 A、 G、 C、 F、 B、 D D. E、 G、 A、 C、 D、 F、 B,C,【解析】 層次遍歷，也是常見的二叉樹遍歷算法。層次遍歷二叉樹，即從上到下，從左到右遍歷二叉樹的結(jié)點。 對題中的二叉樹進行層次遍歷，可以得到序列 EAGEFBD，故而選擇 C 答案。,第四部分 樹與二叉樹,考點二 二叉樹線索二叉樹的基本概念和構(gòu)造,1. 引入二叉線索樹的目的是 ( ) A. 加快查找結(jié)點的前驅(qū)或后繼的速度 B. 為了能在二叉樹中方便的進行插入與刪除 C. 為了能方便的找到雙親 D. 使二叉樹的遍歷結(jié)果唯一,【解析】引入二叉線索樹的目的是有效利用空指針域，提高遍歷運算的效率， 加快查找結(jié)點的前驅(qū)或者后繼結(jié)點的速度， 簡化遍歷算法。對于有 n 個結(jié)點的線索二叉樹上含有 n+1 條線索。,A,2. 在中序線索二叉樹中，若某結(jié)點有右孩子，則該結(jié)點的直接后繼是 ( ) A. 左子樹的最右下結(jié)點 B. 右子樹的最右下結(jié)點 C. 左子樹的最左下結(jié)點 D. 右子樹的最左下結(jié)點,第四部分 樹與二叉樹,考點二 二叉樹線索二叉樹的基本概念和構(gòu)造,【解析】 二叉樹的線索化說透了就是按照某種遍歷算法將結(jié)點的線索引向前驅(qū)或者后繼（若不存在左孩子，則左指針引向該遍歷序列的直接前驅(qū)結(jié)點；若不存在右孩子，則右指針引向該遍歷序列的直接后繼結(jié)點）。若中序遍歷時，某結(jié)點有右孩子，那么該結(jié)點中序遍歷的直接后繼應該是其右子樹的最左下的結(jié)點。故而，本題選擇 D 答案。,D,第四部分 樹與二叉樹,考點三 樹和森林,本考點主要考查： 1、 樹的存儲結(jié)構(gòu)； 2、 森林與二叉樹的轉(zhuǎn)換； 3、 樹和森林的遍歷。 本部分內(nèi)容的命題形式比較固定，解題方法也比較固定，同學們可以通過掌握一個題的解題方法，而掌握一類題型的解題方法。,第四部分 樹與二叉樹,考點三 樹和森林,1. 設 F 是由 T1、 T2 和 T3 三棵樹組成的森林，與 F 對應的二叉樹為 B，T1、 T2 和 T3 的結(jié)點數(shù)分別為 N1、 N2 和 N3，則二叉樹 B 的根結(jié)點的左子樹的結(jié)點數(shù)為 ( ) A. N1-1 B. N2-1 C. N2+N3 D. N1+N3,A,【解析】本題道理與第 1 題相同。 F 是由 T1、 T2 和 T3 三棵樹組成的森林，與 F 對應的二叉樹為 B， T1、 T2 和 T3 的結(jié)點數(shù)分別為 N1、 N2 和 N3，則二叉樹 B 的根結(jié)點的左子樹的結(jié)點數(shù) N1-1。,第四部分 樹與二叉樹,考點四 樹和二叉樹的應用,本考點主要考查： 1、 二叉排序樹； 2、 平衡二叉樹； 3、 哈夫曼(Huffman)樹和哈夫曼編碼。 前兩個知識點結(jié)合課本第九章出題，這里主要掌握第三個知識點。,第四部分 樹與二叉樹,考點四 樹和二叉樹的應用哈夫曼樹和哈夫曼編碼,1. 由五個分別帶權(quán)值為 9， 2， 3， 5， 14 的葉子結(jié)點構(gòu)成的一棵哈夫曼樹，該樹的帶權(quán)路徑長度為 ( ) A. 60 B. 66 C. 67 D. 50,C,【解析】哈夫曼樹的構(gòu)造過程如下： (1). 根據(jù)給定的 n 個權(quán)值w1, w2, , wn，構(gòu)造 n 棵二叉樹的集合 F = T1, T2, , Tn，其中每棵二叉樹中均只含一個帶權(quán)值為 wi 的根結(jié)點，其左、右子樹為空樹; (2). 在 F 中選取根結(jié)點的權(quán)值最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和; (3). 從 F 中刪去這兩棵樹，同時將剛生成的新樹加入到 F 中; (4). 重復 (2) 和 (3) 兩步，直至 F 中只含一棵樹為止。,由五個分別帶權(quán)值為 9， 2， 3， 5， 14 的葉子結(jié)點構(gòu)成的一棵哈夫曼樹，該哈夫曼樹如下圖所示。,第四部分 樹與二叉樹,考點四 樹和二叉樹的應用哈夫曼樹和哈夫曼編碼,由上圖可知，該哈夫曼樹的帶權(quán)路徑長度為 WPS=(2+3) 4 + 5 3 + 9 2 + 14 = 67,第四部分 樹與二叉樹,考點四 樹和二叉樹的應用哈夫曼樹和哈夫曼編碼,2. 設某哈夫曼樹中有 199 個結(jié)點，則該哈夫曼樹中有( )個葉子結(jié)點。 A. 99 B. 100 C. 101 D. 102,B,【解析】正如第一題所言， 哈夫曼樹其實是二叉樹的一種。哈夫曼樹的特點是沒有度為 1 的結(jié)點，根據(jù)二叉樹的性質(zhì)可知 n0=n2+1。所以，具有 n0 個葉子結(jié)點的二叉樹具有 n0-1個度為 2 的結(jié)點。 當 n=199 時， n0+n2=199，可知 n0=100， n2=99。故而，本題選擇 B 答案。,第五部分 圖,考點一 圖的基本概念,本部分考查圖的基本概念，包括： 1、頂點、邊、度、完全圖、子圖、路徑、 連通圖等基本概念； 2、圖的頂點集和邊集的表示。 本考點考查的都是圖的基本內(nèi)容,連通分量指的是 （ ） 無向圖中的極小連通子圖 B. 無向圖中的極大連通子圖 C. 有向圖中的極小連通子圖 D. 有向圖中的極大連通子圖,第五部分 圖,考點一 圖的基本概念,B,【解析】本題考查連通分量的基本概念。連通分量是針對無向圖而言的，是無向圖中的極大連通子圖（與極小連通子圖進行區(qū)別）。如下圖左圖所示，無向圖 G 有 3 個連通分量，分別如右圖所示。,第五部分 圖,考點二 圖的存儲及基本操作,本考點考查圖的鄰接矩陣、鄰接表、鄰接多重表和十字鏈表四種存儲結(jié)構(gòu)表示及相應的空間復雜度。,第五部分 圖,考點二 圖的存儲及基本操作,1. 圖的鄰接矩陣表示法適用于表示 （ ） A. 無向圖 B. 有向圖 C. 稠密圖 D. 稀疏圖,【解析】 常見的圖的存儲方式有主要有兩種：鄰接矩陣和鄰接表。 鄰接矩陣屬于順序存儲結(jié)構(gòu)，鄰接表屬于鏈式存儲結(jié)構(gòu)。鄰接矩陣易于實現(xiàn)圖的操作，但對稀疏圖而言尤其浪費空間。 故而，鄰接矩陣一般用于存儲稠密圖（鄰接表一般適用于稀疏圖）。,C,2. 帶權(quán)有向圖 G 用鄰接矩陣 A 存儲，則頂點 i 的入度等于 A 中（ ） A. 第 i 行非無窮的元素之和 B. 第 i 列非無窮且非 0 的元素個數(shù) C. 第 i 行非無窮且非 0 的元素個數(shù) D. 第 i 行與第 i 列非無窮且非 0 的元素之和,第五部分 圖,考點二 圖的存儲及基本操作,【解析】 對于鄰接矩陣表示的有向圖，第 i 行表示的是頂點 Vi的出度，而第 i 列表示的是頂點 Vi的入度。帶權(quán)圖不同于不帶權(quán)圖，帶權(quán)圖 Aij=x 表示從Vi到Vj的邊的權(quán)值為 x，而在不帶權(quán)圖中，鄰接矩陣中只有 0、 1 兩個值，值為 1 表示從 Vi到Vj有邊，為 0 則表示沒有邊。故而，第 i 列非無窮且非 0 元素的元素個數(shù)之和，即為頂點 A 的入度。,B,第五部分 圖,考點三 圖的遍歷,本考點主要考查 圖的深度優(yōu)先、 廣度優(yōu)先搜索遍歷和層次遍歷的過程。 請同學們掌握用鄰接表和鄰接矩陣存儲表示下，圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷和層次遍歷的方法和時間復雜度。,第五部分 圖,考點三 圖的遍歷,1. 已知一有向圖的鄰接表存儲結(jié)構(gòu)如下圖所示。,(1). 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點 v1 出發(fā)，所得到的頂點序列是 （ ） A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 (2). 根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點 v1 出發(fā)，所得到的頂點序列是 （ ） A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2,C,B,第五部分 圖,考點三 圖的遍歷,【解析】 為了說明深度優(yōu)先遍歷和廣度優(yōu)先遍歷，我們給出了本題。請同學們多留意遍歷方法。 (1). 從頂點 v1 出發(fā)，發(fā)起深度優(yōu)先遍歷，經(jīng)過 v1v3,再 v3v4， v4 沒有后續(xù)頂點，轉(zhuǎn)回 v3， v3 的后續(xù)頂點中還有 v5 沒有被遍歷過，于是找到 v3v5，再由 v5v2。 因而，得到一個序列 v1v3v4v5v2。選擇C答案。 (2). 從頂點 v1 出發(fā)，發(fā)起廣度優(yōu)先遍歷。因為從 v1 發(fā)出，有一條有向邊 v1v3。因此，有序列 v1v3v2，可有序列 v1v3v2v4v5，選擇 B 答案。,第五部分 圖,考點四 圖的應用,本考點主要考查圖的應用，包括最小生成樹、最短路徑、拓撲排序和關(guān)鍵路徑。本考點特別重要。,第五部分 圖,考點四 圖的應用最小生成樹,1. 已知一個圖 G 如圖所示，在該圖的最小生成樹中各邊上數(shù)值之和為 （ ）,A. 21 B. 26 C. 28 D. 33,B,第五部分 圖,考點四 圖的應用最小生成樹,【解析】 我們可以利用克魯斯卡爾算法構(gòu)造最小生成樹，過程如圖所示。,由圖可知，原圖的最小生成樹各邊上的權(quán)值之和為 2+3+4+7+10=26，故而選擇 B 答案。,第五部分 圖,考點四 圖的應用拓撲排序,1. 已知有向圖 G = (V, E), 其中 V = V1, V2, V3, V4, V5, V6, V7， E=, , , , , , , ,， G 的拓撲序列是 （ ） A. V1, V3, V4, V6, V2, V5, V7 B. V1, V3, V5, V6, V4, V2, V7 C. V1, V3, V4, V5, V2, V6, V7 D. V1, V2, V5, V3, V4, V6, V7,A,第五部分 圖,考點四 圖的應用拓撲排序,【解析】 本題考查有向圖的拓撲排序方法。本題中的圖 G 如圖所示。對圖G 進行拓撲排序，其中的一個排序過程如圖所示。,由圖 5.24 可得到一個拓撲序列為 V1、 V3、 V4、 V6、 V2、 V5、 V7。當然，本題的圖G 的拓撲排序可以得到多個正確的序列，比如 V1、 V2、 V3、 V4、 V5、 V6、 V7 或 V1、 V3、V4、 V2、 V6、 V5、 V7 等等。本題選A。,第五部分 圖,考點四 圖的應用拓撲排序,2. 在有向圖 G 的拓撲序列中，若頂點 Vi 在頂點 Vj 之前，則下列情形不可能出現(xiàn)的是 （ ） A. G 中有弧 B. G 中有一條從 Vi 到 Vj 的路徑 C. G 中沒