計算機(jī)算法-單元測驗(yàn)-第5章樹和二叉樹

計算機(jī)算法_單元測驗(yàn)_第5章樹和二叉樹[復(fù)制]1.對于一棵具有n個結(jié)點(diǎn)、度為4的樹來說，_______________。[單選題]*A.樹的高度至多是n-3(正確答案)B.樹的高度至多是n-4C.第i層上至多有4*(i-1)個結(jié)點(diǎn)D.至少在某一層上正好有4個結(jié)點(diǎn)2.一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是___________。[單選題]*A.250B.501(正確答案)C.254D.5053.在高度為h的完全二叉樹中，______________________。[單選題]*A.度為0的結(jié)點(diǎn)都在第h層上B.第i（1≤i≤h）層上結(jié)點(diǎn)都是度為2的結(jié)點(diǎn)C.第i（1≤i<h）層上有個結(jié)點(diǎn)(正確答案)D.不存在度為1的結(jié)點(diǎn)4.若二叉樹的中序遍歷序列是abcdef，且c為根結(jié)點(diǎn)，則________________。[單選題]*A.結(jié)點(diǎn)c有兩個孩子(正確答案)B.二叉樹有兩個度為0的結(jié)點(diǎn)C.二叉樹的高度為5D.以上都不對5.在任何一棵二叉樹中，如果結(jié)點(diǎn)a有左孩子b和右孩子c，則在結(jié)點(diǎn)的先序序列、中序序列和后序序列中，___________。[單選題]*A.結(jié)點(diǎn)b一定在結(jié)點(diǎn)a的前面B.結(jié)點(diǎn)a一定在結(jié)點(diǎn)c的前面C.結(jié)點(diǎn)b一定在結(jié)點(diǎn)c的前面(正確答案)D.結(jié)點(diǎn)a一定在結(jié)點(diǎn)b的前面6.設(shè)n、m為一棵二叉樹上的兩個結(jié)點(diǎn)，在中序遍歷時，n在m前的條件是___________。[單選題]*A.n在m的右方B.n是m的祖先C.n在m的左方(正確答案)D.n是m的子孫7.如果在一棵二叉樹的先序序列、中序序列和后序序列中，結(jié)點(diǎn)a、b的位置都是a在前、b在后（形如…a…b…），則___________。[單選題]*A.a、b可能是兄弟(正確答案)B.a可能是b的雙親C.a可能是b的孩子D.不存在這樣的二叉樹8.若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)是_________。[單選題]*A.11(正確答案)B.9C.18D.159.具有10個葉結(jié)點(diǎn)的二叉樹中有_________個度為2的結(jié)點(diǎn)。[單選題]*A.8B.9(正確答案)C.10D.1110.一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是_________。[單選題]*A.254B.505C.501(正確答案)D.25011.二叉樹的第l（只有根結(jié)點(diǎn)時的層數(shù)為1）層上最多含有結(jié)點(diǎn)數(shù)為_________。[單選題]*A.2^(l-1)(正確答案)B.2^(l-1)-1C.2^lD.2^l-112.一棵二叉樹高度為h（只有根結(jié)點(diǎn)時的高度為1）,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有_________結(jié)點(diǎn)。[單選題]*A.2h-1(正確答案)B.h+1C.2hD.2h+113.高度為K（只有根結(jié)點(diǎn)時的高度為1）的二叉樹最大的結(jié)點(diǎn)數(shù)為_________。[單選題]*A.2^k-1(正確答案)B.2^(k-1)C.2^kD.2^(k-1)-114.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以_________。[單選題]*A.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用B.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲(正確答案)C.它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲D.它不能用順序存儲結(jié)構(gòu)存儲15.一個二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為_________。[單選題]*A.DEBCFAB.DEBFCA(正確答案)C.DEBAFCD.DEFBCA16.有n個葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為_________。[單選題]*A.2n-1(正確答案)B.不確定C.2n+1D.2n17.下面關(guān)于Huffman樹的說法，不正確的是_________。[單選題]*A.Huffman樹中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn)(正確答案)B.Huffman樹中沒有度為1的結(jié)點(diǎn)C.Huffman樹具有最小權(quán)值路徑長度D.對應(yīng)與一組權(quán)值構(gòu)造出的Huffman樹一般不是唯一的18.若一個二叉樹的葉子結(jié)點(diǎn)是某子樹的中序遍歷序列中的最后一個結(jié)點(diǎn)，則它必是該子樹的___________遍歷序列中的最后一個結(jié)點(diǎn)。[填空題]*_________________________________(答案：先序|后序|根序)19.度為m的樹中至少有一個度為m的結(jié)點(diǎn)。[單選題]*A.√(正確答案)B.×20.在樹型結(jié)構(gòu)中，處于同一層上的各結(jié)點(diǎn)之間具有兄弟關(guān)系。[單選題]*A.√B.×(正確答案)21.某個二叉樹有n個度為0的結(jié)點(diǎn)，n-1個度為1的結(jié)點(diǎn)，n-2個度為2的結(jié)點(diǎn)。事實(shí)上，這種樹是不存在的。[單選題]*A.√(正確答案)B.×22.在任何一棵完全二叉樹中，終端結(jié)點(diǎn)或者和分支結(jié)點(diǎn)一樣多，或者只比分支結(jié)點(diǎn)多1個。[單選題]*A.√(正確答案)B.×23.在赫夫曼樹中，權(quán)值相同的樹葉結(jié)點(diǎn)都在同一層上。[單選題]*A.√B.×(正確答案)24.若一個樹葉是某二叉樹先序遍歷序列中的最后一個結(jié)點(diǎn)，則它必是該樹中