第6章 树和二叉树(相关试题)数据结构

《数据结构》（C语言版）

第6章树和二叉树

计算机与信息工程学院于江德1树形结构树树的定义基本术语ADT定义树的遍历：先序遍历后序遍历层序遍历二叉树双亲表示法孩子表示法相互转换存储结构逻辑结构存储结构逻辑结构孩子兄弟表示法二叉树的定义二叉树的性质特殊二叉树二叉树的性质二叉树的四种遍历方法满二叉树完全二叉树二叉链表顺序存储线索链表三叉链表遍历算法实现基于遍历的其他算法2二叉树的遍历1.

一棵二叉树的先序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（

）A.CBEFDA B.FEDCBAC.CBEDFA D.不确定3二叉树的遍历2.

某二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（）。A．acbedB．decab

C．deabcD．cedba

4二叉树的遍历3.

对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历5二叉树的遍历4.

二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是()A．EB．FC．G

D．H6二叉树的遍历5.

某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子7二叉树的遍历5’.

某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树8二叉树的遍历6.

设n，m为一棵二叉树的两个结点，在中序遍历时，n在m前的条件是（）A.n在m的右方 B.n是m的祖先C.n在m的左方 D.n是m的子孙97.具有10个叶子结点的二叉树中有（ ）个度为2的结点。A.8 B.9 C.10 D.11108.树中所有结点的度的和等于所有结点数加（

）。A．0 B．1C．－1 D．2119.在线索化二叉树中，t所指结点没有左子树的充要条件是（ ）A．t->left=NULLB.t->ltag=1C.t->ltag=1且t->left=NULLD.以上都不对1210.

由权值为9、2、5、7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为（）A．23B.37C.44D.461311．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）A．4B．5C．6D．71412．一个具有1025个结点的二叉树的高h为（）.A．11B．10C．11至1025之间D．10至1024之间1513.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．N1B．N1+N2C．N3D．N2+N31614.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．81715.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定1816.

若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定1917.一棵完全二叉树上有1000个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对20问:设一棵完全二叉树具有1000个结点，则它有

个叶子结点，有

个度为2的结点，有

个结点只有非空左子树，有

个结点只有非空右子树。48948810由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现只有非空右子树的结点(0个)。答：易求出总层数和末层叶子数。总层数k=log2n＋1=10;且前9层总结点数为29-1=511

(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。21请注意叶子结点总数≠末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。分析：k层的489个叶子的父结点占上层的245个结点（489/2)上层（k=9)右边的0度结点数还有29-1-245=11个！另一法：可先求2度结点数,再由此得到叶子总数。首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉）另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2，（共有489/2＝244个）。所以，全部2度结点数为255(k-2层)＋244(k-1层)=499个；总叶子数＝2度结点数＋1=500个。第i层上的满结点数为2i-1所以，全部叶子数＝489(末层)＋11(k-1层)=500个。度为2的结点＝叶子总数－1=499个。2218．设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-118‘．有n个叶子的哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-12319.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为22420.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+12521.一棵树高为K的完全二叉树至少有（）个结点A．2k–1B.2k-1–1C.2k-1D.2k

2622.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历2723.树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列2824.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用()遍历方法最合适。A．前序B．中序C．后序D．按层次2925.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同3026.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点3127.引入二叉线索树的目的是（）A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一3228.n个结点的线索二叉树上含有的线索数为（）A．2nB．n－lC．n＋lD．n3329.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。A．n-1B．nC．n+1D．n+23430.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)