1、數(shù) 據(jù) 結(jié) 構(gòu),習(xí) 題 二,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)一 樹(shù)的概念,本考點(diǎn)主要考查： 樹(shù)的基本概念,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)一 樹(shù)的概念,1. 下列有關(guān)樹(shù)的概念錯(cuò)誤的是 ( ) A. 一棵樹(shù)中只有一個(gè)無(wú)前驅(qū)的結(jié)點(diǎn) B. 一棵樹(shù)的度為樹(shù)中各個(gè)結(jié)點(diǎn)的度數(shù)之和 C. 一棵樹(shù)中，每個(gè)結(jié)點(diǎn)的度數(shù)之和等于結(jié)點(diǎn)總數(shù)減 1 D. 一棵樹(shù)中每個(gè)結(jié)點(diǎn)的度數(shù)之和與邊的條數(shù)相等,【解析】本題考查樹(shù)的相關(guān)概念。 一棵樹(shù)中只有根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)， 除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有一個(gè)前驅(qū)結(jié)點(diǎn)， 即父結(jié)點(diǎn)，故而 A 答案正確。 通常我們把一個(gè)結(jié)點(diǎn)擁有子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度數(shù)，所以結(jié)點(diǎn)的度數(shù)之和等于除根結(jié)點(diǎn)外所有結(jié)點(diǎn)的個(gè)數(shù)，即

2、每個(gè)結(jié)點(diǎn)的度數(shù)之和等于結(jié)點(diǎn)總數(shù)減 1，故而 C 答案正確。 結(jié)點(diǎn)的度等于該結(jié)點(diǎn)子樹(shù)的個(gè)數(shù)，而結(jié)點(diǎn)與子樹(shù)之間是以邊連接的，所以一棵樹(shù)中每個(gè)結(jié)點(diǎn)的度數(shù)之和與邊的條數(shù)相等， D 答案正確。 一棵樹(shù)的度等于結(jié)點(diǎn)中度數(shù)最大的結(jié)點(diǎn)的度數(shù)，而不是樹(shù)中各結(jié)點(diǎn)的度數(shù)之和。故而，B 答案錯(cuò)誤。,B,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)一 樹(shù)的概念,2. 有一棵樹(shù)如右圖所示，回答下面的問(wèn)題：,(1). 這棵樹(shù)的根結(jié)點(diǎn)是_. (2). 這棵樹(shù)的葉子結(jié)點(diǎn)是_. (3). 結(jié)點(diǎn) k3 的度是_. (4). 這棵樹(shù)的度是_. (5). 這棵樹(shù)的深度是_. (6). 結(jié)點(diǎn) k3 的孩子結(jié)點(diǎn)是_. (7). 結(jié)點(diǎn) k3 的父結(jié)點(diǎn)是_.,

3、k1,k2, k5, k7, k4,2,3,4,k5, k6,k1,【解析】由圖可知， (1). 這棵樹(shù)的根結(jié)點(diǎn)是結(jié)點(diǎn) k1。 (2). 這棵樹(shù)的葉子結(jié)點(diǎn)是 k2、 k5、 k7、 k4 。 (3). k3 結(jié)點(diǎn)有 2 個(gè)孩子結(jié)點(diǎn) k5 與 k6，故而其度為 2。 (4). 樹(shù)的度等于數(shù)中度最大的結(jié)點(diǎn)的度數(shù)，本題中度數(shù)最大的結(jié)點(diǎn)為根結(jié)點(diǎn)，度數(shù)為 3。 故而，樹(shù)的度為 3。 (5). 很顯然本題的樹(shù)的層數(shù)為 4 層，第一層（層數(shù)我們從 1 開(kāi)始算）有結(jié)點(diǎn) k1，第二 層有結(jié)點(diǎn) k2、 k3 和 k4，第三層有結(jié)點(diǎn) k5 和 k6，第四層有結(jié)點(diǎn) k7。因而，樹(shù)的深度為 4。 (6). k3 結(jié)點(diǎn)的

4、孩子結(jié)點(diǎn)為 k5、 k6。 (7). k3 結(jié)點(diǎn)的父結(jié)點(diǎn)是結(jié)點(diǎn) k1。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)一 樹(shù)的概念,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù),本考點(diǎn)主要考查： 二叉樹(shù) 包括： 1、 二叉樹(shù)的定義及其主要特征； 2、 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)； 3、二叉樹(shù)的遍歷； 4、 線索二叉樹(shù)的基本概念和構(gòu)造。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù)二叉樹(shù)的定義及其主要特征,設(shè)高度為 h 的二叉樹(shù)上只有度為 0 和度為 2 的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為 （ ） A. 2h B. 2h-1 C. 2h+1 D. h+1,B,【解析】 高度為 h，而且只有度數(shù)為 0 或者 2 的結(jié)

