单项选择(1998年中国科学院软件研究所)

假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行【 】次探测。

A、K-1次

B、K次

C、K+1次

D、K(K+1)/2次

答案解析

D

【解析】

因为K个关键字互为同义词,只有在存入第一个关键字的情况下不发生冲突,所以至少需要进行1+2+...+K=K(K+1)/2次探测。

讨论

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

若杂凑表(Hash)的地址范围为[0,9],杂凑函数为H(key)=(key2+2) MOD 9,并采用链地址法处理冲突,请画出元素7、4、5、3、6、2、8、9依次插入杂凑表的状态。

设有12个数据{25,40,33,47,12,66,72,87,94,22,5,58},它们存储在散列表中,利用双散列解决冲突,要求插入新数据的平均查找次数不超过3次。① 该散列表的大小m应该设计多大?② 试为该散列表设计相应的散列函数(用除留余数法)并计算寻找下一个“空位”时向前跨步步长的再散列函数。③ 顺次将各个数据散列到表中。④ 计算查找成功的平均查找次数。

设a、b、c、d和e这5个字符的编码分别为1、2、3、4和5,并设标识符依以下次序出现ac、bd、aa、be、ab、ad、cd、bc、ae和cd。要求用哈希(Hash)方式将它们存放在具有10个位置的表中。① 对上述关键字(标识符)构造一个哈希函数,使得发生冲突尽可能地少。② 用线性探测再散列法解决冲突。写出上述各关键字在表中的位置。

对关键码序列(12,24,15,56,20,87,69,9)采用散列法进行存储和查找,并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性控查法(顺地探查可用存储单元)解决冲突所构造的散列表为【 】。

对于关键码序列(54,34,5,14,50,36,47,83),用链地址法(或拉链法)解决冲突构造散列表(即将冲突的元素存储在同一个单链表中,单链表的头指针存入散列地址对应的单元),设散列函数为H(Key)= Key MOD7(MOD表示整除取余运算),则构造散列冲突次数最多的哈希单元的地址是【 】。

若散列表的负载因子α<1,则可避免碰撞的产生。

在n个结点的无向图中,若边数>n-1,则该图必是连通图。

用DFS遍历一个无环有向图,并DFS算法退栈返回时打印出相应的顶点,则输出的顶点序列是【 】。

图的遍历方式有__________和__________两种。