計(jì)算機(jī)專業(yè)基礎(chǔ)綜合歷年真題試卷匯編1?

(總分：62.00，做題時(shí)間：90分鐘)?

一、 單項(xiàng)選擇題(總題數(shù)：27，分?jǐn)?shù)：54.00)?

1.單項(xiàng)選擇題1-40小題。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。（分?jǐn)?shù)：2.00）?

__________________________________________________________________________________________?

解析：?

2.先序序列為a，b，c，d的不同二叉樹的個(gè)數(shù)是_______。?

（分?jǐn)?shù)：2.00）?

?A.13?

?B.14 √?

?C.15?

?D.16?

解析：解析：根據(jù)二叉樹前序遍歷和中序遍歷的遞歸算法中遞歸工作棧的狀態(tài)變化得出：前序序列和中序

序列的關(guān)系相當(dāng)于以前序序列為入棧次序，以中序序列為出棧次序。因?yàn)榍靶蛐蛄泻椭行蛐蛄锌梢晕ㄒ坏?/p>

確定一棵二叉樹，所以題意相當(dāng)于“以序列a，b，c，d為入棧次序，則出棧序列的個(gè)數(shù)為?”，對于n個(gè)

n

不同元素進(jìn)棧，出棧序列的個(gè)數(shù)為 C? ?=14。?

2n

3.假設(shè)棧初始為空，將中綴表達(dá)式a／b+(c*d-e*f)／g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式的過程中，當(dāng)掃描到f時(shí)，

棧中的元素依次是_______。?

（分?jǐn)?shù)：2.00）?

?A.+(*-?

?B.+(-* √?

?C.／+(*-*?

?D.／+-*?

解析：解析：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法思想如下： 從左向右開始掃描中綴表達(dá)式； 遇到數(shù)

字時(shí)，加入后綴表達(dá)式； 遇到運(yùn)算符時(shí)： a．若為‘(’，入棧； b．若為‘)’，則依次把棧中的的運(yùn)算

符加入后綴表達(dá)式中，直到出現(xiàn)‘(’，從棧中刪除‘(’； c．若為除括號外的其他運(yùn)算符，當(dāng)其優(yōu)先級

高于除‘(’以外的棧頂運(yùn)算符時(shí)，直接入棧。否則從棧頂開始，依次彈出比當(dāng)前處理的運(yùn)算符優(yōu)先級高和

優(yōu)先級相等的運(yùn)算符，直到一個(gè)比它優(yōu)先級低的或者遇到了一個(gè)左括號為止。 當(dāng)掃描的中綴表達(dá)式結(jié)束時(shí)，

棧中的所有運(yùn)算符依次出棧加入后綴表達(dá)式。?

4.在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1

的結(jié)點(diǎn)，則樹T的葉結(jié)點(diǎn)個(gè)數(shù)是_______。?

（分?jǐn)?shù)：2.00）?

?A.41?

?B.82 √?

?C.113?

?D.122?

解析：解析：設(shè)樹中度為i(i=0，1，2，3，4)的結(jié)點(diǎn)數(shù)分別為N? ，樹中結(jié)點(diǎn)總數(shù)為N，則樹中各結(jié)點(diǎn)的

i

度之和等于N-1，即N=1+N? +2N? +3N? +4N? =N? +N? +N? +N? +N? ，根據(jù)題設(shè)中的數(shù)據(jù)，即可得到

123401234

N? =82，即樹T的葉結(jié)點(diǎn)的個(gè)數(shù)是82。?

0

5.已知一棵完全二叉樹的第6層(設(shè)根為第1層)有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是_______。?

（分?jǐn)?shù)：2.00）?

?A.39?

?B.52?

?C.111 √?

?D.119?

解析：解析：完全二叉樹比滿二叉樹只是在最下面一層的右邊缺少了部分葉結(jié)點(diǎn)，而最后一層之上是個(gè)滿

二叉樹，并且只有最后兩層有葉結(jié)點(diǎn)。第6層有葉結(jié)點(diǎn)則完全二叉樹的高度可能為6或7，顯然樹高為7

時(shí)結(jié)點(diǎn)更多。若第6層上有8個(gè)葉結(jié)點(diǎn)，則前六層為滿二叉樹，而第7層缺失了8×2=16個(gè)葉結(jié)點(diǎn)，故完

7

全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多為(2? -1)-16=111個(gè)結(jié)點(diǎn)。?

6.若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是_______。?

（分?jǐn)?shù)：2.00）?