5、點(diǎn)，這是什么樣的樹(shù)呢？如下圖所示的二叉樹(shù)就是一棵這樣的二叉樹(shù)。,由圖可以觀察出，除了第 1 層，其他每一層都是兩個(gè)結(jié)點(diǎn)，故而總共有結(jié)點(diǎn) 2 （ h-1）+1=2h-1。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù)二叉樹(shù)的定義及其主要特征,2. 以下說(shuō)法錯(cuò)誤的是 ( ) A. 存在這樣的二叉樹(shù)，對(duì)它采用任何次序遍歷其結(jié)點(diǎn)訪問(wèn)序列均相同 B. 二叉樹(shù)是樹(shù)的特殊情形 C. 由樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的 D. 在二叉樹(shù)只有一棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù),【解析】 盡管二叉樹(shù)與樹(shù)有許多相似之處，但二叉樹(shù)不是樹(shù)的特殊情形，故而 B 答案錯(cuò)誤。 對(duì)于 A 答案，如果二叉樹(shù)中只有

6、一個(gè)根結(jié)點(diǎn)，則不管采用什么樣的遍歷算法，所得訪問(wèn)序列都是一樣的。 對(duì)于 C 答案，樹(shù)轉(zhuǎn)換成二叉樹(shù)時(shí)，樹(shù)的左孩子為樹(shù)的一個(gè)孩子，第二個(gè)孩子成為其左孩子的右孩子，第三個(gè)孩子（如果存在的話）成為其左孩子的右孩子的右孩子。故而，根結(jié)點(diǎn)的右子樹(shù)總是空的。 二叉樹(shù)是有序樹(shù)，其左右孩子有次序之分，即使只有一棵子樹(shù)也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)。,B,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù)二叉樹(shù)的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組中 R1.n，結(jié)點(diǎn) Ri若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn) ( ),A. R2i+1 B. R2i C. Ri/2 D. R2i-1,B,【

7、解析】 將完全二叉樹(shù)存儲(chǔ)在數(shù)組中 R1n中，結(jié)點(diǎn) Ri若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn) R2i，若有右孩子，則右孩子的編號(hào)為結(jié)點(diǎn) R2i+1。故而，本題選擇 B 答案。 值得注意的是，一般二叉樹(shù)的順序存儲(chǔ)，將每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)照，然后存儲(chǔ)在數(shù)組的相應(yīng)位置中，缺少的結(jié)點(diǎn)用“ 0”補(bǔ)齊。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù)二叉樹(shù)的遍歷,1. 該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為( ) 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,【解析】 前序遍歷

8、首先訪問(wèn)根結(jié)點(diǎn)，其次遍歷左子樹(shù)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)，即遍歷左右子樹(shù)時(shí)仍然采用前序遍歷方法。 對(duì)題中的二叉樹(shù)進(jìn)行前序遍歷，可以得到序列 EACBDGF，故而選擇 C答案。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù)二叉樹(shù)的遍歷,2. 該二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為 ( ) 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,【解析】 中序遍歷首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)

9、，仍然先遍歷左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)，即遍歷左右子樹(shù)時(shí)仍然采用中序遍歷方法。 對(duì)題中的二叉樹(shù)進(jìn)行中序遍歷，可以得到序列 ABCDEGF，故而選擇 A答案。,A,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù)二叉樹(shù)的遍歷,3. 該二叉樹(shù)的按層遍歷的序列為 （ ） 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àn)的二叉樹(shù)遍歷算法。層次遍歷二叉樹(shù)，即從上到下，從左到右遍歷二叉樹(shù)的結(jié)點(diǎn)。 對(duì)題中的二叉樹(shù)進(jìn)行層次遍歷，可以得到序列 EA

