数据结构树习题

第六章树习题1单项选择题1、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则叶子结点个数是（B）。A、9 B、11 C、15 D、无法确定2、设给定权值总数有n个，其哈夫曼树的结点总数为（D）。A、不确定 B、2n C、2n+1 D、2n13、有关二叉树下列说法正确的是（B）。A、二叉树的度为2 B、一棵二叉树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为24、一棵二叉树高度为h，所有结点的度或为0，或为2,则这棵二叉树最少有（）结点。A、2h B、2h-1 C、2h+1 D、h+15、对于有n个结点的二叉树，其高度为（）。A、n10g2n B、10g2n C、Log2n-D、不确定6、利用二叉链表存储树，则根结点的右指针是（）。A、指向最左孩子 B、指向最右孩子C、空 D、非空7、树的后根遍历序列等同于该树对应的二叉树的（）。A、先序遍历 B、中序遍历 C、后序遍历 D、层序遍历8、在下列存储形式中，哪一个不是树的存储形式？（）人、双亲表示法 B、孩子链表表示法C、孩子兄弟表示法 D、顺序存储表示法9、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A、CBEFDA B、FEDCBA C、CBEDFA 口、不定10、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空的或只有一个结点 B、任一结点无左子树C、高度等于其结点数 D、任一结点无右子树11、一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：（）。A、不确定 B、0 C、1 D、212、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（）。A、X的双亲 B、X的右子树中最左的结点C、X的左子树中最右结点 D、X的左子树中最右叶结点13、引入二叉线索树的目的是（）.A、加快查找结点的前驱或后继的速度8、为了能在二叉树中方便的进行插入和删除^为了能方便的找到双亲D、使二叉树的遍历结果唯一14、下述编码中哪一个不是前缀码（）。A、（00，01，10，11） B、（0，1，00，11）C、（0，10，110，111） D、（1，01，000，001）TOC\o"1-5"\h\z15、按照二叉树的定义，具有3个结点的二叉树有（ ）种。A、6 B、5 C、4 D、316、在具有n个结点的二叉链表中，空指针域的个数为（ ）。A、2n-1 B、2n+1 C、n-1 D、n+117、深度为4的二叉树至多有（ ）个结点。A、17 B、18 C、15 D、1318、树最适合用来表示（ ）。A、有序数据元素 B、无序数据元素C、元素之间具有层次关系的数据D、元素之间无联系的数据19、一棵具有n个结点的树，所有结点的度之和为（ ）。A、n B、n-1 C、n+1 D、无法确定20、一棵完全二叉树上有1001个结点，其中叶子结点个数是（ ）。A、250B、501C、254D、50521、先序序列和后序序列正好相反的二叉树是（ ）。A、二叉排序树 B、平衡二叉树 C、左斜树D、以上都不对22、在任何一棵二叉树中，如果结点q的左孩子为b，右孩子为c，则在结点的先序遍历、中序遍历和后序遍历中（）。A、结点b一定在结点a的前面B、结点a一定在结点c的前面

C、结点b一定在结点c的前面 D、结点a一定在结点b的前面TOC\o"1-5"\h\z23、下面哪个选项可以唯一地确定一棵二叉树。（ ）A、先序序列 B、中序序列C、中序后序序列 D、先序和后序序列24、判断线索二叉树上指针p所指结点有右孩子的条件是（ ）。A、p!=NULL B、p->rchild!=NULL C、p->rtag==0 D、p->rtag==125、设一棵哈夫曼树共有35个结点，则该哈夫曼树共有（ ）个叶子。A、18 B、35 C、20 D、3026、对应哈夫曼树，下面说法错误的是（ ）。A、哈夫曼树一定是完全二叉树B、哈夫曼树中没有度为1的结点C、树中两个权值最小的结点一定是兄弟结点D、树中任一非叶子结点的权值一定不小于下一层任一结点的权值2填空题TOC\o"1-5"\h\z1、已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则其后序序列为（ ）。2、在n个结点的线索二叉链表中，有（ ）个线索指针。3、若一棵满三叉树中含有121个结点，则该树深度为（ ）。4、在有n个叶子结点的哈夫曼树中，总结点数是（ ）。5、树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中该结点一定（ ）。6、在一棵高度为h的三叉树中，最多含有（ ）个结点。7、判断线索二叉树中某结点指针p所指结点有左孩子的条件是（ ）。8、在有n个结点的哈夫曼树中，度为1的结点数是（ ）。9、深度为n的二叉树最少有（ ）个结点，最多有（）个结点。10、若对一棵具有n个结点的二叉树，采用二叉链表存储时，其指针总数为（ ），其中（ ）个用于指向孩子，（ ）个指针是空闲的。11、若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储在一维数组A中，则：A[i]若有左孩子，其左孩子在数组中的位序号为（ ），若有右孩子，其右孩子在数组中的位序号为（），其双亲在数组中的位序号为（）。12、后缀表达式12、后缀表达式923+-102/-的值为（达式为（ ）。），中缀表达式（3+4x）-2y/2对应的后缀表13、一棵高度为3的二叉树中最少含有（ ）个结点，最多含有（ ）个结点；一棵高度为3的平衡二叉树中最少含有（）个结点，最多含有（ ）个结点。14、已知一棵完全二叉树共有768个结点，则该树共有（ ）个叶子。15、设哈夫曼树中共有99个结点，则该树有（ ）个叶子结点；若采用二叉链表作为存储结构，则该树中有（ ）个空指针。16、一棵深度为6的满二叉树有（ ）个分支结点和（）个叶子。3问答题1、给出图6-7所示的二叉树的先根、中根和后根遍历序列。AEBCFD图AEBCFD图6-72、设二叉树BT的存储结构如下:12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000其中BT为树根结点的指针，其值为6,Lchild和Rchild分别为结点的左右孩子指针域，data为结点的数据域。完成下列各题：（1）画出二叉树BT的逻辑结构；（2）写出按前序、中序和后序遍历该二叉树所得到的结点序列；（3）画出二叉树的后序线索树。3、已知一棵完全二叉树的第6层有8个叶子结点，求该完全二叉树有多少个结点？4、若二叉树采用顺序存储结构表示，则编号为i和j的两个结点处于同一层的条件是什么？5、已知高度为8的完全二叉树的第8层有8个结点，则叶子结点有多少个？6、若某非空二叉树，分别写出满足下列条件的二叉树是什么形态的二叉树？（1）先序序列和中序序列正好相反；(2)先序序列和中序序列正好相同；(3)中序序列和后序序列正好相同；(4)中序序列和后序序列正好相反。7、一棵满k叉树上的叶子结点数。和非叶子结点数b之间满足下面的关系式:a=(k-1)b+1,请给出推导证明过程。8、一棵树有3度结点100个，2度结点200个，该树有多少个叶子结点？有多少个度为1的结点？9、已知树如图6-8所示：(1)写出该树的后序序列；(2)画出由该树转换得到的二叉树。10、假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别是0.10、0.07、0.16、0.05、0.19、0.23、0.12、0.08,试为这8个字母设计哈夫曼编码。4算法填空题下面函数的功能是返回二叉树BT中值为e的结点所在的层号，请在画有横线的地方填写适当的内容完成该功能。intNode_Level(BinTreeNode*BT,ElemTypee)(if(!BT)return0; 〃空树层号为0elseif()return1; 〃根结点层号为1else(int