?A.257?

?B.258?

?C.384 √?

?D.385?

解析：解析：根據(jù)完全二叉樹的性質(zhì)，最后一個(gè)分支結(jié)點(diǎn)的序號為=384，故葉子結(jié)點(diǎn)的個(gè)數(shù)為

768-384=384。?

7.給定二叉樹如下圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷

后的結(jié)點(diǎn)序列為3，1，7，5，6，2，4，則其遍歷方式是_______。?

（分?jǐn)?shù)：2.00）?

?A.LRN?

?B.NRL?

?C.RLN?

?D.KNL √?

解析：解析：分析遍歷后的結(jié)點(diǎn)序列，可以看出根結(jié)點(diǎn)是在中間訪問，而右子樹結(jié)點(diǎn)在左子樹之前，即遍

歷的方式是RNL。本題考查的遍歷方法并不是二叉樹的3種基本遍歷方法，對于考生而言，重要的是要掌

握遍歷的思想。?

8.先序序列為a，b，c，d的不同二叉樹的個(gè)數(shù)是_______。?

（分?jǐn)?shù)：2.00）?

?A.13?

?B.14 √?

?C.15?

?D.16?

解析：解析：根據(jù)二叉樹前序遍歷和中序遍歷的遞歸算法中遞歸工作棧的狀態(tài)變化得出：前序序列和中序

序列的關(guān)系相當(dāng)于以前序序列為入棧次序，以中序序列為出棧次序。因?yàn)榍靶蛐蛄泻椭行蛐蛄锌梢晕ㄒ坏?/p>

確定一棵二叉樹，所以題意相當(dāng)于“以序列a，b，c，d為入棧次序，則出棧序列的個(gè)數(shù)為?”，對于n個(gè)

n

不同元素進(jìn)棧，出棧序列的個(gè)數(shù)為 C? ?=14。?

n+1

9.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1，2，3，4和4，3，2，1，則該二叉樹的中序遍

歷序列不會是_______。?

（分?jǐn)?shù)：2.00）?

?A.1，2，3，4?

?B.2，3，4，1?

?C.3，2，4，1 √?

?D.4，3，2，1?

解析：解析：前序序列為NLR，后序序列為LRN，由于前序序列和后序序列剛好相反，故不可能存在一個(gè)結(jié)

點(diǎn)同時(shí)存在左右孩子，即二叉樹的高度為4。1為根結(jié)點(diǎn)，由于根結(jié)點(diǎn)只能有左孩子(或右孩子)，因此，在

中序序列中，1或在序列首或在序列尾，ABCD皆滿足要求。僅考慮以1的孩子結(jié)點(diǎn)2為根結(jié)點(diǎn)的子樹，它

也只能有左孩子(或右孩子)，因此，在中序序列中，2或在序列首或序列尾，ABD皆滿足要求。?

10.若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)

點(diǎn)_______。?

（分?jǐn)?shù)：2.00）?

?A.只有e √?

?B.有e、b?

?C.有e、c?

?D.無法確定?

解析：解析：前序序列和后序序列不能唯一確定一棵二叉樹，但可以確定二叉樹中結(jié)點(diǎn)的祖先關(guān)系：當(dāng)兩

個(gè)結(jié)點(diǎn)的前序序列為XY與后序序列為YX時(shí)，則X為Y的祖先?？紤]前序序列 a ，e，b，d，c、后序序列

b，c，d，e， a ，可知a為根結(jié)點(diǎn)，e為a的孩子結(jié)點(diǎn)；此外，a的孩子結(jié)點(diǎn)的前序序列 e ，b，d，c、

后序序列b，c，d， e ，可知e是bcd的祖先，故根結(jié)點(diǎn)的孩子結(jié)點(diǎn)只有e。故選A。?

