第八章 查找(4)
时间:2025-07-10
时间:2025-07-10
第八章 查找
缺点,指出一种适用于索引顺序文件的外存设备。
9.5 已知一个长度为12的线性表(Dec,Feb,Nov,Oct,Jul,Sept,Aug,Apr,May,Jun,Jan,Mar)。
(1)按该线性表中元素的顺序构造出一棵二叉排序树;
(2)若每个元素的查找概率均等,查找此二叉排序树中任意一个结点的平均查找长度ASL是多少?
(3)若对线性表的元素按字典顺序从小到大排列以后,再用折半查找方法,则查找其中任意一个元素的平均查找长度ASL是多少?
(4)画出相应的平衡二叉树。
9.6 折半查找过程可以利用一棵判定树来描述。请画出n'13时的判定树。
9.7 何谓散列冲突?何谓冲突处理?简要说明冲突处理的过程。
9.8 已知散列函数为H(k)二k%7,并采用线性探测再散列方法处理冲突,所建立的散列表如下所示,请依次将关键字17,27填人表中。
9.9 在初始为空的散列表中依次插入以下关键字序列:Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sept,Oct,Nov,Dec。散列函数为H(k):i%p,其中,i为关键字的第一个字母在英文字母表中的序号。请分别画出按以下两种情况构成的散列表:
(1)散列地址空间为[0,12],p=13,用线性再散列法处理冲突;
(2)散列地址空间为[0,6],p=7,用链地址法处理冲突。
9.10 在散列函数与散列地址范围都分别相同的前提下,采用链地址法处理冲突比采用开放地址法处理冲突的时间效率要高,为什么?
9.11 已知有长度为M的散列表HT[0,M-1],散列函数为H(k),并且采用线性探测再散列方法处理冲突。请写出在该散列表中查找关键字值为key的元素存在与否的算法。若存在,则给出它在表中的位置,否则给出相应的信息。
9.12 请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为H(k),处理冲突的方法为线性再散列法。
9.13 请写出一个从散列文件中删除一个记录的算法。设所用的散列函数为H(k),处理冲突的方法为链地址法。
9.14 已知一长度为n的线性表A和待散列地址空间为[0,m-1),其中m≥n。若采用除留余数法构造散列函数与步长为根号下N下取整的线性探测再散列法处理冲突,请分别写出建立该散列表和在该散列表上进行查找的算法。
9.15 已知散列函数为H(k)=(3*k)%11,采用线性探测再散列法处理冲突。对下列关键字值序列构造一个散列地址空间为[0,10]的散
列表,并求出ASL。
(22,41,53,8,46,30,1,3l,66)
历年考试题
11.若用二分查找法取得的中间位置元素键值大于被查找值,说明被查找值位于中间值的前面,下次的查找区间为从原开始位置至( )
A.该中间位置B.该中间位置-1
C.该中间