19 散列查找

选择题

（1） 散列技术中的冲突指的是（ ）。 A．两个元素具有相同的序号 B．两个元素的键值不同，而其他属性相同 C．数据元素过多 D．不同键值的元素对应于相同的存储地址

（2） 设散列表表长为m=14，散列函数H(k)=k mod 11。表中已有15、38、61、84

四个元素，如果用线性探测法处理冲突，则元素49的存储地址是（ ）。 A．8 B．3 C．5 D．9

（3） 为一组关键码{87，73，25，55，90，28，31，17，101，22，3，62}构造散列

表，设散列函数为H(key)=key mod 11，在用链地址法处理后位于同一链表中的是（ ）。 A．81，90 B．31，101 C．3，78 D．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．1 B．2 C．3 D．4

（8） 关于散列查找，下面说法正确的是（ ）。 A．再散列法处理冲突不会产生聚集

B．散列表的装填因子越大说明空间利用率越高，因此应使装填因子尽可能大 C．散列函数选择得好可以减少冲突现象

D．对任何关键码集合都无法找到不产生冲突的散列函数

36

（9） 散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。 A．最大概率 B．最小概率 C．平均概率 D．同等概率

（10） 散列函数方法一般适用于（ ）情况下的查找。 A．查找表为链表 B．查找表为有序表 C．关键码集合比地址集合大得多 D．关键码集合与地址集合存在对应关系

（11） 设哈希表长m=15，哈希函数H(key)=key mod 13，关键码集合为{53，17，12，

61，89，70，87，25，64，46}，采用二次探测再散列方法处理冲突，则查找成功的平均比较长度为（ ）。 A．1.4 B．1.6 C．1.8 D．2.0

（12） 假设有10个关键码，它们具有相同的散列函数值，用线性探测法把这10个关

键码存入散列表中至少需要做（ ）次探测。 A．110 B．100 C．55 D．45

（13） 采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（ ）。 A．数据元素过多 B．装填因子过大 C．散列函数选择不当 D．解决冲突的算法不好

（14） 对具有n个关键码的散列表进行查找，平均查找长度是（ ）。 A．○(log2n) B．○(n) C．○(nlog2n) D．与n无关

应用题

（15） 已知关键码序列为（Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，

Nov，Dec），散列表的地址空间为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，请给出除留余数法的散列函数，画出采用线性探测法处理冲突构造的散列表。

37

20 排序的基本概念

选择题

（1） 排序算法的稳定性是指（ ）。

A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C．排序算法的性能与被排序元素的数量关系不大 D．排序算法的性能与被排序元素的数量关系密切

（2） 对任意的7个关键码进行排序，至少要进行（ ）次关键码之间的比较。 A．13 B．14 C．15 D．16

（3） 一个待排序的n个记录可分为n/k组，每组包含k个记录，且任一组内的各记

录分别大于前一组内的所有记录且小于后一组内的所有记录，若采用基于比较的排序方法，其时间下界为（ ）。 A．○(klog2k) B．○(klog2n) C．○(nlog2k) D．○(nlog2n)

（4） 关于排序，下列说法中正确的是（ ）。

A．稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高 B．对同一个线性表使用不同的排序方法进行排序，得到的排序结果可能不同 C．排序方法都是在顺序表上实现的，在链表上无法实现排序方法 D．在顺序表上实现的排序方法在链表上也可以实现

（5） 下列不属于内部排序方法的是（ ）。 A．归并排序 B．拓扑排序 C．堆排序 D．插入排序

38

21 插入排序

选择题

（1） 用直接插入排序对下面四个序列进行由小到大排序，元素比较次数最小的是

（ ）。

A．94，32，40，90，80，46，21，69 B．21，32，46，40，80，69，90，94 C．32，40，21，46，69，94，90，80 D．90，69，80，46，21，32，94，40

（2） 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（ ）。 A．起泡排序 B．直接插入排序 C．快速排序 D．简单选择排序

（3） 数据序列{8，9，10，4，5，6，20，1，2}只能是（ ）的两趟排序后的结

果。 A．选择排序 B．冒泡排序 C．插入排序 D．堆排序

（4） 对数据序列{15，9，7，8，20，-1，4}进行排序，一趟后数据序列变为{9，15，

7，8，20，-1，4}，则采用的是（ ）。 A．选择排序 B．冒泡排序 C．插入排序 D．堆排序

（5） 下列排序算法中，（ ）可能会出现下面情况：在最后一趟开始之前，所有

元素都不在最终位置上。 A．起泡排序 B．插入排序 C．快速排序 D．堆排序

（6） 对有n个记录的线性表进行直接插入排序，在最好情况下需比较（ ）次。 A．n-1 B．n+1 C．n/2 D．n(n-1)/2

39

22 希尔排序

选择题

（1） 以下排序算法中，（ ）不能保证每趟至少能将一个元素放到其最终位置上。 A．快速排序 B．希尔排序 C．起泡排序 D．堆排序

（2） 对数据序列{98，36，-9，0，47，23，1，8，10，7}采用希尔排序，下列（ ）

是增量为4的排序结果。

A．{10，7，-9，0，47，23，1，8，98，36} B．{-9，0，36，98，1，8，23，47，7，10} C．{36，98，-9，0，23，47，1，8，7，10} D．以上都不对

40