11.對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是_______。?

（分?jǐn)?shù)：2.00）?

?A.95，22，91，24，94，71 √?

?B.92，20，91，34，88，35?

?C.21，89，77，29，36，38?

?D.12，25，71，68，33，34?

解析：解析：各選項(xiàng)對應(yīng)的查找過如下圖，BCD對應(yīng)的查找樹都是二叉排序樹，A對應(yīng)的查找樹不是二叉排

序樹，因?yàn)樵?1為根的左子樹中出現(xiàn)了比91大點(diǎn)的結(jié)點(diǎn)94。

?

12.在任意一棵非空二叉排序樹T? 中，刪除某結(jié)點(diǎn)v之后形成二叉排序樹T? ，再將v插入T? 形成二叉

122

排序樹T? 。下列關(guān)于T? 與T? 的敘述中，正確的是_______。 Ⅰ．若v是T? 的葉結(jié)點(diǎn)，則T? 與T??

313113

不同 Ⅱ．若v是T? 的葉結(jié)點(diǎn)，則T? 與T? 相同 Ⅲ．若v不是T? 的葉結(jié)點(diǎn)，則T? 與T? 不同 Ⅳ．若

113113

v不是T? 的葉結(jié)點(diǎn)，則T? 與T? 相同?

113

（分?jǐn)?shù)：2.00）?

?A.僅Ⅰ、Ⅲ?

?B.僅Ⅰ、Ⅳ?

?C.僅Ⅱ、Ⅲ √?

?D.僅Ⅱ、Ⅳ?

解析：解析：在一棵二叉排序樹中刪除一個(gè)結(jié)點(diǎn)后再將此結(jié)點(diǎn)插入到二叉排序樹中，如果刪除的結(jié)點(diǎn)是葉

子結(jié)點(diǎn)，那么在插入結(jié)點(diǎn)后，后來的二叉排序樹與刪除結(jié)點(diǎn)之前相同。如果刪除的結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，那

么再插入這個(gè)結(jié)點(diǎn)后，后來的二叉樹會發(fā)生變化，不完全相同。?

13.下列二叉排序樹中，滿足平衡二叉樹定義的是_______。?

（分?jǐn)?shù)：2.00）?

?A.?

?B. √?

?C.?

?D.?

解析：解析：根據(jù)平衡二叉樹的定義有，任意結(jié)點(diǎn)的左、右子樹高度差的絕對值不超過1。而其余3個(gè)選

項(xiàng)均可以找到不符合該條件的結(jié)點(diǎn)。在做題的過程中，如果答案不太明顯，可以把每個(gè)非葉結(jié)點(diǎn)的平衡因

子都寫出來再進(jìn)行判斷。?

14.在下圖所示的平衡二叉樹中，插入關(guān)鍵字48后得到一棵新平衡二叉樹。在新平衡二叉樹中，關(guān)鍵字37

所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是_______。?

（分?jǐn)?shù)：2.00）?

?A.13，48?

?B.24，48?

?C.24，53 √?

?D.24，90?

解析：解析：插入48以后，該二叉樹根結(jié)點(diǎn)的平衡因子由-1變?yōu)?2，在最小不平衡子樹根結(jié)點(diǎn)的右子樹

(R)的左子樹(L)中插入新結(jié)點(diǎn)引起的不平衡屬于RL型平衡旋轉(zhuǎn)，需要做兩次旋轉(zhuǎn)操作(先右旋后左旋)。

調(diào)整后，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是24、53。?

15.若平衡二叉樹的高度為6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為_______。?

（分?jǐn)?shù)：2.00）?

?A.10?

?B.20 √?

?C.32?

?D.33?

解析：解析：所有非葉結(jié)點(diǎn)的平衡因子均為1，即平衡二叉樹滿足平衡的最少結(jié)點(diǎn)情況，如下圖所示。?

對于高度為N、左右子樹的高度分別為N-1和N-2、所有非葉結(jié)點(diǎn)的平衡因子均為1的平衡二叉樹，總結(jié)點(diǎn)

