返回主页
已有4条笔记
[数据结构 P2063] 已知一个长度为 16 的顺序表 L ，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在
未通过
已知一个长度为 16 的顺序表 L ，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多是（ ）。
A. 4
B. 5
C. 6
D. 7
上面问题的答案是：
加入错题本
个人笔记
方法一：二叉搜索树
可以画出...
用户登录可进行刷题及查看答案
方法一：二叉搜索树
可以画出对应的二叉搜索树。
明显走到最深的下标为 32 或 33 的失败结点，路径长度为 5 ，需要和下标为 1,2,4,8,16 的结点进行比较。
本题选B。
方法二：公式法
若采用折半查找法查找一个顺序表中不存在的元素，最大比较次数为对应二叉搜索树的高度，设结点数为 n ，
二叉搜索树高度为
代入 n=16 ，解得 h=5 。
本题选B。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案