数据结构
相似问题和答案
第1题：
深度为n(n＞0)的二叉树最多有【 】个结点。
2n-1
第2题：
在具有n(n＞1)个结点的完全二叉树中，结点i(2i＞n)的左孩子结点是______。
A．2i
B．2i+1
C．不存在
D．2i-1
解析：完全二叉树中叶子结点一定在最后一层或两层。n个结点的完全二叉树中，其层数最多为log2n+1。结点i与双亲的关系是i≠1时，i的双亲是trunc(i/2)。结点i与子女的关系是：若2i≤n，则i的左孩子是标号2i的结点，若2i＞n，则不存在左孩子；若2i+1≤n，则i的右孩子是标号2i+1的结点，若2i+1＞n，则该结点不存在右孩子。
第3题：
下列关于完全二叉树的叙述中，错误的是( )。
A．除了最后一层外，每一层上的结点数均达到最大值
B．可能缺少若干个左右叶子结点
C．完全二叉树一般不是满二叉树
D．具有结点的完全二叉树的深度为[1og2n)+1
解析： 满二叉树指除最后一层外，每一层上所有结点都有两个子结点的二叉树。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干叶子结点的二叉树。因此选项A叙述正确，而选项B叙述错误。由定义可知，满二叉树肯定是完全二叉树，而完全二叉树一般不是满二叉树。
第4题：
具有n个结点的完全二叉树，若按自上而下、从左到右依次给结点编号，则编号最小的叶结点的序号是（ ）。A．[n/2] B．[n+1］C．［n/2］＋1 D．［n/2］－1
完全二叉树编号最小的叶节点即为最后一层的第一个节点。[n/2]为倒数第二层的最后一个节点，因此结果为[n/2]+1.
第5题：
一个深度为I(I≥1)的二叉树有n个结点，从1-n对结点自上而下，自左至右编号，这样的树( )。
A．是完全二叉树
B．是满二叉树
C．结点数最多2i1个
D．父结点编号是子结点编号的1/2
解析：这是完全二叉树的定义，应该注意满二叉树与完全二叉树的区别，满二叉树是完全二叉树，但完全二叉树却不一定为满二叉树。
第6题：
具有n个结点的完全二叉树，其深度为【 】。
log2n+1
第7题：
下面关于完全二叉树的叙述中，错误的是______。
A．除了最后一层外，每_层上的结点数均达到最大值
B．可能缺少若干个左右叶子结点
C．完全二叉树一般不是满二叉树
D．具有结点的完全二叉树的深度为[log2n]+1
解析：满二叉树指除最后一层外每一层上所有结点都有两个子结点的二叉树。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干子结点(叶子结点)的二叉树。
第8题：
在具有n个结点的二叉树中，如果各结点值互不相同，但前序遍历序列与中序遍历序列相同，则该二叉树的深度为(根结点在第1层)()。
A.n
B.n/2+1
C.n+1
D.n-1
第9题：
下面关于完全二叉树的叙述中，错误的是______。
A．除了最后—层外，每—层上的结点数均达到最大值
B．可能缺少若干个左右叶子结点
C．完全二叉树—般不是满二叉树
D．具有结点的完全二叉树的深度为[log2n]+1
解析：满二叉树指除最后一层外每一层上所有结点都有两个子结点的二叉树。完全二叉树指除最后一层外，每—层上的结点数均达到最大值，在最后—层上只缺少右边的若干子结点(叶子结点)的二叉树。
第10题：
下面关于二叉树的基本性质说明错误的是______ 。
A．在二叉树的第k层上，最多有2k(k≥1)个结点
B．深度为m的二叉树最多有2m-1(m≥1)个结点
C．深度为0的结点(即叶子结点)总是比深度为2的结点多一个
D．具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取不大于log2n的最大整数
解析：在二叉树的第k层上，最多有2k-1(k1)个结点，而不是2k(k1)个结点。