全国自考数据结构导论（查找）模拟试卷1

27． 写出从哈希法构造的散列表中删除关键字为k的一个记录的算法，设所有哈希函数为H，解决冲突的方法是链地址法。

26． 试写出二分查找的递归算法。

24． 已知一组关键字为{5，88，12，56，7l，28，33，43，93，17},采用链地址法构造哈希表。

25． 画出对长度为10 的有序表进行二分查找的一颗判定树，并求其等概率时查找成功的平均查找长度。

23． 选取哈希函数 H(k)=(k)MOD 11。用二次探测再散列处理冲突，试在 0-10 的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)造哈希表，并求等概率 情况下查找成功时的平均查找长度。

22． 在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。

20． 顺序查找时间为O(n)，折半查找时间为O(log₂n)，哈希法为O(1)，为什么有高效率的查找方法而低效率的方法不被放弃?

19． 常用的处理冲突的方法有：_______和_______。

21． 为什么有序的单链表不能进行折半查找?

17． 哈希函数的构造方法主要有______、_____、______、_______和______。

18． 在哈希函数h(key)=key％m中，m值最好取_____。

16． 在分块查找法中，首先查找______，然后再查找相应的_______。

15． 在分块检索中，若索引表和各块内均采用顺序查找，则900个元素的线性表分成________块最好；若分成25块，其平均查找长度为_______。

12． 折半查找只能使用________存储结构。

14． 索引顺序表上的查找分两个阶段，它们是______和______。

13． 已知一个有序表为{10，23，35，46，48，55，59，64，72，83，88，99}，当用折半查找方法查找值为46和83的元素时，分别需要比较_______次和_______次才能查找成功；若采用顺序查找时，分别需要比较______次和______次才能查找成功。

10． 将10个数据元素存放到有100000个单元的哈希表中，则__________产生冲突。

9． 设有一组关键字为{19，15，23，2，68，20，84，28，55，11，10，80}，用链地址法构造哈希表，哈希函数为h(key)=key％13，则哈希地址为2的链表中有______个记录。

11． 顺序查找在查找成功情况下的平均查找长度为________；在查找失败情况下的平均查找长度为________。

8． 哈希表的地址区间为0～17，哈希函数为h(key)=Kmod17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18，59}依次存储到哈希表中，则存放元素59需要搜索的次数是________。

7． 下面关于哈希表的说法中，正确的是_______。

5． 有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功时所需平均比较次数为_______。

6． 当采用分块查找时，数据的组织方式为______。

4． 对有14个数据元素的有序表a[14]进行折半查找，搜索到a[5]的关键字等于给定值，此时元素比较顺序依次为________。

3． 下面有关折半查找的叙述中，正确的是_______。

2． 对长度为4的顺序表进行查找，若查找第一个元素的概率为1／24，第二个元素的概率为1／6，第三个元素的概率为2／3，第四个元素的概率为1／8，则查找任一个元素的平均查找长度为_______。

1． 对有n个数据元素的顺序表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为_____________。