樹(shù)據(jù)結(jié)構(gòu)第5章答案(已核)

一、選擇1．以下說(shuō)法錯(cuò)誤的是()A.樹(shù)形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨B.線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C.樹(shù)形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)雜的數(shù)據(jù)D.樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)2，以下說(shuō)法錯(cuò)誤的是(BC)A.二叉樹(shù)可以是空集B.二叉樹(shù)的任一結(jié)點(diǎn)都有兩棵子樹(shù)(是“最多有”兩棵子樹(shù))C.二叉樹(shù)與樹(shù)具有相同的樹(shù)形結(jié)構(gòu)(二叉樹(shù)的孩子必有左右之分,只有一個(gè)孩子時(shí)也要分出左右,而樹(shù)即使是有序樹(shù),只有一個(gè)孩子時(shí)部分左右)D.二叉樹(shù)中任一結(jié)點(diǎn)的兩棵子樹(shù)有次序之分3、以下說(shuō)法錯(cuò)誤的是()A.完全二叉樹(shù)上結(jié)點(diǎn)之間的父子關(guān)系可由它們編號(hào)之間的關(guān)系來(lái)表達(dá)B.在三叉鏈表上，二叉樹(shù)的求雙親運(yùn)算很容易實(shí)現(xiàn)C.在二叉鏈表上，求根，求左、右孩子等很容易實(shí)現(xiàn)D.在二叉鏈表上，求雙親運(yùn)算的時(shí)間性能很好4、以下說(shuō)法錯(cuò)誤的是()A.一般在哈夫曼樹(shù)中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近A.64B.63C.32D.31)A.42B.40C.21D.20A.n-1B.nC.5floor(logn)D.無(wú)法確定2注：完全二叉樹(shù)才能確定其深度。數(shù)最少()個(gè)A.k+1B.2kC.2k-1D.2k+19．下列說(shuō)法中正確的是()A.任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2B.任何一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2C.任何一棵二叉樹(shù)中的度肯定等于2D.任何一棵二叉樹(shù)中的度可以小于2列A.0B.1C.2D.不存在這樣的二叉樹(shù)已知某二叉樹(shù)的后續(xù)遍歷序列是dabec,中序遍歷序列是deabc,它的先序遍歷序列是()A.acbedB.deabcC.decabD.cedba12．某二叉樹(shù)的先序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是()A.bdgcefhaB.gdbecfhaC.D.bdgechfaD.gdbehfca13、二叉樹(shù)的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說(shuō)法A.正確B.錯(cuò)誤14．由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹(shù)是一種特殊的樹(shù)，這種說(shuō)法A.正確B.錯(cuò)誤15．二叉樹(shù)是每個(gè)結(jié)點(diǎn)的度不超過(guò)2的有序樹(shù)的特殊情況，這種說(shuō)法()A.正確B.錯(cuò)誤A.16B.32C.31D.10二、填空2.一棵樹(shù)上的任何結(jié)點(diǎn)(不包括根本身)稱為根的__子孫______。若B是A__________3.一般的，二叉樹(shù)有__空____二叉樹(shù)、__只有根__的二叉樹(shù)、只有_左子樹(shù)______的二叉樹(shù)五種基本形叉樹(shù)、只有_右子樹(shù)______的二叉樹(shù)、同時(shí)有___左子樹(shù)_、右子樹(shù)_的二叉樹(shù)五種基本形i(i>=1)層上至多有___2i-1___個(gè)結(jié)點(diǎn)。kk的二叉樹(shù)至多有___2K-1___個(gè)結(jié)點(diǎn)。6.對(duì)任何二叉樹(shù)，若度為2i(i>=1)層上至多有___2i-1___個(gè)結(jié)點(diǎn)。kk的二叉樹(shù)至多有___2K-1___個(gè)結(jié)點(diǎn)。2027.滿二叉樹(shù)上各層的結(jié)點(diǎn)數(shù)已達(dá)到了二叉樹(shù)可以容納的__極限_。滿二叉樹(shù)也是_完全Llogn2X10.二叉樹(shù)通常有__順序__存儲(chǔ)結(jié)構(gòu)和_鏈?zhǔn)絖存儲(chǔ)結(jié)構(gòu)兩類(lèi)存儲(chǔ)結(jié)構(gòu)。__根__結(jié)點(diǎn)的指針，該指針具有標(biāo)識(shí)二叉鏈表的作用。11.__根__結(jié)點(diǎn)的指針，該指針具有標(biāo)識(shí)二叉鏈表的作用。13.二叉鏈表中每個(gè)存儲(chǔ)結(jié)點(diǎn)的每個(gè)指針域必須有一個(gè)值，這個(gè)值或者是_____空_____14.具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中,一共有___2n___個(gè)指針域,其中只有__n-1__個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的___n+1_個(gè)指針域?yàn)镹ULL。．二叉樹(shù)有不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中最常用的是__二叉鏈表__與__三叉鏈表_。結(jié)點(diǎn)之后。17．哈夫曼樹(shù)是帶權(quán)路徑度__最小_的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根__越近___。0020．由任何一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)時(shí)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。三、簡(jiǎn)答題義。2．簡(jiǎn)述三叉鏈表的類(lèi)型定義。4