数据结构基础--查找

2-1已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素,则关键字的比较次数最多是

我们知道折半查找就相当于是建立了一个二叉树,然后去搜索相应的叶子,那么查询的次数最多就应该是树的

高度,也就是log~2~n+1,答案就是5了

2-2用二分查找从100个有序整数中查找某数,最坏情况下需要比较的次数是

和上个题一样,其实就是log~2~n+1,注意这里的log~2~n要向下取整也就是6

2-3在有n(n>1000)个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示:

1
2
3
4
5
6
k = 0
while ( k<n 且 A[k]<x ) k = k+3;
if ( k<n 且 A[k]==x ) 查找成功;
else if ( k-1<n 且 A[k-1]==x ) 查找成功;
else if ( k-2<n 且 A[k-2]==x ) 查找成功;
else 查找失败;

看算法,就是个简单的顺序查找,只不过是3个一组罢了。想象你要找的元素是第二个,因为折半查找先找中间,而你顺序查找的话一下子就找到了。所以答案很明显应该是前几个元素。

2-4下列二叉树中,可能成为折半查找判定树(不含外部结点)的是:

折半查找二叉树要注意,他的中序遍历是一个有序序列(升序的),但是折半就有个问题了,你是向上取整呢,还是向下取整呢?一般我们都是向下取整的,但其实这两种情况都可以,不过两种情况的二叉树在当顶点数是偶数时就会出现左右分配不均匀的情况,就会存在差异。

  • 当向上取整时,左多右少
  • 当向下取整时,左少右多

做这种题目关键就是看他们的取整策略是否相同,这里有个小技巧,高度对称的一定不是,比如b、c。而d呢?根结点左是4,右是5,也就是向下取整,在看左子树的根结点,左2右1,是向上取整,矛盾所以错误。

2-5若二叉搜索树是有N个结点的完全二叉树,则不正确的说法是:

查找效率之前说过了就是logN,最小值一定在叶结点上也是对的,但最大却不一定在叶结点上,还有可能是中间。

2-6若一棵二叉树的后序遍历序列是{ 1, 3, 2, 6, 5, 7, 4 },中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 },则下列哪句是错的

这个就不说了,还原出来树就很简单了,怎么还原?先看后序,后序的最后一个是根结点,再看中序,中序中以根结点为mid分成两部分,左是左子树,右是右子树,重复上面的过程即可

2-10对二叉搜索树进行什么遍历可以得到从小到大的排序序列?

这个之前说那个折半查找树的时候说过了,中序(因为左一定小于中,右一定大于中)。

其余的题目都是类似的或者是重复的,就不再说了(其实是今天还要被逼更新二叉树,来不及写了),successful