数据结构练习 第六章 树.doc

1、1数据结构练习 第六章 树一、选择题1.树最适合用来表示( )。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据2.二叉树的第 k 层的结点数最多为( ).A2 k-1 B.2K+1 C.2K-1 D. 2 k-13.设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。A. 2m-1 B. 2m C. 2m+1 D. 4m4设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树得到序列为（ ） 。A. BADC B. BCDA C. CDAB D. CBDA5.设某棵二叉树

2、中有 2000 个结点，则该二叉树的最小高度为（ ） 。A. 9 B. 10 C. 11 D. 126设一棵二叉树的深度为 k，则该二叉树中最多有（ ）个结点。A. 2k-1 B .2k C. 2k-1 D. 2k-17设某二叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 Nl，度数为 2的结点数为 N2，则下列等式成立的是（ ） 。A. N0=N1+1 B. N0=Nl+N2 C. N0=N2+1 D. N0=2N1+l8设一棵 m 叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 Nl，度数为 m 的结点数为 Nm，则 N0=（ ） 。A. Nl+N2+Nm B. l

3、+N2+2N3+3N4+(m-1)NmC. N2+2N3+3N4+(m-1)Nm D. 2Nl+3N2+(m+1)Nm9设一组权值集合 W=2，3，4，5，6，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ） 。A. 20 B. 30 C. 40 D. 4510设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ） 。A. 空或只有一个结点 B. 高度等于其结点数C. 任一结点无左孩子 D. 任一结点无右孩子11设某棵三叉树中有 40 个结点，则该三叉树的最小高度为（ ） 。A. 3 B. 4 C. 5 D. 612深度为 k 的完全二叉树中最少有（ ）个结点。A.

4、2k-1-1 B. 2k-1 C. 2k-1+1 D. 2k-113设某哈夫曼树中有 199 个结点，则该哈夫曼树中有（ ）个叶子结点。A. 99 B. 100 C. 101 D. 10214设按照从上到下、从左到右的顺序从 1 开始对完全二叉树进行顺序编号，则编号为 i 结点的左孩子结点的编号为（ ） 。A. 2i+1 B. 2i C. i/2 D. 2i-115设某棵二叉树的高度为 10，则该二叉树上叶子结点最多有（ ） 。A. 20 B. 256 C. 512 D. 1024216设一棵完全二叉树中有 65 个结点，则该完全二叉树的深度为（ ） 。A. 8 B. 7 C. 6 D. 51

5、7设一棵三叉树中有 2 个度数为 1 的结点，2 个度数为 2 的结点，2 个度数为3 的结点，则该三叉链权中有（ ）个度数为 0 的结点。A. 5 B. 6 C. 7 D. 818设无向图 G 中的边的集合 E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点 a 出发进行深度优先遍历可以得到的一种顶点序列为（ ） 。A. aedfcb B. acfebd C. aebcfd D.aedfbc19设 F 是由 T1、T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为B，T1、T2 和 T3 的结点数分别为 N1、N2 和 N3，则二叉树 B

6、的根结点的左子树的结点数为（ ） 。A. N1-1 B. N2-1 C. N2+N3 D. N1+N320设在一棵度数为 3 的树中，度数为 3 的结点数有 2 个，度数为 2 的结点数有 1 个，度数为 1 的结点数有 2 个，那么度数为 0 的结点数有（ ）个。A. 4 B. 5 C. 6 D. 721设一棵 m 叉树中有 N1个度数为 1 的结点，N 2个度数为 2 的结点，Nm个度数为 m 的结点，则该树中共有（ ）个叶子结点。A. B. C. D. ii1)(ii1mii2 miiN2)1(22设一组权值集合 W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一

7、棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ） 。A.129 B. 219 C. 189 D. 22923设某棵二叉树中只有度数为 0 和度数为 2 的结点且度数为 0 的结点数为n，则这棵二叉中共有（ ）个结点。A. 2n B. n+l C. 2n-1 D. 2n+l24由权值分别为 3,6,7,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） 。A51 B23 C53 D7425在一棵二叉树中，第 4 层上的结点数最多为（ ） 。A31 B8 C15 D1626二叉树上叶结点数等于（ ） 。A分支结点数加 1 B单分支结点数加 1 C双分支结点数加 1 D双分支结点数 减 1

8、27对某二叉树进行前序遍历的结果为 ABDEFC，中序遍历的结果为 DBFEAC，则后序周游的结果为（ ）ADBFEAC BDFEBCACBDFECA DBDEFAC28将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为 1。编号为 49 的结点 X 的双亲编号为（ ）A24 B. 25 C.23 D.无法确定29含有 n 个结点的二叉树采用二叉链表存储时，空指针域的个数为（ ）A.n-1 B.n C.n+1 D.n+230在一棵深度为 H 的完全二叉树中，所含结点的个数不少于（ ）3A.2H-1-1 B.2H-1 C.2H-1 D.2H31某二叉树的

9、先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )A.高度等于其结点数 B.任一结点无左孩子 C.任一结点无右孩子 D.空或只有一个结点32在完全二叉树中，若一个结点是叶结点，则它没有( )A.左孩子结点 B.右孩子结点 C.左孩子结点和右孩子结点 D.左孩子结点，右孩子结点和兄弟结点33除根结点外，树上每个结点( )A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲34题 9 图中树的度为( )A.2 B.3C.5D.8 题 9 图35高度为 h 的完全二叉树中，结点数最多为（ ）A2h-1 B.2h+1