數(shù)的公式為：C? =C? +C? +1，C? =1，C? =2，C? 2+1+1=4，可推出C? =20。 畫圖法：先畫出T? 和

NN-1N-212361

T? ；然后新建一個(gè)根結(jié)點(diǎn)，連接T? 、T? 構(gòu)成T? ；新建一個(gè)根結(jié)點(diǎn)，連接T? 、T? 構(gòu)成T? ；……

2213324

依此類推，直到畫出T? ，可知T? 的結(jié)點(diǎn)數(shù)為20。 排除法：對于選項(xiàng)A，高度為6、結(jié)點(diǎn)數(shù)為10的樹

66

怎么也無法達(dá)到平衡。對于選項(xiàng)C，結(jié)點(diǎn)較多時(shí)，考慮較極端情形，即第6層只有最左葉子的完全二叉樹

剛好有32個(gè)結(jié)點(diǎn)，雖然滿足平衡的條件，但顯然再刪去部分結(jié)點(diǎn)，依然不影響平衡，不是最少結(jié)點(diǎn)的情況。

同理D錯(cuò)誤。只可能選B。?

16.若將關(guān)鍵字1，2，3，4，5，6，7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支

結(jié)點(diǎn)的個(gè)數(shù)是_______。?

（分?jǐn)?shù)：2.00）?

?A.0?

?B.1?

?C.2?

?D.3 √?

解析：解析：利用7個(gè)關(guān)鍵字構(gòu)建平衡二叉樹T，平衡因子為O的分支結(jié)點(diǎn)個(gè)數(shù)為3，構(gòu)建的平衡二叉樹如

下圖所示。構(gòu)造及調(diào)整的過程如下：?

17.現(xiàn)有一棵無重復(fù)關(guān)鍵字的平衡二叉樹(AVL樹)，對其進(jìn)行中序遍歷可得到一個(gè)降序序列。下列關(guān)于該平

衡二叉樹的敘述中，正確的是_______。?

（分?jǐn)?shù)：2.00）?

?A.根結(jié)點(diǎn)的度一定為2?

?B.樹中最小元素一定是葉結(jié)點(diǎn)?

?C.最后插入的元素一定是葉結(jié)點(diǎn)?

?D.樹中最大元素一定是無左子樹 √?

解析：解析：只有兩個(gè)結(jié)點(diǎn)的平衡二叉樹的根結(jié)點(diǎn)的度為1，A錯(cuò)誤。中序遍歷后可以得到一個(gè)降序序列，

樹中最小元素一定無左子樹(可能有右子樹)，因此不一定是葉結(jié)點(diǎn)，B錯(cuò)誤。最后插入的結(jié)點(diǎn)可能會導(dǎo)致

平衡調(diào)整，而不一定是葉結(jié)點(diǎn)，C錯(cuò)誤。?

18.將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，

u和v可能具有的關(guān)系是_______。Ⅰ．父子關(guān)系Ⅱ．兄弟關(guān)系Ⅲ．u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系?

（分?jǐn)?shù)：2.00）?

?A.只有Ⅱ?

?B.Ⅰ和Ⅱ √?

?C.Ⅰ和Ⅲ?

?D.Ⅰ、Ⅱ和Ⅲ?

解析：解析：森林與二叉樹的轉(zhuǎn)換規(guī)則為“左孩子右兄弟”。在最后生成的二叉樹中，父子關(guān)系在對應(yīng)森

林關(guān)系中可能是兄弟關(guān)系或原本就是父子關(guān)系。 情形Ⅰ：若結(jié)點(diǎn)v是結(jié)點(diǎn)u的第二個(gè)孩子結(jié)點(diǎn)，在轉(zhuǎn)換時(shí)，

結(jié)點(diǎn)v就變成結(jié)點(diǎn)u第一個(gè)孩子的右孩子，符合要求。 情形Ⅱ．結(jié)點(diǎn)u和v是兄弟結(jié)點(diǎn)的關(guān)系，但二者之

中還有一個(gè)兄弟結(jié)點(diǎn)k，則轉(zhuǎn)換后，結(jié)點(diǎn)v就變?yōu)榻Y(jié)點(diǎn)k的右孩子，而結(jié)點(diǎn)k則是結(jié)點(diǎn)u的右孩子，符合

