數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題-資料下載頁(yè)
2025-08-04 16:52本頁(yè)面
【正文】 D．cedba31．二叉樹(shù)的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹(shù)根的右子樹(shù)的根是： A、 E B、 F C、 G D、 H 32．將一棵樹(shù)t 轉(zhuǎn)換為孩子—兄弟鏈表表示的二叉樹(shù)h，則t的后根序遍歷是h 的A．前序遍歷 B．中序遍歷 C．后序遍歷（ ） 33．下面的說(shuō)法中正確的是（ ）.（1）任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在三種遍歷中的相對(duì)次序不變；（2）按二叉樹(shù)定義，具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)共有6種。A．(1)(2) B．(1) C．(2) D．(1)、(2)都錯(cuò) 34．一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足（ ）A．所有的結(jié)點(diǎn)均無(wú)左孩子 B．所有的結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn) D．是任意一棵二叉樹(shù)35．在二叉樹(shù)結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（ ）A．都不相同 B．完全相同 C．先序和中序相同，而與后序不同 D．中序和后序相同，而與先序不同 36．某二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定是（）的二叉樹(shù)。 A．空或只有一個(gè)結(jié)點(diǎn) B．任一結(jié)點(diǎn)無(wú)左子樹(shù) C．高度等于其結(jié)點(diǎn)數(shù) D．任一結(jié)點(diǎn)無(wú)右子樹(shù)37．在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)（ ）。 A．左子結(jié)點(diǎn) B．右子結(jié)點(diǎn) C．左子結(jié)點(diǎn)和右子結(jié)點(diǎn) D．左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)38．在下列情況中，可稱為二叉樹(shù)的是（ ）A．每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的樹(shù) B. 哈夫曼樹(shù) C．每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的有序樹(shù) D. 每個(gè)結(jié)點(diǎn)只有一棵右子樹(shù) E．以上答案都不對(duì) 39. 一棵左子樹(shù)為空的二叉樹(shù)在先序線索化后，其中空的鏈域的個(gè)數(shù)是：( )A．不確定 B. 0 C. 1 D. 2 40. 一棵左右子樹(shù)均不空的二叉樹(shù)在先序線索化后，其中空的鏈域的個(gè)數(shù)是：( )。A. 0 B. 1 C. 2 D. 不確定 41．n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有的線索數(shù)為（ ）A．2n B．n－l C．n＋l D．n 42. 設(shè)F是一個(gè)森林，B是由F變換得的二叉樹(shù)。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)。A． n1 B．n C． n+1 D． n+2 43．由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（ ）A．2 B．3 C．4 D．5 44．下述編碼中哪一個(gè)不是前綴碼（ ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）45．下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（ ）。A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 度為2的有序樹(shù)與二叉樹(shù)的區(qū)別：有序樹(shù)的結(jié)點(diǎn)次序是相對(duì)于另一結(jié)點(diǎn)而言的，如果有序樹(shù)中的子樹(shù)只有一個(gè)孩子結(jié)點(diǎn)時(shí)，該孩子結(jié)點(diǎn)就無(wú)需區(qū)分其左右次序，而二叉樹(shù)無(wú)論其孩子結(jié)點(diǎn)是否為2，均需確定其左右次序。二、判斷題1. 二叉樹(shù)是度為2的有序樹(shù)。 ( F )2. 完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。 ( F )3. 對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2n。( F )4．深度為K的二叉樹(shù)中結(jié)點(diǎn)總數(shù)≤2k1。 ( T )5. 二叉樹(shù)以后序遍歷序列與前序遍歷序列反映的同樣的信息(他們反映的信息不獨(dú)立）。( T )6. 二叉樹(shù)的遍歷結(jié)果不是唯一的. ( T )7. 二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。 ( T )8. 樹(shù)可用投影法進(jìn)行中序遍歷。 ( F )9．用樹(shù)的前序遍歷和中序遍歷可以導(dǎo)出樹(shù)的后序遍歷。 ( F )10. 用鏈表（llinkrlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)時(shí)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)空指針。( T )三、填空題1．二叉樹(shù)由， 三個(gè)基本單元組成。 2．樹(shù)在計(jì)算機(jī)內(nèi)的表示方式有。 3．具有256個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為9。 4．深度為k的完全二叉樹(shù)至少有2k1個(gè)結(jié)點(diǎn)，至多有2k1個(gè)結(jié)點(diǎn)。5．在完全二叉樹(shù)中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是235。logi ==235。logj6．一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)有個(gè)度為1的結(jié)點(diǎn)、有個(gè)分支 （非 終端）結(jié)點(diǎn)和個(gè)葉子，該滿二叉樹(shù)的深度為。 7．高度為K的完全二叉樹(shù)至少有個(gè)葉子結(jié)點(diǎn)。 8．高度為8的完全二叉樹(shù)至少有64個(gè)葉子結(jié)點(diǎn)。 9．已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少是99。 10．一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為11。 四、應(yīng)用題1．有n個(gè)結(jié)點(diǎn)并且其高度為n的二叉樹(shù)的數(shù)目是多少? 2n1從根結(jié)點(diǎn)出到各葉子結(jié)點(diǎn)的單枝樹(shù)是不同的二叉樹(shù)此題等價(jià)于高度為n的滿二叉樹(shù)有多少個(gè)葉子結(jié)點(diǎn)？
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1