10、 C.2h-1 D.2h36由 m 棵结点数为 n 的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（ ）Amn B.mn-1 C.n(m-1) D.m(n-1)37含有 10 个结点的二叉树中，度为 0 的结点数为 4，则度为 2 的结点数为（ ） A.3 B.4 C.5 D.638对一棵有 100 个结点的完全二叉树按层编号，则编号为 49 的结点，它的父结点的编号为（ ）A.24 B.25 C.98 D.9939可以惟一地转化成一棵一般树的二叉树的特点是（ ）A.根结点无左孩子 B.根结点无右孩子C.根结点有两个孩子 D.根结点没有孩子40关于二叉树性质

11、的描述，正确的是（ ）A.二叉树结点的个数可以为 0B.二叉树至少含有一个根结点C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子41具有 4 个结点的二叉树可有（ ）A.4 种形态 B.7 种形态 C.10 种形态 D.11 种形态42一棵有 16 结点的完全二叉树，对它按层编号，则对编号为 7 的结点 X，它的双亲结点及右孩子结点的编号分别为（ ）A2，14 B2，15C3，14 D3，15443具有 2000 个结点的二叉树，其高度至少为（ ） 。A9 B10C11 D1244如果结点 A 有 3 个兄弟，而且 B 为

12、 A 的双亲，则 B 是度为（ ）A3 B4 C5 D145二叉树第 i(i1)层最多有（ ）个结点。A2 i B2i C2 i-1 D2 i -146如果树的结点有 4 个兄弟，而且 B 为 A 的双亲，则 B 的度为（ ）A3 B4 C5 D147设一棵二叉树共有 20 个度为 2 的结点，则叶子结点共有（ ）个。A40 B19 C20 D2148一棵完全二叉树中根结点的编号为 1，而且 23 号结点有左孩子但没有右孩子，则完全二叉树共有（ ）个结点。A24 B45 C46 D4749一棵深度为 k 的满二叉树有（ ）个结点。A2 k -1 B2 k-1 C2k D2 k50一棵完全二叉树

13、的结点按层次遍历从 1 开始编号，如果编号为 m 的结点有双亲，则双亲的编号为（ ） 。A2m Bm/2Cm1 Dm-151由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） 。A、 24 B、 48 C、 72 D、 5352从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ） 。A O(n) B O(1) C O(log 2n) D O(n 2)53向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ） 。A O(1) B O(log 2n ) C O(n) D O( nlog2n)54根据 n 个元素建立一棵二叉搜索树时，其时间复杂度大致为（ ） 。

14、A O(n) B O(log 2n ) C O(n 2) D O( nlog2n)55从堆中删除一个元素的时间复杂度为（ ） 。AO(1) B O(n) C O(log 2n) D O( nlog2n)56向堆中插入一个元素的时间复杂度为（ ） 。A O(log 2n) B、 O(n) C、 O(1) D、 O( nlog2n)57由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） 。A 24 B 48 C 72 D 5358由权值分别为 11，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）A 24 B 71 C 48 D 5359设

15、F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非叶结点，则 B中右指针域为空的结点有（ ）个。An-1 Bn Cn+1 Dn+260具有 65 个结点的完全二叉树的高度为（ ） 。 （根的层次号为 0）A8 B7 C6 D5561有关二叉树下列说法正确的是（ B ）A二叉树的度为 2 B一棵二叉树的度可以小于 2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的度都为 262设树 T 的度为 4，其中度为 1,2,3 和 4 的结点个数分别为 4,2,1,1,则 T 中的叶子数为（ D ）。A5 B6 C7 D863已知一算术表达式的中缀表达式为 a-(b+c/d

16、)*e，其后缀形式为( D)。 A.a+b*c/d B.a+b*cd/e C. -+*abc/de D. abcd/+e*-64设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p,p 的右子树结点个数为 n,森林 F 中第一棵树的结点个数是（A ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定65若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（B ）A9 B11 C15 D不确定 66在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1的结点数为 2 个，则度为 0 的结点数为（C ）个。A4 B