要求。

情形Ⅲ：若結(jié)點(diǎn)u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系，則轉(zhuǎn)換后，結(jié)點(diǎn)u和v分別在兩者最

左父結(jié)點(diǎn)的兩棵子樹中，不可能出現(xiàn)在同一條路徑中。

根據(jù)樹與二叉樹的轉(zhuǎn)換規(guī)則，將這4種情況

轉(zhuǎn)換成樹種結(jié)點(diǎn)的關(guān)系。(1)在原來的樹中u是v的父結(jié)點(diǎn)的父結(jié)點(diǎn)；(2)在樹中u是v的父結(jié)點(diǎn)；(3)在樹

中u是v的父結(jié)點(diǎn)的兄弟；(4)在樹中u與v是兄弟關(guān)系。由此可知Ⅰ和Ⅱ正確。?

19.己知一棵有2011個(gè)結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個(gè)數(shù)為116，該樹對應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)是_______。?

（分?jǐn)?shù)：2.00）?

?A.115?

?B.116?

?C.1895?

?D.1896 √?

解析：解析：樹轉(zhuǎn)換為二叉樹時(shí)，樹中每一個(gè)分支結(jié)點(diǎn)的所有子結(jié)點(diǎn)中的最右子結(jié)點(diǎn)無右孩子，根結(jié)點(diǎn)轉(zhuǎn)

換后也沒有右孩子，因此，對應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)=分支結(jié)點(diǎn)數(shù)+1=2011-116+1=1896。通常本

題應(yīng)采用特殊法解，設(shè)題意中的樹是如下圖所示的結(jié)構(gòu)，則對應(yīng)的二叉樹中僅有前115個(gè)葉結(jié)點(diǎn)有右孩子，

故無右孩子的結(jié)點(diǎn)個(gè)數(shù)=2011-115=1896。?

20.將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T，F(xiàn)中葉結(jié)點(diǎn)的個(gè)數(shù)等于_______。?

（分?jǐn)?shù)：2.00）?

?A.T中葉結(jié)點(diǎn)的個(gè)數(shù)?

?B.T中度為1的結(jié)點(diǎn)個(gè)數(shù)?

?C.T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù) √?

?D.T中右孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)?

解析：解析：將森林轉(zhuǎn)化為二叉樹即相當(dāng)于用孩子兄弟表示法表示森林。在變化過程中，原森林某結(jié)點(diǎn)的

第一個(gè)孩子結(jié)點(diǎn)作為它的左子樹，它的兄弟作為它的右子樹。那么森林中的葉結(jié)點(diǎn)由于沒有孩子結(jié)點(diǎn)，那

么轉(zhuǎn)化為二叉樹時(shí)，該結(jié)點(diǎn)就沒有左結(jié)點(diǎn)，所以F中葉結(jié)點(diǎn)的個(gè)數(shù)就等于T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)，

選C。此題還可以通過一些特例來排除A、B、D選項(xiàng)。?

21.下列線索二叉樹中(用虛線表示線索)，符合后序線索樹定義的是_______。?

（分?jǐn)?shù)：2.00）?

?A.?

?B.?

?C.?

?D. √?

解析：解析：題中所給二叉樹的后序序列為d，b，c，a。結(jié)點(diǎn)d無前驅(qū)和左子樹，左鏈域空，無右子樹，

右鏈域指向其后繼結(jié)點(diǎn)b；結(jié)點(diǎn)b無左子樹，左鏈域指向其前驅(qū)結(jié)點(diǎn)d；結(jié)點(diǎn)c無左子樹，左鏈域指向其前

驅(qū)結(jié)點(diǎn)b，無右子樹，右鏈域指向其后繼結(jié)點(diǎn)a。故選D。?

22.若X是后序線索二叉樹中的葉結(jié)點(diǎn)，且X存在左兄弟結(jié)點(diǎn)Y，則X的右線索指向的是_______。?

（分?jǐn)?shù)：2.00）?

?A.X的父結(jié)點(diǎn) √?

