散列查找选择题（1）散列技术中的冲突指的是（）。A．两个元素具有相同的序号B．两个元素的键值不同，而其他属性相同C．数据元素过多D．不同键值的元素对应于相同的存储地址（2）设散列表表长为m=14，散列函数H(k)=k mod 11。表中已有15、38、61、84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是（）。A．8B．3C．5D．9（3）为一组关键码(87，73，25，55，90，28，31，17，101，22，3，62)构造散列表，设散列函数为H(key)=key mod 11，在用链地址法处理后位于同一链表[1]中的是（）。A．81，90B．31，101C．3，78D．62，73（4）在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（）。A．一定都是同义词B．一定都不是同义词C．不一定都是同义词D．都相同（5）在散列函数H(key)=key mod m中，一般来讲，m应取（）。A．奇数B．偶数C．素数D．充分大的数（6）下面关于散列查找的说法正确的是（）。A．散列函数越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有散列函数中最好的C．不存在特别好和特别坏的散列函数，要视情况而定D．若在散列表中删去一个元素，只要简单地将该元素删去即可（7）关于散列查找说法不正确的有几个（）。①采用链地址法解决冲突，查找一个元素的时间是相同的②采用链地址法解决冲突，若插入总是在链首，则插入任一个元素的时间是相同的③采用链地址法解决冲突易引起聚集现象④再散列法易引起聚集现象A．1B．2C．3D．4（8）关于散列查找，下面说法正确的是（）。A．再散列法处理冲突不会产生聚集B．散列表的装填因子越大说明空间利用率越高，因此应使装填因子尽可能大C．散列函数选择得好可以减少冲突现象D．对任何关键码集合都无法找到不产生冲突的散列函数（9）散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A．最大概率B．最小概率C．平均概率D．同等概率（10）散列函数方法一般适用于（）情况下的查找。A．查找表为链表B．查找表为有序表[2]C．关键码集合比地址集合大得多D．关键码集合与地址集合存在对应关系（11）设哈希表[3]长m=15，哈希函数[4]H(key)=key mod 13，关键码集合为(53，17，12，61，89，70，87，25，64，46)，采用二次探测再散列方法处理冲突，则查找成功的平均比较长度为（）。A．1.4B．1.6C．1.8D．2.0（12）假设有10个关键码，它们具有相同的散列函数值，用线性探测法把这10个关键码存入散列表中至少需要做（）次探测。A．110B．100C．55D．45（13）采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（）。A．数据元素过多B．装填因子过大C．散列函数选择不当D．解决冲突的算法不好（14）对具有n个关键码的散列表进行查找，平均查找长度[5]是（）。G．可读性和文档性H．数据复杂性和程序复杂性（7）算法的时间复杂度与（）有关。A．问题规模B．计算机硬件[6]性能C．编译程序[7]的质量D．程序设计语言[8]（8）算法的时间复杂度与（）有关。A．问题规模B．待处理数据的初态C．算法的易读性D．A和B（9）某算法的时间复杂度是○(n2)，表明该算法（）。A．问题规模是n2B．执行时间等于n2C．执行时间与n2成正比D．问题规模与n2成正比（10）下面说法错误的是（）。①算法原地工作的含义是指示不需要如何额外的辅助空间②在相同的规模n下，复杂度○(n)的算法在时间上总是优于复杂度○(2n)的算法③所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界④同一个算法，实现语言的级别越高，执行效率就越低（11）算法for (i=n-1; i>=1; i--)for (j=1; j<=i; j++)if (a[j]>a[j+1]) a[j]与a[j+1]交换；其中n为正整数，则最后一行语句的频度（执行次数）在最坏情况下是（）。A．○(n)B．○(nlog2n)C．○(n3)D．○(n2)（12）算法的时间复杂度属于一种（）。A．事前统计的方法B．事先分析估算的方法C．事后统计的方法D．事后分析估算的方法（13）设某算法完成对n个元素进行处理，所需的时间是T(n)=100 nlog2n+200n+500，则该算法的时间复杂度是（）。A．○(1)B．○(n)C．○(nlog2n)D．○(nlog2n+n)（14）假设时间复杂度为○(n2)的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上运行需要（）ms。A．3.1B．6.2C．12.4D．x（无法确定）（15）下列程序段[9]加下划线的语句执行（）次。for (m=0,i=1; i<=1; i++)for (j=1; j<=2*i; j++)________；A．n2B．3nC．n(n+1)D．n3A．○(log2n)B．○(n)C．○(nlog2n)D．与n无关应用题（15）已知关键码序列为（Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec），散列表的地址空间[10]为0~16，设散列函数为H(x)=[i/2]，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。（16）设散列表为T[0..12]，散列函数为H(key)=key mod 13，采用再散列法处理冲突，再散列函数为Hi(key)=(Hi-1+REV(key+1) mod 11+1) mod 13，其中REV(key)表示颠倒10进制数key的各位，如REV(73)=37，REV(7)=7等。将关键码集合(2，8，31，20，19，18，53，27)插入到散列表中，画出最后的散列表，并计算查找成功的平均查找长度。（17）给定关键码序列(26，25，20，34，28，24，45，64，42)，设定装填因子为0.6，请给出除留余数法的散列函数，画出采用线性探测法处理冲突构造的散列表。