数据结构期末复习 第八章查找一、选择题1.顺序查找方法适合于存储结构为D的线性表。A散列存储 B索引存储C散列存储或索引存储 D顺序存储或链接存储2在有序表{138133342466376788697100}中用折半查找值86时经B次比较后查找成功。A3 B4 C6 D83对二叉排序树进行C遍历可以使遍历所得到的序列是有序序列。A按层次 B后序 C中序 D前序4有一个长度为12的有序表按折半查找对该表进行查找在等概率情况下查找成功的平均比较次数为A。A37/12 B39/12 C41/12 D35/125已知一个有序表为{11,22,33,44,55,66,77,88,99}则顺序查找元素55需要比较C次。A3 B4 C5 D66.顺序查找法与折半查找法对存储结构的要求是D。A顺序查找与折半查找均只适用于顺序表B顺序查找与折半查找均既适用于顺序表也适用于链表C顺序查找只是适用于顺序表D折半查找适用于顺序表7有数据{53,30,37,12,45,24,96}从空二叉树开始逐个插入数据来形成二叉排序树若希望高度最小应该选择的序列是B。A45,24,53,12,37,96,30 B37,24,12,30,53,45,96C12,24,30,37,45,53,96 D30,24,12,37,45,96,538.采用顺序查找方法查找长度为n的线性表时每个元素的平均查找长度为C。An Bn/2C(n1)/2 D(n-1)/29.对于一个线性表若要求既能进行较快地插入和删除又要求存储结构能够反映数据元素之间的逻辑关系则应该B。A以顺序存储方式 B以链接存储方式C以索引存储方式 D以散列存储方式10.哈希函数有一个共同的性质即函数值应当以D取其值域的每个值。A最大概率 B最小概率C平均概率 D同等概率解析哈希函数的一个重要性质是对于不同的输入其输出应尽可能均匀分布在值域中即每个输出值被选中的概率应大致相等。平均概率是个综合性的计算不是对具体某个输出值的控制。且平均概率的表象下有极小概率和极大概率共存的不均匀状态11.在最坏情况下折半查找与二叉排序树查找性能比较BA. 完全相同 B.折半查找性能好C. 二叉排序树查找性能好 D.不能确定解析折半查找对有序顺序表最坏情况下需要比较⌊log2n⌋1次时间复杂度为O(logn)且是严格稳定的对数级别。二叉排序树查找最坏情况发生在树退化成单支即插入序列有序或逆序时此时树高为n查找退化为顺序查找最坏时间复杂度为O(n)。因此在最坏情况下折半查找的性能远优于二叉排序树查找。12.设哈希表长m14哈希函数H(key)key mod 11。表中已有4个结点addr(15)4; addr(38)5; addr(61)6; addr(84)7。如用线性探测处理冲突关键字为49的结点的地址是A。A.8 B.3 C.5 D.9解析哈希表长m14地址范围0~13。哈希函数H(key)key mod 11已有结点H(15)15 mod114地址4H(38)38 mod 115地址5H(61)61 mod 116地址6H(84)84 mod 117地址7插入49计算H(49)49 mod 115地址5已被38占用→冲突线性探测(51) mod146 →地址6已被61占用继续(61) mod 147 →地址7已被84占用继续(71) mod 148 →地址8空闲所以49存放在地址8。13.采用折半查找方法查找长度为n的线性表时每个元素的平均查找长度为D。An2 B.nlog2n C.n D.log2n14.哈希表的平均查找长度AA与处理冲突的方法有关与表的长度无关B与处理冲突的方法无关与表的长度有关C与处理冲突的方法有关与表的长度有关D与处理冲突的方法无关与表的长度无关解析按严格哈希表理论应选C与冲突方法和装填因子有关而装填因子包含表长。按常见应试答案尤其部分教材选A。解释哈希表的平均查找长度ASL受多个因素影响与处理冲突的方法有关不同冲突解决方法如线性探测、二次探测、链地址法等对查找长度影响很大。例如线性探测容易产生“聚集”平均查找长度通常比链地址法要大。与表的长度有关更准确地说与装填因子αn/mαn/m有关表长mm固定时表中已存元素个数nn越大即装填因子越大冲突越可能发生平均查找长度越大。反之表越长mm越大而nn固定时装填因子越小平均查找长度越小。因此“与表的长度有关”在通常意义上可以理解为与装填因子有关而装填因子包含表长mm这个因素。综上平均查找长度既与冲突处理方法有关也与表的长度通过装填因子有关。故选择C。15.一组记录的关键字是{19,14,23,1,68,20,84,27,55,11,10,79}用链接地址法构造散列表散列函数为H(key)key mod 13,散列地址为1的链中有D个记录。A.1 B.2 C.3 D.4解析19mod13614mod 131←地址123mod 13101mod 131←地址168mod 1368−65320mod 13784mod 1384−78627mod 131←地址155mod 1355−52311mod 131110mod 131079mod 1379−781←地址1散列地址为1的关键字有14、1、27、79一共4个。16.二叉排序树的查找效率与二叉树的C有关。A.高度 B.结点个数 C.树形 D.结点的位置解释二叉排序树的查找效率主要取决于树的形状即树形而树形又由关键字插入的顺序决定。树形直接影响树的高度。同样nn个结点平衡的树形→高度约log⁡2nlog2​n→查找效率高O(log⁡n)O(logn)退化的树形如单支树→高度nn→查找效率低O(n)O(n)A.高度高度是树形的直接结果但“与高度有关”不够本质因为高度由树形决定。不过某些题目会选高度但本题有“树形”这个更根本的选项时应选树形。B.结点个数nn一定时不同树形效率不同所以查找效率不只看结点个数。D.结点的位置这是微观描述不够准确。二、判断题1在顺序查找、折半查找、哈希表查找3种方法中平均查找长度与结点个数n无关的查找方法是折半查找。×2在一个查找表中能够唯一地确定一个记录的关键字称为主关键字。√3.顺序查找是一种最简单的查找方法。√4.折半查找的前提条件是查找表中记录相应的关键字值必须有序或者部分有序。×5.二叉排序树的建立过程上实际上是从空树逐次插入的过程。√6.理想情况下哈希表查找等概率查找成功的时间复杂度是O(1)。√7.按照一定规则在二叉排序树上插入、删除结点仍能保持二叉排序树的性质。√8.分块查找分为两个步骤第一步是要对索引表进行查找第二步是在块中查找。这两步查找都可以采用折半查找或者顺序查找方法。×9.一个好的哈希函数应该使哈希地址均匀地分布在整个哈希表的地址区间中完全避免冲突的发生。×10.在有序顺序存储的线性表中查找一个元素用折半查找速度一定比顺序查找快。×11.二叉树为二叉排序树的充分必要条件是任一个分支结点的值都大于其左孩子的值小于右孩子的值。×12.二叉排序树在呈单支二叉树时查找效率最低。√13.将10个元素散列到10000个单元的哈希表中仍然可能会产生冲突。√14.根据无序序列构造二叉排序树的过程也是对无序序列排序的过程。√15.折半查找方法运用在升序序列比降序序列效率更高所以降序序列最好先转换为升序序列。×