?B.以Y為根的子樹的最左下結(jié)點(diǎn)?

?C.X的左兄弟結(jié)點(diǎn)Y?

?D.以Y為根的子樹的最右下結(jié)點(diǎn)?

解析：解析：根據(jù)后序線索二叉樹的定義，X結(jié)點(diǎn)為葉子結(jié)點(diǎn)且有左兄弟，那么這個(gè)結(jié)點(diǎn)為右孩子結(jié)點(diǎn)，

利用后序遍歷的方式可知X結(jié)點(diǎn)的后序后繼是其父結(jié)點(diǎn)，即其右線索指向的是父結(jié)點(diǎn)。為了更加形象，在

解題的過程中可以畫出如下草圖。

?

23.若對如下的二叉樹進(jìn)行中序線索化，則結(jié)點(diǎn)x的左、右線索指向的結(jié)點(diǎn)分別是_______。?

（分?jǐn)?shù)：2.00）?

?A.e、c?

?B.e、a?

?C.d、c?

?D.b、a √?

解析：解析：線索二叉樹的線索實(shí)際上指向的是相應(yīng)遍歷序列特定結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，所以先寫

出二叉樹的中序遍歷序列：edbxac，中序遍歷中在x左邊和右邊的字符，就是它在中序線索化的左、右線

索，即b、a，選D。?

24.對n(n≥2)個(gè)權(quán)值均不相同的字符構(gòu)造哈夫曼樹。下列關(guān)于該哈夫曼樹的敘述中，錯(cuò)誤的是_______。?

（分?jǐn)?shù)：2.00）?

?A.該樹一定是一棵完全二叉樹 √?

?B.樹中一定沒有度為1的結(jié)點(diǎn)?

?C.樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)?

?D.樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值?

解析：解析：哈夫曼樹為帶權(quán)路徑長度最小的二叉樹，不一定是完全二叉樹。哈夫曼樹中沒有度為1的結(jié)

點(diǎn)，B正確；構(gòu)造哈夫曼樹時(shí)，最先選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左、右子樹構(gòu)造一棵新的二叉樹，C正確；

哈夫曼樹中任一非葉結(jié)點(diǎn)P的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和，其權(quán)值不小于其左、右子樹根結(jié)點(diǎn)的

權(quán)值，在與結(jié)點(diǎn)P的左、右子樹根結(jié)點(diǎn)處于同—層的結(jié)點(diǎn)中，若存在權(quán)值大于結(jié)點(diǎn)P權(quán)值的結(jié)點(diǎn)Q，那么

結(jié)點(diǎn)Q的兄弟結(jié)點(diǎn)中權(quán)值較小的一個(gè)應(yīng)該與結(jié)點(diǎn)P作為左、右子樹構(gòu)造新的二叉樹。綜上可知，哈夫曼樹

中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。?

25.5個(gè)字符有如下4種編碼方案，不是前綴編碼的是_______。?

（分?jǐn)?shù)：2.00）?

?A.01，0000，0001，001，1?

?B.011，000，001，010，1?

?C.000，001，010，011，100?

?D.0，100，110，1110，1100 √?

解析：解析：前綴編碼的定義是在一個(gè)字符集中，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。選

項(xiàng)D中編碼110是編碼1100的前綴，違反了前綴編碼的規(guī)則，所以D不是前綴編碼。?

26.下列選項(xiàng)給出的是從根分別到達(dá)兩個(gè)葉結(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是_______。?

（分?jǐn)?shù)：2.00）?

?A.24，10，5和24，10，7?

?B.24，10，5和24，12，7?

?C.24，10，10和24，14，11?

?D.24，10，5和24，14，6 √?

解析：解析：在哈夫曼樹中，左右孩子權(quán)值之和為父結(jié)點(diǎn)權(quán)值。僅以分析選項(xiàng)A為例：若兩個(gè)10分別屬于

兩棵不同的子樹，根的權(quán)值不等于其孩子的權(quán)值和，不符：若兩個(gè)10屬同棵子樹，其權(quán)值不等于其兩個(gè)孩

