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