资源描述：
《数据结构习题6~12(含答桉)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、数据结构练习题第六章练习选择题1.设树T的度为4,其中度为1，2,3和4的结点个数分别为4,2,1，1则T中的叶子数为（D）A.5B.6C.7D.82.设森林F对应的二叉树为B,它有m个结点，B的根为p，p的右了树结点个数为n，森林F中第一棵树的结点个数是（A）A.m~nB.m-n-1C.n+1D.条件不足，无法确定3.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A.9B.11C.15D.不确定4.具有10个叶结点的二叉树中有（B）个度为2的结点，八.8B.9C.10D.115.一棵完全二叉树上有1001
2、个结点，其中叶子结点的个数是（E）A.250B.500C.254D.505E.以上答案都不对6.有n个叶子的哈夫曼树的结点总数为（D）。A.不确定B.2nC.2n+lD.2n-l7.一棵具有n个结点的完全二叉树的树高度（深度）是（八）A.LlognJ+1B.logn+1C.LlognJD.logn-18.深度为h的满m叉树的第k层有（A）个结点。（l=〈k=〈h）A.mk_,B.mk-lC.m1,_1D.m-l9.在一棵高度为k的满二叉树中，结点总数为（C）A.2k_1B.2kC.2k-lD.Llog2kJ+l10.对二叉树的结点从1开始进
3、行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子屮，其左孩子的编号小于其右孩子的编号，可采用（C）次序的遍历实现编号。A.先序B.中序C.后序D.从根开始按展次遍历11.树的后根遍历序列等同丁•该树对应的二叉树的（B）.A.先序序列B.中序序列C.后序序列12.已知某二叉树的后序遍历序列是dabec,屮序遍历序列是dcbac,它的前序遍历是（D）。A.acbedB.decabC.deabcD.cedba13.二叉树的先序遍历和中序遍历如下：先序遍历：EFHTGJK；中序遍历：HHEJKG。该二叉树根的右子树的根是.•
4、CA、EB、FC、GD、H14.对于前序遍历与屮序遍历结果相同的二叉树为（F）;对于前序遍历和后序遍历结果相同的二叉树为（B）。A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左子数的二叉树F.所有结点只有右子树的二叉树15.—棵非空的二义树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树16.引入二叉线索树的口的是（A）A.加快查找结点的前驱或后继的速度B.为了能在二叉树屮方便的进行
5、插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一1.n个结点的线索二叉树上含有的线索数为（C）A.2nB.n—1C.n+1D.n2.（C）的遍历仍需要栈的支持.A.前序线索树B.屮序线索树C.后序线索树3.二叉树在线索仍不能食效求解的问题是（D）。八.前（先）序线索二叉树中求前（先）序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继4.由3个结点可以构造出多少种不同的二叉树？（D）A.2B.3C.4D.55.下述编码中哪一个不是前缀码（B）。A.（00,01,10,11）B.（0,1
6、,00,11）C.（0,10,110,111）D.（1,01,000,001）6.从下列有关树的叙述屮，选出5条正确的叙述（共5分）（CDFHI）A.二叉树屮每个结点有两个子结点,而树无此限制，因此二叉树是树的特殊情况。B.当K彡1时高度为K的二叉树至多有2kH个结点。C.用树的前序周游和中序周游可以导出树的后序周游。D.线索二叉树的优点是便于在中序下查找前驱结点和后继结点。E.将一棵树转换成二叉树后,根结点没有左子树。E.一棵含有N个结点的完全二叉树,它的高度是LL0G2N」+l。G.在二叉树中插入结点,该二叉树便不再是二叉树。H.釆用二
7、叉树链表作树的存储结构，树的前序周游和其相应的二叉树的前序周游的结果是一样的。I.哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。J.用一维数组存储二叉树吋，总是以前序周游存储结点。判断题1.完全二叉树中，若一个结点没有左孩子，则它必是树叶。V2.二叉树只能用二叉链表表示。X3.在二叉树的第i层上至少有2：1个结点（i〉=l）X4.度为二的树就是二叉树。X5.在中序线索二叉树中，每一非空的线索均指向其祖先结点。V填空题：1.如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为692.具有256个结点的完全二
8、叉树的深度为jo3.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有12个叶子结点。4.在一棵二叉树屮，度为零的结点的个数为N。，度为2的结点的