子(葉結(jié)點(diǎn))的權(quán)值和，不符。B、C選項(xiàng)的排除方法一樣。?

27.下列關(guān)于無向連通圖特性的敘述中，正確的是_______。Ⅰ．所有頂點(diǎn)的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂

點(diǎn)個(gè)數(shù)減1Ⅲ．至少有一個(gè)頂點(diǎn)的度為1?

（分?jǐn)?shù)：2.00）?

?A.只有Ⅰ √?

?B.只有Ⅱ?

?C.Ⅰ和Ⅱ?

?D.Ⅰ和Ⅲ?

解析：解析：每條邊都連接了兩個(gè)結(jié)點(diǎn)，在計(jì)算頂點(diǎn)的度之和時(shí)每條邊都被計(jì)算了兩次(出度和入度)，故

所有頂點(diǎn)的度之和為邊數(shù)的兩倍，Ⅰ正確。n個(gè)頂點(diǎn)、n-1條邊可以構(gòu)成無向連通圖，比如樹，Ⅱ錯(cuò)誤。頂

點(diǎn)數(shù)為N(N≥1)的無向完全圖中不存在度為1的頂點(diǎn)，Ⅲ錯(cuò)誤。?

二、 綜合應(yīng)用題(總題數(shù)：3，分?jǐn)?shù)：8.00)?

28.綜合應(yīng)用題41-47小題。?

__________________________________________________________________________________________?

解析：?

29.已知有6個(gè)頂點(diǎn)(頂點(diǎn)編號為0～5)的有向帶權(quán)圖G，其鄰接矩陣A為上三角矩陣，按行為主序(行優(yōu)先)

保存在如下的一維數(shù)組中。請寫出圖G的鄰接矩陣A。?

（分?jǐn)?shù)：2.00）?

__________________________________________________________________________________________?

正確答案：(正確答案：在上三角矩陣A[6][6]中，第1行至第5行主對角線上方的元素個(gè)數(shù)分別為5、4、

3、2、1，由此可以畫出壓縮存儲數(shù)組中的元素所屬行的情況，如下圖所示。

采用“平移”的思想，

分別將前5、4、3、2、1個(gè)元素，移動(dòng)到矩陣對角線(“0”)右邊的行上。 故，圖G的鄰接矩陣A如下圖

所示。

)?

解析：解析：考查上三角矩陣的存儲。?

二叉樹的帶權(quán)路徑長度(WPL)是二叉樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和。給定一棵二叉樹T，采用二叉鏈

表存儲，結(jié)點(diǎn)結(jié)構(gòu)為：

其中葉結(jié)點(diǎn)的weight域保存該結(jié)點(diǎn)的非負(fù)權(quán)值。設(shè)root為指向T的根結(jié)點(diǎn)

的指針，請?jiān)O(shè)計(jì)求T的WPL的算法，要求：（分?jǐn)?shù)：6.00）?

(1).給出算法的基本設(shè)計(jì)思想；（分?jǐn)?shù)：2.00）?

__________________________________________________________________________________________?

正確答案：(正確答案：算法的基本設(shè)計(jì)思想： ①基于先序遞歸遍歷的算法思想是用一個(gè)static變量記錄、

wpl，把每個(gè)結(jié)點(diǎn)的深度作為遞歸函數(shù)的 一個(gè)參數(shù)傳遞，算法步驟如下： 若該結(jié)點(diǎn)是葉結(jié)點(diǎn)，那么變量

wpl加上該結(jié)點(diǎn)的深度與權(quán)值之積； 若該結(jié)點(diǎn)是非葉結(jié)點(diǎn)，那么若左子樹不為空，對左子樹調(diào)用遞歸算法：

若右子樹不為空，對右子樹 調(diào)用遞歸算法，深度參數(shù)均為本結(jié)點(diǎn)的深度參數(shù)加1； 最后返回計(jì)算出的wpl

即可。 ②基于層次遍歷的算法思想是使用隊(duì)列進(jìn)行層次遍歷，并記錄當(dāng)前的層數(shù)， 當(dāng)遍歷到葉結(jié)點(diǎn)時(shí)，

累計(jì)wpl； 當(dāng)遍歷到非葉結(jié)點(diǎn)時(shí)，把該結(jié)點(diǎn)的子樹加入隊(duì)列； 當(dāng)某結(jié)點(diǎn)為該層的最后一個(gè)結(jié)點(diǎn)時(shí)，層數(shù)

自增1； 隊(duì)列空時(shí)遍歷結(jié)束，返回wpl。)?

