數(shù)據(jù)結(jié)構(gòu)(樹(shù)與二叉樹(shù))習(xí)題與答案

一、單選題1、已知一算術(shù)表達(dá)式的中綴形式為A-B/C+D*E，前綴形式為+-A/BC*DE，其后綴形式為()。A.ABC/-DE*+B.AB/C-D*E+C.A-BC/DE*+D.ABCDE/-*+正確答案：A2、有關(guān)二叉樹(shù)下列說(shuō)法正確的是（）。A.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2B.一棵二叉樹(shù)的度可以小于2C.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2D.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2正確答案：B3、在一棵高度為k的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（）。A.2k-1B.2k-1C.2k-1+1D.2k正確答案：B4、某二叉樹(shù)中有60個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)為（）。A.不確定B.60C.59D.61正確答案：C解析：任意二叉樹(shù)中，n0=n2+15、高度為7的完全二叉樹(shù)，最少有（）個(gè)結(jié)點(diǎn)。A.127B.128C.63D.64正確答案：D解析：前6層都是滿的，最后一層（第7層）近1個(gè)結(jié)點(diǎn)?？杀ＷC題目條件。6、高度為7的二叉樹(shù)，最少有（）個(gè)結(jié)點(diǎn)。A.7B.127C.13D.64正確答案：A解析：每層只有1個(gè)結(jié)點(diǎn)。共7個(gè)即可構(gòu)成一個(gè)高度為7的二叉樹(shù)。7、對(duì)任意一棵有n個(gè)結(jié)點(diǎn)的樹(shù)，這n個(gè)結(jié)點(diǎn)的度之和為()。A.n-1B.2*nC.n+2D.n正確答案：A解析：所有結(jié)點(diǎn)的度之和為分支個(gè)數(shù)，分支個(gè)數(shù)即為結(jié)點(diǎn)個(gè)數(shù)-18、在下列存儲(chǔ)形式中，（）不是樹(shù)的存儲(chǔ)形式。A.雙親表示法B.孩子-兄弟表示法C.孩子鏈表表示法D.順序存儲(chǔ)表示法正確答案：D9、對(duì)二叉樹(shù)中的結(jié)點(diǎn)進(jìn)行編號(hào)，要求根結(jié)點(diǎn)的編號(hào)最小，左孩子結(jié)點(diǎn)編號(hào)比右孩子結(jié)點(diǎn)編號(hào)小。則應(yīng)該采用（）遍歷方法對(duì)其進(jìn)行編號(hào)。A.層次B.先序C.后序D.中序正確答案：B10、某二叉樹(shù)中有60個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)為（）。A.59B.61C.60D.不一定正確答案：A11、樹(shù)的后根遍歷，相當(dāng)于對(duì)應(yīng)二叉樹(shù)的（）遍歷。A.中序B.后序C.層次D.先序正確答案：A二、判斷題1、完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。(×)2、完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是葉子。(√)3、二叉樹(shù)只能用二叉鏈表表示。(×)6、哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度等于其中所有結(jié)點(diǎn)的帶權(quán)路徑之和。(×)解析：哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。7、在葉子數(shù)目和權(quán)值相同的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度最小的樹(shù)一定是哈夫曼樹(shù)。(√)三、填空題1、有10個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，總結(jié)點(diǎn)個(gè)數(shù)是（）。正確答案：192、將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)時(shí)，遵循的規(guī)則是左孩子、（）。正確答案：右兄