数据结构试题库

if x>a[k] i=k+1; }while (i>=j); 第五个： i=1; j=n; do{

k=(i+j) / 2; if x=j);

解答：第三个程序段不正确。例如，令n＝2,a[1]＝5,a[2]＝6,x＝6,则开始时，i＝1,j＝2, k＝(1＋2) div 2，又因a[k]

第五个程序段不正确。例如，令n＝2,a[1]＝5,a[2]＝6,x＝6,则开始时，i＝1,j＝2, k＝1,又因x

第一、二、四个程序段是正确的折半查找算法的表示。

3、设有一个含有200个元素的表待散列存储,用线性探查法处理冲突,若按关键字查询时找到一个元素的平均查找长度(即平均探查次数)不能超过1.5,则散列表的长度应至少为多少?

答：采用线性探查法处理冲突时的平均探查次数为 (1+1/(1+α))/2，其中α为装填因子，它等于待散列的数据元素个数为n和散列表长度m的比值，及α=n/m。 由题意可知：(1+1/(1+α))/2≤1.5 求解后得：α≤1/2 即：n/m≤1/2 得到：m≥2n

把n=200带入则可知：散列表的长度至少为400。

10 内部排序

- 49 -

沈阳理工大学应用技术学院

信息与控制学院 计算机科学与技术教研室

2011-5-8

数据结构复习题：内部排序 单选题

1、设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是___6__。 2、在归并排序过程中，需归并的趟数为__log2 n向上取整___。

3、一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为__(84、79、56、38、40、46)___。

4、一组记录的关键码为(46、79、56、38、40、84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_____。 5、在平均情况下快速排序的时间复杂性为__O(nlog2n)___，空间复杂性为__O(log2n)___；在最坏情况下（如初始记录已有序），快速排序的时间复杂性为___O(n^2)__，空间复杂性为__O(n)___。 6、顺序查找法适合于存储结构为_____顺序存储或链式存储_____的线性表。 7、对线性表进行折半查找时,要求线性表必须_________。

8、采用顺序查找法查找长度为n的线性表时,每个元素的平均查找长度为________。

9、采用折半查找法查找长度为n的线性表时,每个元素的平均查找长度为___O(log2n)____。 10、有一个长度为12的有序表,按折半查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为_______。

11、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值82的结点时,_________次比较后查找成功。

12、对有18个元素的有序表作折半查找,则查找A[3]的比较序列的下标为______。

- 50 -