解析：?

(2).使用C或C++語言，給出二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義；（分?jǐn)?shù)：2.00）?

__________________________________________________________________________________________?

正確答案：(正確答案：二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義如下： typedef struct BiTNode{ int weight； struct?

BiTNode *lchild，*rchild； }BiTNode，*BiTree；)?

解析：?

(3).根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。（分?jǐn)?shù)：2.00）?

__________________________________________________________________________________________?

正確答案：(正確答案：算法的代碼如下： ①基于先序遍歷的算法： int WPL(BiTree root){ return?

wpl_PreOrder(root，0)； } int wpl PreOrder(BiTree root，int deep){ static int wpl=0；／／定義

一個(gè)static變量存儲wpl if(root-＞lchild==NuLL＆＆root-＞lchild==NULL)／／若為葉結(jié)點(diǎn)，累積wpl?

wpl+=deep*root-＞weight， if(root-＞ichiid!；NuLL)／／若左子樹不空，對左子樹遞歸遍歷?

wpl_PreOrder(root-＞ichild，deep+1)， if(root-＞rchiidI=NULL)／／若右子樹不空，對右于樹遞歸遍

歷 wpl_PreOrder(root-＞rchild，deep+1)； return wpl； } ②基于層次遍歷的算法： #define MaxSize?

100／／設(shè)置隊(duì)列的最大容量 int wpl LevelOrder(BiTree root){ BiTree q[MaxSize]；／／聲明隊(duì)列，

end1為頭指針，end2為尾指針 int end1，end2，／／隊(duì)列最多容納MaxSize-1個(gè)元素 end1=end2=0；／

／頭指針指向隊(duì)頭元素，尾指針指向隊(duì)尾的后一個(gè)元素 int wpl=deep=0；／／初始化wpl和深度 BiTree?

lastNode；／／lastNode用來記錄當(dāng)前層的最后一個(gè)結(jié)點(diǎn) BiTree newlastNode；／／newlastNode用來記

錄下一層的最后一個(gè)結(jié)點(diǎn) lastNode=root；／／lastNode初始化為根結(jié)點(diǎn) newlastNode=NULL；／／

newlastNode初始化為空 q[end2++]=root；／／根結(jié)點(diǎn)入隊(duì) while(end1!=end2)f／／層次遍歷，若隊(duì)列

不空則循環(huán) BiTree t=q[end1++]；／／拿出隊(duì)列中的頭一個(gè)元素 if(t-＞ichild==NULL&&t-＞

lchild==NULL){ wpl+=deep*t-＞weight； }／／若為葉結(jié)點(diǎn)，統(tǒng)計(jì)wpl if(t-＞ichild!=NULL){／／若非

葉結(jié)點(diǎn)把左結(jié)點(diǎn)入隊(duì) q[end2++]=t-＞ichild； newlastNode=t-＞ichiid； }／／并設(shè)下一層的最后一個(gè)

結(jié)點(diǎn)為該結(jié)點(diǎn)的左結(jié)點(diǎn) if(t-＞rchild!=NULL){／／處理葉結(jié)點(diǎn) q[end2++]=t-＞rchild； newlastNode=t-

＞rchild； } if(t==lastNode){／／若該結(jié)點(diǎn)為本層最后一個(gè)結(jié)點(diǎn)，更新lastNode lastNode=newlastNode；?

deep+=1；／／層數(shù)加1 } } return wpl；／／返回wpl })?

解析：解析：考查二叉樹的帶權(quán)路徑長度，二叉樹的帶權(quán)路徑長度為每個(gè)葉結(jié)點(diǎn)的深度與權(quán)值之積的總和，

可以使用先序遍歷或?qū)哟伪闅v解決問題。?