第2頁共8頁第1頁共8頁一、單選題（6小題，每小題2分，共12分）1、一個(gè)無向樹中有7條邊，則它結(jié)點(diǎn)數(shù)為()。A.5；B.6；C.7；D.8．D2、設(shè)有28盞燈，擬公用一個(gè)電源，則至少需要４插頭的接線板的數(shù)目為（）．A．7；B．8；C．9；D．14．C3、下面哪一種圖不一定是樹（）．A．無圈的連通圖；B．有ｎ個(gè)結(jié)點(diǎn)ｎ－１條邊的連通圖；C．每對結(jié)點(diǎn)間都有路的圖；D．連通但刪去一條邊就不連通的圖．C4、設(shè)G=〈V，E〉為（ｎ，ｍ）連通圖，則要確定Ｇ的一棵生成樹，必刪去Ｇ的邊數(shù)是（）．A．ｎ－ｍ－１；B．ｎ－ｍ＋１；C．ｍ－ｎ＋１；D．ｍ－ｎ－１．C5、下面哪一種圖不一定是樹（）．A．無圈連通圖；B．有個(gè)結(jié)點(diǎn)條邊的無圈圖；C．每對結(jié)點(diǎn)間都有路的圖；D．無圈但增加一條邊，就得到一個(gè)且僅有一個(gè)圈．C6、設(shè)完全二叉樹Ｔ有ｔ片葉子。ｅ條邊，則有（）．A．ｅ>2(t-1)；B．e<2(t-1)；C．e=2(t-1)；D．e=2(t+1)．C二、填空題（11小題，每空1分，共12分）(1分)1、無向圖G具有生成樹，當(dāng)且僅當(dāng)___________________。圖G連通(1分)2、一棵有向樹T，若T恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度都為1，則稱T為根樹。其中稱為樹葉。出度為0的結(jié)點(diǎn)(1分)3、一個(gè)無向樹中有6條邊，則它結(jié)點(diǎn)數(shù)為。7(1分)4、一棵有向樹T，若T恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度都為1，則稱T為根樹。其中稱為樹根。入度為0的結(jié)點(diǎn)(1分)5、一棵有9個(gè)葉結(jié)點(diǎn)的完全三叉樹，有個(gè)內(nèi)點(diǎn)．4(1分)6、設(shè)有33盞燈，擬公用一個(gè)電源，則至少需要5插頭的接線板的數(shù)目為。8(1分)7、若G為(n,m)（n為結(jié)點(diǎn)數(shù)，m為邊數(shù)）連通圖，要確定G的一棵生成樹必刪去G的_______________條邊。m-n+1(2分)8、在一棵根樹中，有且只有一個(gè)結(jié)點(diǎn)的入度為，其余所有結(jié)點(diǎn)的入度均為。0；1(1分)9、若一棵樹有2個(gè)結(jié)點(diǎn)度數(shù)為2，一個(gè)結(jié)點(diǎn)度數(shù)為3，3個(gè)結(jié)點(diǎn)度數(shù)為4，其余是葉結(jié)點(diǎn)，則該樹有個(gè)葉結(jié)點(diǎn)。9(1分)10、如果有一臺計(jì)算機(jī)，它有一條加法指令，可計(jì)算四個(gè)數(shù)的和?，F(xiàn)有28個(gè)數(shù)需要計(jì)算和，它至少要執(zhí)行次這個(gè)加法指令。9(1分)11、一棵樹有2個(gè)度為2的結(jié)點(diǎn)，1個(gè)度為3的結(jié)點(diǎn)，4個(gè)度為4的結(jié)點(diǎn)，1個(gè)度為5的結(jié)點(diǎn)，其余均是度為1的結(jié)點(diǎn)，則有個(gè)度為1的結(jié)點(diǎn)．14三、簡答題（6小題，每小題6分，共36分）1、今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用（單位：萬元）如圖邊上的數(shù)字所示．要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費(fèi)用．AABCDEFGHIJKS2222223.55452634531解：該問題相當(dāng)于求圖的最小生成樹問題，此圖的最小生成樹為：（4分）因此如圖鋪設(shè)煤氣管道所需費(fèi)用最小，最小費(fèi)用為：2＋2＋2＋2＋2＋2＋2+3＋3+4+1＝25（萬元）．（2分）2、以給定權(quán)1,4,9,16,25,36,49,64,81,100構(gòu)造一棵最優(yōu)二叉樹。解：根據(jù)哈夫曼算法，最優(yōu)二叉樹如下圖所示385385166219851191008164364955302514165914（2分）（2分）（2分）3、下圖給出的賦權(quán)圖表示八個(gè)城市及架起城市間直接通訊線路的預(yù)測造價(jià)，試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小，并計(jì)算出最小造價(jià)。解：該問題相當(dāng)于求上圖的最小生成樹。按下圖架起八個(gè)城市間直接通訊線路的造價(jià)最?。钚≡靸r(jià)為：W（T）=180+240+200+280+120+90+220=1330（2分）（4分）4、以給定權(quán)2，4，5，8，13，15，18，25構(gòu)造一棵最優(yōu)二叉樹．（根據(jù)樹的完整程度酌情減分）5、下圖給出的賦權(quán)圖表示五個(gè)城市A、B、C、D、E及架起城市間直接通訊線路的預(yù)測造價(jià)（以千萬RMB計(jì)）。試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小，并計(jì)算出最小造價(jià)。解：根據(jù)克魯斯科爾算法，最小生成樹如圖所示，即包含如下四條邊： （4分）C(A,B),C(B,C),C(D,E),C(B,E)C(T)=3+6+2+4=15(千萬RMB) （2分）答：按如圖所示設(shè)計(jì)使得各城市間能夠通訊且總造價(jià)最小，最小造價(jià)為15千萬RMB.6、下圖給出的賦權(quán)圖表示七個(gè)城市及架起城市間直接通訊線路的預(yù)測造價(jià)，試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小，并計(jì)算出最小造價(jià)