重庆移通学院：《数据结构》课程教学资源（PPT课件讲稿）树的练习

、单项选择题: 、下图中, 不是完全二叉树

一、单项选择题： 1、下图中，______不是完全二叉树。 A B C D

2、在线索二叉树中,t所指节点没有左子树的充要条件是: A t->left==null >Tag== C t->ltag==1 & t->left==null D以上都不对 3、二叉树按某种顺序线索化后,任一节点均有指向其前驱和后继的线索,这种说法 A正确 B错误 4、二叉树的前序遍历中,任意一个节点均处于其孩子节点的前面,这种说法: A正确 B错误 5、由于二叉树中每个节点的度最大为2,所以二叉树是一种特殊的树,这种说法: A正确 B错误 6、设高度为h的二叉树只有度为O和2的节点,则此类二叉树中所包含的节点数至少 为: A 2h B2h-1 C2h+1

2、在线索二叉树中，t所指节点没有左子树的充要条件是： A t->left==null B t->ltag==1 C t->ltag==1 && t->left==null D 以上都不对 3、二叉树按某种顺序线索化后，任一节点均有指向其前驱和后继的线索，这种说法： A 正确 B 错误 4、二叉树的前序遍历中，任意一个节点均处于其孩子节点的前面，这种说法： A 正确 B 错误 5、由于二叉树中每个节点的度最大为2，所以二叉树是一种特殊的树，这种说法： A 正确 B 错误 6、设高度为h的二叉树只有度为0和2的节点，则此类二叉树中所包含的节点数至少 为： A 2h B 2h-1 C 2h+1 D h+1

7、下图所示二叉树的中序遍历序列是: A arcane b dfebagc C abaefc aetbagc

7、下图所示二叉树的中序遍历序列是： A abcdgef B dfebagc C dbaefcg D defbagc a b c d e f g

8、已知某二叉树的后序遍历序列是 dabic,中序遍历序列是 debao,它的前序遍 历序列是: A ached b decab C deabc D cedba 9、已知某二叉树的前序遍历序列是 abdgcefh,中序遍历序列是 dgbaechf,它的 后序遍历序列是: a bdgcefha b gdbecfha C bdgaechf d gdbehfca 10、下图是有一个森林转化成的二叉树,那么森林有 个叶子结点。 B 5 C6 D7 a d

8、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍 历序列是： A acbed B decab C deabc D cedba 9、已知某二叉树的前序遍历序列是abdgcefh，中序遍历序列是dgbaechf，它的 后序遍历序列是： A bdgcefha B gdbecfha C bdgaechf D gdbehfca 10、下图是有一个森林转化成的二叉树，那么森林有________个叶子结点。 A 4 B 5 C 6 D 7 a b c d e f g h i j

11、设一棵完全二叉树具有1000个结点,则此完全二叉树有 个叶子结 点,有个度为2的结点,有个结点只有非空左子树,有 个结 点只有非空右子树 12、按照二叉树的定义,具有3个节点的二叉树有 种。 A 3 B 4 C 5 13、深度为5的二叉树至多有 个节点 A16B32 C31D10 14、在一非空二叉树的中序遍历序列中,根节点的右边 A只有右子树上的所有节点B只有右子树上的部分节点 C只有左子树上的部分节点D只有左子树上的所有节点 15、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序 A不发生变化B发生变化C不能确定D以上都不对 16、对于一个满二叉树,m个树叶,n个结点,深度为h,则 A n=h+m b h+m=2n Cm=h+1 Dn=2h-1

11、 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结 点，有 个度为2的结点，有 个结点只有非空左子树，有 个结 点只有非空右子树。 12、按照二叉树的定义，具有3个节点的二叉树有___________种。 A 3 B 4 C 5 D 6 13、深度为5的二叉树至多有_________个节点。 A 16 B 32 C 31 D 10 14、在一非空二叉树的中序遍历序列中，根节点的右边 A 只有右子树上的所有节点 B 只有右子树上的部分节点 C 只有左子树上的部分节点 D 只有左子树上的所有节点 15、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序 _______ A 不发生变化 B 发生变化 C 不能确定 D 以上都不对 16、对于一个满二叉树，m个树叶，n个结点，深度为h，则_____ A n=h+m B h+m=2n C m=h+1 D n=2h-1

17、根据使用频率为5个字符设计的哈夫曼编码不可能的是: A111,110,10,01,00 B000,001,010,011, C100,11,10,1,0 D001,000,01,11,10 18、一棵二叉树如图,其中序遍历的序列为: A abdacefh b dabaechf C gdbehfca D abcdefgh C

17、根据使用频率为5个字符设计的哈夫曼编码不可能的是： A 111，110，10，01，00 B 000，001，010，011，1 C 100，11，10，1，0 D 001，000，01，11，10 18、一棵二叉树如图，其中序遍历的序列为： A abdgcefh B dgbaechf C gdbehfca D abcdefgh a b d g c e h f

19、以数据集{4,5.6,7,10,12,18}为结点权值所构造的哈夫曼树为 其WPL为 20、某二叉树的节点数据采用顺序存储结构如下 123456789101112131415161718 1920 E AF 1)画出该二叉树 2)写出节点值为D的双亲结点及左右子树 3)将此二叉树还原成森林

19、以数据集{4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树为__________ 其WPL为___________ 20、某二叉树的节点数据采用顺序存储结构如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F D H C G I B 1) 画出该二叉树 2) 写出节点值为D的双亲结点及左右子树 3) 将此二叉树还原成森林

8题: 后序: dabic 中序: debao C 已 deba d(b ba return

8题: 后序:dabec 中序:debac c deba c e d ba c e d b a return

12题: bn=>bi*bn -i-1 N个结点的不相似的二叉树有 n+1 2n return

12题:  − = = − − 1 0 * 1 n i bn bi bn i N个结点的不相似的二叉树有 C n n n 2 1 1 + return

17题 0 10 ○1 0 0 ,○③

17题： 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 return