数据结构 | 【查找】例题

1、由n个数据元素组成的两个表：一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任一元素的概率是相同的，则在两种表中成功查找（）.
A.平均时间后者小      B.平均时间两者相同
C.平均时间前者小      D.无法确定

【答案】B
【解析】对于顺序查找，不管线性表是有序的还是无序的，成功查找第一个元素的比较次数为1，成功查找第二个元素的比较次数为2，以此类推，即每个元素查找成功的比较次数只与其位置有关（与是否有序无关），因此查找成功的平均时间两者相同。

2、已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找法查找一个中不存在的元素，则比较的次数至少是（），至多是（）。
A.4       B.5
C.6       D.7

【答案】B
【解析】折半查找法在查找不成功时和给定值进行关键字的比较次数最多为树的高度，即 ⌈log2​(n+1)⌉或 ⌊log2n⌋ + 1，直接用公式求出最小的分支高度和最大分支高度。

即最多五次，又因为判定树不是一棵满树，则至少为4（由判定树的各分支高度最多相差1得出）。在折半查找判定树中的方形结点是虚构的，它并不计入比较的次数中。

注意，若是求查找成功或查找失败的平均查找长度，则需要画出判定树进行求解。此外，对长度为 n 的有序表，采用折半查找时，查找成功和查找失败的最多比较次数相同，均为⌈log2​(n+1)⌉，最少比较次数也相同。

 

3、下列选项中，不能构成折半查找中关键字比较序列的是？

A.500,200,450,180          B.500,450,200,180
C.180,500,200,450          D.180,200,500,450

【答案】A

【解析】折半查找的关键字序列既可以是数组（顺序存储），也可以是链表（链式存储）。

B选项：一个有序的序列，用数组表示就可以构成折半查找的关键字序列。

C选项：用数组表示不是有序的，但是可以构成一科BST树，按前序遍历可以得到选项中的序列，

                      180

                             \

                            500

                          /

                      200

                           \

                           450

D选项：同C，也可以构成一棵BST树，

                        180

                             \

                             200

                                   \

                                  500

                                /

                            450

A选项：既不是有序的，也没法构成一棵BST树，所以选A

4、具有12个关键字的有序表，折半查找的平均查找长度为( )。
A.3.1
B.4
C.2.5
D.5 

【答案】A

【解析】

法一：

将12个数画成完全二叉树，第一层有1个、第二次2个、第三层4个，第四层只有5个。

二分查找时：

第一层需要比较1次

第二两个数，每个比较2次

第三层四个数，每个比较3次

第四层五个数，每个比较4次

则平均查找长度即为：（1+2*2+3*4+4*5）/12 = 37/12 = 3.0833 即为 A、3.1

法二：

因为，我们每次都是对半分的，所以形成的树具有如下特点：

除去最后一层，是一颗满二叉树。

所以，做这个题就不需要画出树，只要列几个数就行。

第一层有1个、第二层有2个、第三层有4个，按照满二叉树的规律。

最后一层有5个，因为节点总数不能超12个。

 平均查找长度：

5、下列二叉树中，可能成为折半查找判定树（不含外部结点）的是（）

 

【答案】A

【解析】

法一：

折半查找判定树实际上是一棵二又排序树，它的中序序列是一个有序序列。

可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。

B选项4、5相加除二向上取整，7、8相加除二向下取整，矛盾。

C选项，3、4相加除二向上取整，6、7相加除二向下取整矛盾。

D选项，1、10相加除二向下取整，6、7相加除二向上取整，矛盾。

A符合折半查找规则，正确。

法二：秒杀

二叉查找判定树若结点数相同，那么其结构应该相同。

若结点为奇数，如果采用向下取整，那么结点个数将一直是左少右多，然后子树也一定是左少右多。

1234  5  678910

若结点为奇数，如果采用向上取整，那么结点个数将一直是左多右少，然后子树也一定是左多右少。

12345  6  78910

若结点为偶数，那么结点个数两棵子树将相同，那么结构也该一样。

1234  5  6789

故 B、C错误，应该和左边子树相同结构。

故D错误，应该左右子树一直都是左少右多或左多右少。