单选题
17.
在含有12个结点的平衡二叉树上，查找关键字为35(存在该结点)的结点，则依次比较的关键字有可能是( )。
A、
46，36，18，20，28，35
B、
47，37，18，27，36
C、
27，48，39，43，37
D、
15，45，55，35
【正确答案】
D
【答案解析】
设Nn表示深度为h的平衡二叉树中含有的最少结点数，有：N
0
=0N
1
=1N
h
=N
h-1
+N
h-2
+1当结点数为12时，N
h
=12，h=5，即12个结点的平衡二叉树而最小叶子结点的层数为3，最大叶子结点的层数为5，由于存在关键字为35的结点，即最多比较5次一定能找到该结点。故排除A、B、C，选D。
提交答案
关闭