10、GEFBD，故而選擇 C 答案。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù)線索二叉樹(shù)的基本概念和構(gòu)造,1. 引入二叉線索樹(shù)的目的是 ( ) A. 加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B. 為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除 C. 為了能方便的找到雙親 D. 使二叉樹(shù)的遍歷結(jié)果唯一,【解析】引入二叉線索樹(shù)的目的是有效利用空指針域，提高遍歷運(yùn)算的效率， 加快查找結(jié)點(diǎn)的前驅(qū)或者后繼結(jié)點(diǎn)的速度， 簡(jiǎn)化遍歷算法。對(duì)于有 n 個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有 n+1 條線索。,A,2. 在中序線索二叉樹(shù)中，若某結(jié)點(diǎn)有右孩子，則該結(jié)點(diǎn)的直接后繼是 ( ) A. 左子樹(shù)的最右下結(jié)點(diǎn) B. 右子樹(shù)的最右下結(jié)點(diǎn) C. 左子樹(shù)的

11、最左下結(jié)點(diǎn) D. 右子樹(shù)的最左下結(jié)點(diǎn),第四部分 樹(shù)與二叉樹(shù),考點(diǎn)二 二叉樹(shù)線索二叉樹(shù)的基本概念和構(gòu)造,【解析】 二叉樹(shù)的線索化說(shuō)透了就是按照某種遍歷算法將結(jié)點(diǎn)的線索引向前驅(qū)或者后繼（若不存在左孩子，則左指針引向該遍歷序列的直接前驅(qū)結(jié)點(diǎn)；若不存在右孩子，則右指針引向該遍歷序列的直接后繼結(jié)點(diǎn)）。若中序遍歷時(shí)，某結(jié)點(diǎn)有右孩子，那么該結(jié)點(diǎn)中序遍歷的直接后繼應(yīng)該是其右子樹(shù)的最左下的結(jié)點(diǎn)。故而，本題選擇 D 答案。,D,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)三 樹(shù)和森林,本考點(diǎn)主要考查： 1、 樹(shù)的存儲(chǔ)結(jié)構(gòu)； 2、 森林與二叉樹(shù)的轉(zhuǎn)換； 3、 樹(shù)和森林的遍歷。 本部分內(nèi)容的命題形式比較固定，解題方法也比較固定，同學(xué)們

12、可以通過(guò)掌握一個(gè)題的解題方法，而掌握一類(lèi)題型的解題方法。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)三 樹(shù)和森林,1. 設(shè) F 是由 T1、 T2 和 T3 三棵樹(shù)組成的森林，與 F 對(duì)應(yīng)的二叉樹(shù)為 B，T1、 T2 和 T3 的結(jié)點(diǎn)數(shù)分別為 N1、 N2 和 N3，則二叉樹(shù) B 的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為 ( ) A. N1-1 B. N2-1 C. N2+N3 D. N1+N3,A,【解析】本題道理與第 1 題相同。 F 是由 T1、 T2 和 T3 三棵樹(shù)組成的森林，與 F 對(duì)應(yīng)的二叉樹(shù)為 B， T1、 T2 和 T3 的結(jié)點(diǎn)數(shù)分別為 N1、 N2 和 N3，則二叉樹(shù) B 的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù) N1

13、-1。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)四 樹(shù)和二叉樹(shù)的應(yīng)用,本考點(diǎn)主要考查： 1、 二叉排序樹(shù)； 2、 平衡二叉樹(shù)； 3、 哈夫曼(Huffman)樹(shù)和哈夫曼編碼。 前兩個(gè)知識(shí)點(diǎn)結(jié)合課本第九章出題，這里主要掌握第三個(gè)知識(shí)點(diǎn)。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)四 樹(shù)和二叉樹(shù)的應(yīng)用哈夫曼樹(shù)和哈夫曼編碼,1. 由五個(gè)分別帶權(quán)值為 9， 2， 3， 5， 14 的葉子結(jié)點(diǎn)構(gòu)成的一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為 ( ) A. 60 B. 66 C. 67 D. 50,C,【解析】哈夫曼樹(shù)的構(gòu)造過(guò)程如下： (1). 根據(jù)給定的 n 個(gè)權(quán)值w1, w2, , wn，構(gòu)造 n 棵二叉樹(shù)的集合 F = T1, T2,

14、, Tn，其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為 wi 的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù); (2). 在 F 中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹(shù)，分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和; (3). 從 F 中刪去這兩棵樹(shù)，同時(shí)將剛生成的新樹(shù)加入到 F 中; (4). 重復(fù) (2) 和 (3) 兩步，直至 F 中只含一棵樹(shù)為止。,由五個(gè)分別帶權(quán)值為 9， 2， 3， 5， 14 的葉子結(jié)點(diǎn)構(gòu)成的一棵哈夫曼樹(shù)，該哈夫曼樹(shù)如下圖所示。,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)四 樹(shù)和二叉樹(shù)的應(yīng)用哈夫曼樹(shù)和哈夫曼編碼,由上圖可知，該哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為 WPS

