考研2023年暨南大学( )

在折半查找中,要求待查找的关键字序列必须________,这样才能进行查找操作。

考研2023年暨南大学( )

分块查找的平均查找长度不仅与索引表的长度有关,而且与块的长度有关。

考研2023年暨南大学( )

顺序表查找指的是在顺序存储结构上进行查找。

考研2023年计算机统考( )

现有长度为 5,初始为空的散列表HT,散列函数H(k)=(k+4) mod 5, 用线性探查再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入HT中,然后删除关键字 25 ,则HT中查找失败的平均查找长度为【 】。

A、1

B、1.6

C、1.8

D、2.2

1.8

1)插入2022,H(2022)=(2022+4) mod 5 =1;1位为空,可插入;

2)插入12,H(12)=(12+4) mod 5 =1,冲突,采用线性探测法,每次向右探索一位,当前为空,可插入;

3)插入25,H(25)=(25+4) mod 5 =4,4位为空,可插入。

4)删除25,该散列表采用线性探测再散列法,属于开放寻址法,从中删除关键字时,不能简单地置NIL,而是作一个标记,如DELETED,简记为D。

5)计算查找失败时的平均查找长度:

查找元素失败统计项数目与散列表空间大小和散列函数均有关,这里取5。

按照冲突处理方法,计算出每种情况查找失败需要的次数,即失败查找长度:

散列到0:

查找次数为1;

散列到1:

查找次数为3;

散列到2:

查找次数为2;

散列到3:

查找次数为1;

散列到4:

查找次数为2。

查找失败时的平均查找长度为:(1+3+2+1+2)/5=1.8

考研2023年计算机统考( )

对含有 600 个元素的有序顺序表进行折半查找,关键字之间的比较次数最多是【 】

A、9

B、10

C、30

D、300

10

若采用折半查找法查找一个顺序表中不存在的元素,最大比较次数为对应二叉搜索树的高度,设结点数为 n ,

二叉搜索树高度为 h=[log2n]+1 。

代入 n=600,解得h=10。