第八章 查找(4)

第八章 查找

缺点，指出一种适用于索引顺序文件的外存设备。
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．该中间