15、=(2+3) 4 + 5 3 + 9 2 + 14 = 67,第四部分 樹(shù)與二叉樹(shù),考點(diǎn)四 樹(shù)和二叉樹(shù)的應(yīng)用哈夫曼樹(shù)和哈夫曼編碼,2. 設(shè)某哈夫曼樹(shù)中有 199 個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有( )個(gè)葉子結(jié)點(diǎn)。 A. 99 B. 100 C. 101 D. 102,B,【解析】正如第一題所言， 哈夫曼樹(shù)其實(shí)是二叉樹(shù)的一種。哈夫曼樹(shù)的特點(diǎn)是沒(méi)有度為 1 的結(jié)點(diǎn)，根據(jù)二叉樹(shù)的性質(zhì)可知 n0=n2+1。所以，具有 n0 個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)具有 n0-1個(gè)度為 2 的結(jié)點(diǎn)。 當(dāng) n=199 時(shí)， n0+n2=199，可知 n0=100， n2=99。故而，本題選擇 B 答案。,第五部分 圖,考點(diǎn)一 圖的基本

16、概念,本部分考查圖的基本概念，包括： 1、頂點(diǎn)、邊、度、完全圖、子圖、路徑、 連通圖等基本概念； 2、圖的頂點(diǎn)集和邊集的表示。 本考點(diǎn)考查的都是圖的基本內(nèi)容,連通分量指的是 （ ） 無(wú)向圖中的極小連通子圖 B. 無(wú)向圖中的極大連通子圖 C. 有向圖中的極小連通子圖 D. 有向圖中的極大連通子圖,第五部分 圖,考點(diǎn)一 圖的基本概念,B,【解析】本題考查連通分量的基本概念。連通分量是針對(duì)無(wú)向圖而言的，是無(wú)向圖中的極大連通子圖（與極小連通子圖進(jìn)行區(qū)別）。如下圖左圖所示，無(wú)向圖 G 有 3 個(gè)連通分量，分別如右圖所示。,第五部分 圖,考點(diǎn)二 圖的存儲(chǔ)及基本操作,本考點(diǎn)考查圖的鄰接矩陣、鄰接表、鄰接多重

17、表和十字鏈表四種存儲(chǔ)結(jié)構(gòu)表示及相應(yīng)的空間復(fù)雜度。,第五部分 圖,考點(diǎn)二 圖的存儲(chǔ)及基本操作,1. 圖的鄰接矩陣表示法適用于表示 （ ） A. 無(wú)向圖 B. 有向圖 C. 稠密圖 D. 稀疏圖,【解析】 常見(jiàn)的圖的存儲(chǔ)方式有主要有兩種：鄰接矩陣和鄰接表。 鄰接矩陣屬于順序存儲(chǔ)結(jié)構(gòu)，鄰接表屬于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鄰接矩陣易于實(shí)現(xiàn)圖的操作，但對(duì)稀疏圖而言尤其浪費(fèi)空間。 故而，鄰接矩陣一般用于存儲(chǔ)稠密圖（鄰接表一般適用于稀疏圖）。,C,2. 帶權(quán)有向圖 G 用鄰接矩陣 A 存儲(chǔ)，則頂點(diǎn) i 的入度等于 A 中（ ） A. 第 i 行非無(wú)窮的元素之和 B. 第 i 列非無(wú)窮且非 0 的元素個(gè)數(shù) C. 第 i

18、行非無(wú)窮且非 0 的元素個(gè)數(shù) D. 第 i 行與第 i 列非無(wú)窮且非 0 的元素之和,第五部分 圖,考點(diǎn)二 圖的存儲(chǔ)及基本操作,【解析】 對(duì)于鄰接矩陣表示的有向圖，第 i 行表示的是頂點(diǎn) Vi的出度，而第 i 列表示的是頂點(diǎn) Vi的入度。帶權(quán)圖不同于不帶權(quán)圖，帶權(quán)圖 Aij=x 表示從Vi到Vj的邊的權(quán)值為 x，而在不帶權(quán)圖中，鄰接矩陣中只有 0、 1 兩個(gè)值，值為 1 表示從 Vi到Vj有邊，為 0 則表示沒(méi)有邊。故而，第 i 列非無(wú)窮且非 0 元素的元素個(gè)數(shù)之和，即為頂點(diǎn) A 的入度。,B,第五部分 圖,考點(diǎn)三 圖的遍歷,本考點(diǎn)主要考查 圖的深度優(yōu)先、 廣度優(yōu)先搜索遍歷和層次遍歷的過(guò)程。

