设有序表中的元素为(13,18,24,35,47,50,62),则在其中利用二分法查找值为24的元素需要经过()次
设有序表中的元素为(13,18,24,35,47,50,62),则在其中利用二分法查找值为24的元素需要经过()次比较。
A.1
B.2
C.3
D.4
设有序表中的元素为(13,18,24,35,47,50,62),则在其中利用二分法查找值为24的元素需要经过()次比较。
A.1
B.2
C.3
D.4
设有序表为(21,22,23,24,25,26,27,28,29,30,31,32),元素的下标从0开始。
(1)说出有哪几个元素需要经过4次元素间的比较才能成功查到。
(2)画出对上述有序表进行折半查找所对应的判定树(树结点用数值表示)
(3)设查找元素为5,需要进行多少次元素间的比较才能确定不能查到。
(4)求在等概率条件下,成功查找的平均比较次数?
顺序存储的线性表
实验目的:
(1)了解线性表的逻辑结构特征。
(2)熟练掌握线性表的顺序存储结构的描述方法,及在其上实现各种基本运算的方法。
(3)掌握和理解本实验中出现的一些基本的c语言语句。
(4)体会算法在程序设计中的重要性。
实验内容:
(1)将一顺序表a中的元素逆置。要求算法仅用一个辅助结点。
(2)求顺序表中的元素的最大值和次最大值。
(3)试设计一个算法,仅用一个辅助结点,实现将顺序表a中的结点循环右移k位的运算。
(4)设一顺序表中元素值递增有序。试设计一算法,将元素x插入到表中适当的位置上,并保持顺序表的有序性。
已知如下所示长度为12的关键字有序的表:
(1)试按表中元索的顺序依次插入到一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求其在等概宰的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表,求在等概率的情况下查找成功的平均查找长度。
(3)按表中元素的顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
已知如下所示长度为12的表:(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
①试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
②若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
③按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
成功;否则确定下一步搜索的区间为4(i-1)+1到4i-1.然后在此区间内与第4i-2个元素作比较,若相等则搜索成功,否则继续与第4i-3或4i-1个元索进行比较,直到搜索成功。
(1)给出实现算法。
(2)试面出当表长n=16时的判定树,并推导此搜索方法的平均搜索长度(考虑搜索元素等概率和n%4=0的情况)。
算法实现的思路为:在有序单链表中插入一个数据元素x,首先要找到该元素应该插入到什么位置,才能保证插入后的单链表仍为有序表。因此,算法的第一步是寻找x的位置:设置指针p、q,最初p指向头结点,q指向头结点的下一个结点,比较q所指数据域的值与x的大小,如果小于x,则p、q分别向后移动一个位置,使p始终作为q的前驱结点,然后重复上面的比较过程;如果比较结果大于x或是比较到最后单链表结束了,则找到了插入位置,在p与q之间插入结点x即可。算法的具体实现如下:
已知如下11个数据元素的有序表(6,14,19,21,36,57,63,76,81,89,93),请画出查找键值为21(成功)和85(失败)的查找过程。