北京开放大学数据结构3-3 阶段性测试三

试题 1
从二叉搜索树中查找一个元素时，其时间复杂度大致为(  C  )。
选择一项：

A.
O

B.
O(1)

C.
O(log2n)

D.
O(n2)
试题 2
在一棵具有n个结点的二叉树的第i层上，最多具有( C   )个结点。
选择一项：

A.
2i

B.
2i+1

C.
2i-1

D.
2n
试题 3
20.下面叙述中，正确的是（ C）。
选择一项：

A.
若有一个结点是二叉树中某个子树的中根遍历结果序列的最后一个结点，则它 一定是该子树的先根遍历序列中的最后一个结点

B.
若有一个结点是二叉树中某个子树的先根遍历结果序列的最后一个结点，则它 一定是该子树的中根遍历序列中的最后一个结点

C.
若有一个叶结点是二叉树中某个子树的中根遍历结果序列的最后一个结点，则 它一定是该子树的先根遍历序列中的最后一个结点

D.
若有一个叶结点是二叉树中某个子树的先根遍历结果序列的最后一个结点，则 它一定是该子树的中根遍历序列中的最后一个结点

试题 4
在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为(  D  )。
选择一项：

A.
(n+1)/2

B.
(n-1)/2

C.
n/2-1

D.
n/2
试题 5
在一棵完全二叉树中，对于编号为i(i>1)的结点，其双亲结点的编号为(  D  )。
选择一项：

A.
(i+1)/2

B.
(i-1)/2

C.
i/2

D.
i/2
试题 6
在有n个叶结点的哈夫曼树中，非叶结点的总数为（  A ）。
选择一项：

A.
n -1

B.
n

C.
2n —1

D.
2n
试题 7
一棵二叉树的广义表表示为a(b(c),d(e(,g),f))，则该二叉树的高度为(   C )。
选择一项：

A.
3

B.
4

C.
5

D.
6
试题 8
17.若一棵二叉树的先根遍历序列与后根遍历序列正好相反，则这棵二叉树一定是（  C   ）的二叉树。
选择一项：

A.
空

B.
每一个结点无左子树

C.
高度和结点个数相等

D.
只有一个结点
试题 9
13.一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足:(  A   )
选择一项：

A.
所有结点无左孩子

B.
所有结点无右孩子

C.
只有一个根结点

D.
任意一棵二叉树
试题 10
3.对于度为5、高度为h的树，下列观点正确的是( A )。
选择一项：

A.
至少有h + 4个结点

B.
至多有5h-1个结点

C.
至多有5h个结点

D.
至少有h + 5个结点