19、請(qǐng)同學(xué)們掌握用鄰接表和鄰接矩陣存儲(chǔ)表示下，圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷和層次遍歷的方法和時(shí)間復(fù)雜度。,第五部分 圖,考點(diǎn)三 圖的遍歷,1. 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示。,(1). 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn) v1 出發(fā)，所得到的頂點(diǎn)序列是 （ ） 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)先遍歷算法，從頂點(diǎn) v1 出發(fā)，所得到的頂點(diǎn)序列是 （ ） A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,

20、v5,v4 D. v1,v4,v3,v5,v2,C,B,第五部分 圖,考點(diǎn)三 圖的遍歷,【解析】 為了說(shuō)明深度優(yōu)先遍歷和廣度優(yōu)先遍歷，我們給出了本題。請(qǐng)同學(xué)們多留意遍歷方法。 (1). 從頂點(diǎn) v1 出發(fā)，發(fā)起深度優(yōu)先遍歷，經(jīng)過(guò) v1v3,再 v3v4， v4 沒(méi)有后續(xù)頂點(diǎn)，轉(zhuǎn)回 v3， v3 的后續(xù)頂點(diǎn)中還有 v5 沒(méi)有被遍歷過(guò)，于是找到 v3v5，再由 v5v2。 因而，得到一個(gè)序列 v1v3v4v5v2。選擇C答案。 (2). 從頂點(diǎn) v1 出發(fā)，發(fā)起廣度優(yōu)先遍歷。因?yàn)閺?v1 發(fā)出，有一條有向邊 v1v3。因此，有序列 v1v3v2，可有序列 v1v3v2v4v5，選擇 B 答案。,第

21、五部分 圖,考點(diǎn)四 圖的應(yīng)用,本考點(diǎn)主要考查圖的應(yīng)用，包括最小生成樹(shù)、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑。本考點(diǎn)特別重要。,第五部分 圖,考點(diǎn)四 圖的應(yīng)用最小生成樹(shù),1. 已知一個(gè)圖 G 如圖所示，在該圖的最小生成樹(shù)中各邊上數(shù)值之和為 （ ）,A. 21 B. 26 C. 28 D. 33,B,第五部分 圖,考點(diǎn)四 圖的應(yīng)用最小生成樹(shù),【解析】 我們可以利用克魯斯卡爾算法構(gòu)造最小生成樹(shù)，過(guò)程如圖所示。,由圖可知，原圖的最小生成樹(shù)各邊上的權(quán)值之和為 2+3+4+7+10=26，故而選擇 B 答案。,第五部分 圖,考點(diǎn)四 圖的應(yīng)用拓?fù)渑判?1. 已知有向圖 G = (V, E), 其中 V = V1,

22、V2, V3, V4, V5, V6, V7， E=, , , , , , , ,， G 的拓?fù)湫蛄惺?（ ） 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,第五部分 圖,考點(diǎn)四 圖的應(yīng)用拓?fù)渑判?【解析】 本題考查有向圖的拓?fù)渑判蚍椒?。本題中的圖 G 如圖所示。對(duì)圖G 進(jìn)行拓?fù)渑判?，其中的一個(gè)排序過(guò)程如圖所示。,由圖 5.24 可得到一個(gè)拓?fù)湫蛄袨?V1、 V3、 V4、 V6、 V2、 V5、 V7。當(dāng)然，本題的圖G 的拓?fù)渑判蚩梢缘玫蕉鄠€(gè)正確的序列，比如 V1、 V2、 V3、 V4、 V5、 V6、 V7 或 V1、 V3、V4、 V2、 V6、 V5、 V7 等等。本題選A。,第五部分 圖,考點(diǎn)四 圖的應(yīng)用拓?fù)渑判?2. 在有向圖 G 的拓?fù)湫蛄兄校繇旤c(diǎn) Vi 在頂點(diǎn) Vj 之前，則下列情形不可能出現(xiàn)的是 （ ） A. G 中有弧 B. G 中有一條從 Vi 到 Vj 的路徑 C. G 中沒(méi)