数据结构练习(二叉树)

《数据结构练习(二叉树)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、:据结构练习(二叉树)学号31301374姓名张一博班级软件工程1301.一、选择题1.按照二叉树定义，具有3个结点的二叉树共有C种形态。(A)3(B)4(C)5(D)62.具有五层结点的完全二叉树至少有D个结点。(A)9(B)15(C)31(D)163.以下有关二叉树的说法正确的是_B。(A)二叉树的度为2(B)—棵二叉树的度可以小于2(C)至少有一个结点的度为2(D)任一结点的度均为24.己知二叉树的后序遍历是dabec,中浮遍历是debac，则其前序遍历是_D。(A)acbed(B)dec

2、ab(C)deabc(D)cedba5.将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为_。(A)98(B)99(C)50(D)没有右孩子6.对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有D为空。(A)50(B)99(C)100(D)1017.设二叉树的深度为h,且只有度为1和0的结点，则此二叉树的结点总数为_£_。(A)2h(B)2h-1(C)h(D)h+18.对一棵满二叉树，m个树叶，n个结点，深度为h，则D。

3、(A)n=h+m(B)h+m=2n(C)m=h-1(D)n=2h-19.某二叉树的先序序列和后序序列正好相反，则下列说法错误的是_(A)二叉树不存在(B)若二叉树不为空，则二叉树的深度等于结点数(C)若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子(D)若二叉树不为空，则任一结点的度均为110.对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号,司一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用A遍历实现编号，(A)先序(B)中序(C)后序(D)层序11.一个

4、具有1025个结点的二叉树的高h为C。(A)1()(B)ll(011-1025(D)10〜102412.设n，m为一棵二叉树上的两个结点，在屮序遍历时，n在m前的条件是C。(A)n在m右方(B)n是m祖先(C)n在m左方(D)n是m子孙13.实现对任意二叉树的后序遍历的非递归算法而不使川栈结构，最佳方案是二叉树采用C存储结构。(A)二叉链表(B)广义表(C)三叉链表(D)顺序14.一棵树可转换成为与其对应的二叉树，则下面叙述正确的是_A。(A)树的先根遍历序列与其对应的二叉树的先序遍历相同(B)

5、树的后根遍历序列与其对应的二叉树的后序遍历相同(C)树的先根遍历序列与其对应的二叉树的中序遍历相同(D)以上都不对二、填空题1.对一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度:当它为单分支二叉树时，具有最大高度。1.在二叉树的第i(i彡1〉层上至多有2A(j-1)个结点,深度为k(k&1)的完全二叉树至多2八(1<)-1个结点,最少2A(k-1)个结点:2.如果二叉树的终端结点数为nQ，度为2的结点数为n2,则n0=n2+1。3.已知一棵二叉树的屮序序列是cbedahgijf,后

6、序序列是cedbhjigfa,则该二叉树的先序序列是abcdefghii,该二叉树的深度为5。4.若一棵二叉树的屮序遍历结果为ABC，则该二叉树有3屮不同的形态。6.在顺序存储的二叉树中，下标为i和j的两个结点处在同一层的条件是log(2)i=log(2)j。7.己知完全二叉树的第7层有8个结点，则其叶子结点数为36个。总结点数为71个。8.在对二叉树进行非递归屮序遍历过程屮，需要用栈来哲存所访M结点的地址:进行层序遍历过程中，需要用队列来竹存所访问结点的地址;9.高度为h，度为k的树中至少有h

7、+k-1个结点,至多有kA(h)-l个结点。10.一维数组存放完全二叉树：ABCDEFGHI,则后序遍历该二叉树的序列为H1DEBFGCA。三、应用题1.应用题：说明分别满足下列条件的二叉树各是什么？(1)先序遍历和屮序遍历相同(2)中序遍历和后序遍历相同(3)先序遍历和后序遍历相同树树树空空空，只有一个跟节点或右单分支二叉树。，只有一个根节点或左单分支二叉树。，只有一个根节点的二叉树。2.已知一棵二叉树的屮/W:列是cbedahgijf,后/•丫:/•丫:列足cedbhjigfa,画出这棵二叉

8、树的逻辑结构图。AFBGCDHIEJ先序序列中序序列后序序列3.—棵二叉树的先序、中序、后序序列如下，其中一部分未标出，试构造出该二叉树。_A_BCDE_EGHIJ.KCBEDEAHJKIG_CEFDB_KJIH_GA4.有n个结点的二叉树，己知叶子结点个数为n。，回答下列问题：(1)写出求度为1的结点的个数m的计算公式；(2)若此树是深度为k的完全二叉树，写出n为最小的公式；(1)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式;(1)nl=n+l-2n0(2)n(min)=