17、5 C6 D7 67设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 M1，M2和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是（ D ）。AM1 BM1+M2 CM3 DM2+M368已知一棵完全二叉树中共有 626 个结点，叶子结点的个数应为(C )。A. 311 B. 312 C. 313 D. 314 E. 其它69有关二叉树下列说法正确的是（B ）A二叉树的度为 2 B一棵二叉树的度可以小于 2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的度都为 270二叉树的第 I 层上最多含有结点数为（C）A2 I B 2 I-1-1 C 2 I-1 D

18、2 I -171一个具有 1025 个结点的二叉树的高 h 为（ C ）A11 B10 C11 至 1025 之间 D10 至 1024 之间72在一棵高度为 k 的满二叉树中，结点总数为（C ）A2 k-1 B2 k C2 k-1 Dlog2 k+173有 n（n 0）个分枝结点的满二叉树的深度是(C )。A.n2-1 B. log2(n+1)+1 C. log2(n+1) D. log2(n-1)74对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C)次序的遍历实现编号。A先序 B. 中序

19、C. 后序 D. 从根开始按层次遍历75树的后根遍历序列等同于该树对应的二叉树的(B ) A. 先序序列 B. 中序序列 C. 后序序列76在下列存储形式中，哪一个不是树的存储形式？（D ）A. 双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法77高度为 h(h0)的满二叉树对应的森林由(D )棵树构成。6A. 1 B. log2h C. h/2 D. h 78某二叉树结点的中序序列为 BDAECF,后序序列为 DBEFCA,则该二叉树对应的森林包括(C)棵树。A.1 B.2 C.3 D.479二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJK

20、G 。该二叉树根的右子树的根是： CA. E B. F C. G D. H80将一棵树 t 转换为孩子兄弟链表表示的二叉树 h，则 t 的后根序遍历是h 的（ B ）A前序遍历 B中序遍历 C后序遍历81对任意一棵树，设它有 n 个结点，这 n 个结点的度数之和为(C )。A.n B.n-2 C.n-1 D.n+1 82一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( C)。A其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子C其中只有一个叶子结点 D.其中度为 2 的结点最多为一个83在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（B ）A都

21、不相同 B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同 84某二叉树的先序序列和后序序列正好相反，则该二叉树一定是(B )的二叉树A空或只有一个结点 B.高度等于其结点数C任一结点无左孩子 D. 任一结点无右孩子85在完全二叉树中，若一个结点是叶结点，则它没(C )。A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点86二叉树在线索化后，仍不能有效求解的问题是（D）。A. 先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继87由 3 个结点可以构造出多少种不同的有向树？（

22、A ）A2 B3 C4 D5 88下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（D）。A. 二叉排序树 B哈夫曼树 CAVL 树 D堆89一棵 Huffman 树共有 215 个结点，对其进行 Huffman 编码，共能得到(B )个不同的码字；A. 107 B. 108 C. 214 D. 21590下述编码中哪一个不是前缀码（ B ）。A.(00,01,10,11) B.(0,1,00,11) C.(0,10,110,111) D.(1,01,000,001)91设 X 是树 T 中的一个非根结点，B 是 T 所对应的二叉树。在 B 中，X 是其双

23、亲的右孩子，下列结论正确的是(D)。A在树 T 中，X 是其双亲的第一个孩子 B.在树 T 中，X 一定无右边兄弟7C. 在树 T 中，X 一定是叶子结点 D.在树 T 中，X 一定有左边兄弟92一颗完全二叉树上有 1001 个结点，其中叶子结点的个数是（ B ）A250 B501 C254 D50093一颗有 124 个叶结点的完全二叉树，最多有（B ）个结点A247 B248 C249 D25194一棵具有 n 个结点的完全二叉树的树高度（深度）是（A ）Alogn+1 Blogn+1 Clogn Dlogn-195已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac ,

