鱼C论坛

 找回密码
 立即注册
查看: 3767|回复: 4

请教两个数据结构的问题。求大神 给出答案和解释~ 同时也希望能找到一起学习的伙伴~

[复制链接]
发表于 2012-10-4 10:28:06 | 显示全部楼层 |阅读模式
1鱼币
1.一棵BST存放的数据分别为A B C D E F G ,以下()不是查找序列。
A . A B C D E F G     B. G F E D
C. D B C F   D.  D G E F
2.100个结点的AVL树最高为()层。(根是第一层)
A.9 B 10
C.11 D.12

最佳答案

查看完整内容

补充: 第一题:因为C选项中的查找DBCF ,即D为根,然后到B为D的左子树的根,然后再到B的右子树C,而F为比D大不可能出现在D的左子树(即B为根的左子树)中 第二题:设AVL树的最高层为N,则N-2层必定为满的,那么由2^(10-2)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-10-4 10:28:07 | 显示全部楼层
补充:
第一题:因为C选项中的查找DBCF  ,即D为根,然后到B为D的左子树的根,然后再到B的右子树C,而F为比D大不可能出现在D的左子树(即B为根的左子树)中

第二题:设AVL树的最高层为N,则N-2层必定为满的,那么由2^(10-2)<100<2^(10-2+1)(即2的(10-2+1)次方);得出N为10,故选B
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2012-10-5 22:13:01 | 显示全部楼层
个人觉得第一题选:C  ,第二题选:B
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2012-10-6 20:40:20 | 显示全部楼层

第二个题书上的答案是A。 我百度了一下是这么说的  当节点数为N 时,高度h 最多为logN + 2。 但是原因我现在还是没完全明白。 大神可以留下QQ方便交流吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2012-10-7 12:55:11 | 显示全部楼层
He2toN 发表于 2012-10-6 20:40
第二个题书上的答案是A。 我百度了一下是这么说的  当节点数为N 时,高度h 最多为logN + 2。 但是原因我现 ...

我写的那个答案是当时二逼了一下,所以算错了,不过方法没错: 我当时写的是2^(10-2)(即2的8次方)<100<2^(10-2+1)(即2的9次方),应该是2^(8-2)==64<100<2^(8-2+1)==128,所以呢,h==8,这个是从根从第0层开始算起的,而你的根是从第1层算起的所以你的是9层呗,QQ群:55439369

补充内容 (2012-10-7 12:58):
维基百科的解析你看看吧:http://zh.wikipedia.org/wiki/AVL%E6%A0%91
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:05

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表