数据结构第二单元练习题解答.doc

数据结构第二单元练习题答案 一、选择 1.树最适合用来表示( ) A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 2.在下述结论中，正确的是( ) ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④ 3.以下说法正确的是( ) A.任何一棵二叉树中至少有一个结点的度为2 B.任何一棵二叉树中每个结点的度都为2 C.任何一棵二叉树的度肯定等于2 D.任何一棵二叉树的度可以小于2 4.在下列情况中，可称为二叉树的是( ) A.每个结点至多有两棵子树的树 B.哈夫曼树 C.每个结点至多有两棵子树的有序树 D.每个结点只有一棵右子树 E.以上答案都不对 5.深度为h的满m叉树的第k层有( )个结点(1=k=h) A.mk-1 B.mk-1 C.mh-1 D.mh-1 6.在一棵高度为k的满二叉树中，结点总数为( ) A.2k-1 B.2k C.2k-1 D.?log2k?+1 7.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个 A.4 B.5 C.6 D.7 8.具有10个叶结点的二叉树中有( )个度为2的结点。 A.8 B.9 C.10 D.ll 9.二叉树有n个结点，则其深度为（ ） A.n-1 B.n C.(log2n)+`1 D.无法确定 该题是二叉树不是完全二叉树 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 10.一个具有1025个结点的二叉树的高h为( ) A.11 B．10 C.11至1025之间 D.10至1024之间 11.一棵具有 n个结点的完全二叉树的深度是( ) A.?log2n?+1 B.log2n+1 C.?log2n? D.log2n-1 12.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度( ) A.4 B.5 C.6 D.7 13.将一棵有100个结点的完全二叉树从根结点这一层开始，每一层上从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ） A.98 B.99 C.50 D.48 利用二叉树的性质5 14.在完全二叉树中，若一个结点是叶结点，则它没( ) A.左子结点 B.右子结点　 C.左子结点和右子结点 D.左子结点，右子结点和兄弟结点 15.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为( ) A.A[2i](2i=n) B.A[2i+1](2i+1=n) C.A[i/2] D.无法确定 16.在下列存储形式中，( )不是树的存储形式？ A.双亲表示法 B.孩子链表表示法 C.孩子兄弟表示法 D.顺序存储表示法 17.以下说法错误的是( ) A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.三叉链表，二叉树求双亲运算很容易实现 C．在二叉链表上，求左.右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好 18.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现编号。 A.先序遍历 B.中序遍历 C.后序遍历 D.从根开始的层次遍历 19.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，… ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( )编号的。 A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序 20.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( ) A.所有的结点均无左孩子 B.所有的结点均无右孩子 C.只有一个