24、 它的前序遍历是（ D ） 。Aacbed Bdecab Cdeabc Dcedba96二叉树的第 I 层上最多含有结点数为（ C）A2 I B 2 I-1-1 C 2 I-1 D2 I -1二、填空题1假定一棵树的广义表表示为 A（C，D（E，F，G） ，H（I，J） ） ，则树中所含的结点数为_个，树的深度为_，树的度为_。9 ，3 ，32若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有_个指针域，其中有_个指针域是存放了地址，有_个指针是空指针。2n ，n-1 ， n+13. 中序遍历二叉排序树所得到的序列是_序列（

25、填有序或无序） 。有序4设某棵二叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 N1，则该二叉树中度数为 2 的结点数为_；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_个空指针域。N 0-1，2N 0+N15设一棵完全二叉树中有 500 个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指针域。9，5016设哈夫曼树中共有 n 个结点，则该哈夫曼树中有_个度数为 1 的结点。07_遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序） 。中序8设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从 1 开始顺序编号

26、，则第 i 个结点的双亲结点编号为_，右孩子结点的编号为_。i/2，2i+19深度为 k 的完全二叉树中最少有_个结点。2 k-110设哈夫曼树中共有 99 个结点，则该树中有_个叶子结点；若采用二叉链表作为存储结构，则该树中有_个空指针域。50，5111设前序遍历某二叉树的序列为 ABCD，中序遍历该二叉树的序列为 BADC，则后序遍历该二叉树的序列为_。BDCA12设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF，则该二叉树的前序遍历序列为_，中序遍历序列为_，后序遍历序列为_。ABDECF，DBEAFC，DEBFCA13设一棵完全二叉树有 128 个结点，则该完全二叉树的深度

27、为_，有8_个叶子结点。8，64141516设一棵 m 叉树脂的结点数为 n，用多重链表表示其存储结构，则该树中有_个空指针域。n(m-1)+117下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedef struct nodeint data;struct node *lchild;_;bitree;void createbitree(bitree *if(ch=#) _;elsebt=(bitree*)malloc(sizeof(bitree);bt-data=ch; _;createbitree(bt-rchild); struct node *rchild，bt=

28、0，createbitree(bt-lchild)18设某棵完全二叉树中有 100 个结点，则该二叉树中有_个叶子结点。5019设一棵二叉树的中序遍历序列为 BDCA，后序遍历序列为 DBAC，则这棵二叉树的前序序列为_。CBDA20设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_。621设某棵二叉树的中序遍历序列为 ABCD，后序遍历序列为 BADC，则其前序遍历序列为_。CABD22完全二叉树中第 5 层上最少有_个结点，最多有_个结点。1，1623设一棵三叉树中有 50 个

29、度数为 0 的结点，21 个度数为 2 的结点，则该二叉树中度数为 3 的结点数有_个。1424高度为 h 的完全二叉树中最少有_个结点，最多有_个结点。2h-1，2 h-125设一棵二叉树的前序序列为 ABC，则有_种不同的二叉树可以得到这种序列。526设二叉树中度数为 0 的结点数为 50，度数为 1 的结点数为 30，则该二叉树中总共有_个结点数。12927设二叉树中结点的两个指针域分别为 lchild 和 rchild，则判断指针变量p 所指向的结点为叶子结点的条件是_。p-lchild=054后序序列和中序序列相同的二叉树为 没有右子树的二叉树 、后序序列和前序序列相同的二叉树为 只

30、有根的二叉树; 。55如果指针 p 指向一棵二叉树的一个结点，则判断 p 没有左孩子的逻辑表达式为 。P-lchild=NULL；56. 设一颗完全二叉树共有 50 个叶子结点，则它共有_个度为 2 的结点。4957. 二叉树采用_序遍历可以得到结点的有序序列。中58. 在一棵二叉树上第 5 层的结点数最多为 。1659. 总共三层的完全二叉树，其结点数至少有 个，至多有 个。4 、 7 60. 二叉树的遍历方法有 、 、 、 。先序 、 中序 、 后序 、 层次 61. 二叉树的存储结构有 、 、 结构表示。顺序存储 、 二叉链表存储 、 三叉链表存储 62. 一棵哈夫曼树有 5 个叶子结点组成，该哈夫曼树总共有 个结点。9 63. 对于一棵具有 n 个结点的树，该树中所有结点的度数之和为_。n-164. 假定一棵三叉树的结点个数为 50，则它的最小深度为_，最大深度为_。5 、 5065. 在一棵三叉树中，度为 3 的结点数有 2 个，度为 2 的结点数有 1 个，度为1 的结点数为 2 个，那么度为 0 的结点数有_个。666一棵深度为 5 的满二叉树中的结点数为_个，一棵深度为 3 的满三叉树中的结点数为_个。31、21