题7

题7

题目

【2013 统考真题】设包含 个数据元素的集合 ，各元素的查找概率依次为： 。将 保存在一个长度为 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 。请回答：

1. 若采用顺序存储结构保存 ，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
2. 若采用链式存储结构保存 ，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

分析

注意这里第二问的答案2可以不掌握，严格上说应该算是超纲内容，这里两个方式都是顺序查找，按照概率降序排列即可。

解

1. 折半查找要求元素有序顺序存储, 字符串默认按字典序排序 (字典序是一种比较两个字符串大小的方法, 它按字母顺序从左到右逐个比较对应的字符, 若某一位可比较出大小, 则不再继续比较后面的字符, 如 abd<acd、abc<abcd 等), 对本题来说 do<for< repeat<while。若各个元素的查找概率不同, 折半查找的性能不一定优于顺序查找。 采用顺序查找时, 元素按其查找概率的降序排列时查找长度最小。

采用顺序存储结构, 数据元素按其查找概率降序排列。采用顺序查找方法。

查找成功时的平均查找长度 。

此时, 显然查找长度比折半查找的更短。

2. 答案 1: 采用链式存储结构时, 只能采用顺序查找, 其性能和顺序表一样, 类似于上题。 数据元素按其查找概率降序排列, 构成单链表。采用顺序查找方法。

查找成功时的平均查找长度 。

---

答案 2: 还可以构造成二叉排序树的形式。采用二叉链表的存储结构, 构造二叉排序树, 元素的存储方式见下图。采用二叉排序树的查找方法。

查找成功时的平均查找长度 。