第九章
一、选择题
1.二分法查找 存储结构。
A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式 D. 既不适合于顺序也不适合于链式
2.已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当二分查找值为90的元素时， 次比较后查找成功；当二分查找值为47的元素时， 次比较后查找成功。 A. 1 B. 2 C. 3 D. 4
3.散列函数有一个共同性质，即函数值应当以 取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 4.设散列地址空间为0～m－1,k为关键字，用p去除k，将所得的余数作为k的散列地址，
即H(k)＝k % p。为了减少发生冲突的频率，一般取p为 。 A. 小于m的最大奇数 B. 小于m的最大偶数
C. m D. 小于m的最大素数
二、填空
1. 假定在有序表A[1..20]上进行二分查找，则比较一次查找成功的结点数为 ， 比较两次查找成功的结点数为 ，比较三次查找成功的结点数为 ，比较四次查找成功结点数为 [4]8 ，比较五次查找成功的结点数为 ，平均查找长度为 。 2. 在索引查找或分块查找中，首先查找 ，然后再查找相应的 ，整个
索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之 。
3. 在散列存储中，装填因子α的值越大，存取元素时发生冲突的可能性就 ，当α的值
越小，存取元素时发生冲突的可能性就 。
4. 给定线性表(18,25,63,50,42,32,90)，用散列方式存储，若选用h(K)=K % 9作为散列函
数，则元素18的同义词元素共有 个，元素25的同义词元素共有 个，元素50的同义词元素共有 个。 三、判断题
1.散列法存储的基本思想是由关键码的值决定数据的存储地址（ ）。
2.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法（ ）。 3.m阶B-树每一个结点的子树个数都小于或等于m（ ）。 四、综合题
1.若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试问在下面三 种情况下，分别讨论两者在等概率时，平均查找长度是否相同?
(1)查找不成功，即表中没有关键字等于给定值k的记录；
(2)查找成功，且表中只有一个关键字等于给定值k的记录；
(3)查找成功，且表中有若干个关键字等于给定值k的记录，一次查找要求找出所有记
录，此时的平均查找长度应考虑找到所有记录时所用的比较次数。
2.假定有n个关键字，它们具有相同的Hash函数值，用线性探测方法把这n个关键字 存入到Hash地址空间中要做多少次探测?
3.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，问 (1)每块的理想长度是多少?
13
(2)分成多少块最为理想?
(3)平均查找长度是多少?
(4)若每块长度为20，平均查找长度是多少?
4.设A(k)有如下10个元素：2，4，6，8，10，12，14，16，18，20。若对A(k)分别查找x＝1，3，13，21，试跟踪下面过程的执行，并分析该程序段关于n的计算时间。 【程序段】 i=1;j=n; do {
k=(i+j)/2; if A(k)<=x i=k+1 else j=k-1
}while !(i>j);
5.设有一个已排序的整数数组a[1..n]，和一个整数x，研究下面用类C所表示的折半查找的五个程序段，指出哪些是正确的。 第一个：
i=1; j=n;
do{ k=(i+j)div 2;
if x>a[k] i=k+1; else j=k-1; }while !((a[k]=x) || (i>j)); 第二个: i=1; j=n; while (i<=j) { k=(i+j) / 2;
switch{
case x>a[k]: i=k+1; case x= =a[k]: return; case x 第三个： i=1; j=n; do{ k=(i+j) / 2; if x>a[k] i=k; else j=k }while !((a[k]= =x) || (i>=j)); 第四个： i＝1; j=n; do{ k=(i+j) / 2; if x 14 i=1; j=n; do{ k=(i+j) / 2; if x 第十章 一、选择题 1.目前以比较为基础的内部排序时间复杂度T(n)的范围是 ；其比较次数与待 排序的记录的初始排列状态无关的是 。 A. ①O(log2 n)～O(n) ②O(lon2 n)～O(n2 ) ③O(nlog2 n)～O(n2 ) ④O(n)～O(n2 ) ⑤O(n)～O(nlog2 n) B. ①插入排序 ②先用二分法查找，找到后插入排序 ③快速排序 ④冒泡排序 2.设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是 。 A. 6 B. 7 C. 8 D. 20 3.在归并排序过程中，需归并的趟数为 。 A. n B. √n C. log2 n向上取整 D. log2 n向下取整 4.一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为 。 A. (79、46、56、38、40、80) B. (84、79、56、38、40、46) C. (84、79、56、46、40、38) D. (84、56、79、40、46、38) 5.一组记录的关键码为(46、79、56、38、40、84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。 A. (38、40、46、56、79、84) B. (40、38、46、79、56、84) C. (40、38、46、56、79、84) D. (40、38、46、84、56、79) 6.在平均情况下快速排序的时间复杂性为 ，空间复杂性为 ；在最坏情况 下（如初始记录已有序），快速排序的时间复杂性为 ，空间复杂性为 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 ) 二、填空 1.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时，第四次选择和交换后，未排序记录(即无序表)为 。 2.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时，第一趟需进行相邻记 录交换的次数为 ，在整个冒泡排序过程中共需进行 趟后才能完成。 3.在归并排序中，若待排序记录的个数为20，则共需要进行 趟归并，在第三趟归并中，是把长度为 的有序表归并为长度为 的有序表。 4.在直接插入和直接选择排序中，若初始数据基本正序，则选用 ，若初始数 据基本反序，则选用 。 5 .在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法；若只从排序结果的稳定 性考虑，则应选取 ；若只从平均情况下排序最快考虑，则应选取 _______方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。 15 三、判断题 1.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影 响时间复杂性的主要因素（ ）。 2.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)（ ）。 3.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)（ ）。 4.堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值（ ）。 四、综合题 1.在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动， 从而认为该排序算法是不稳定的，这种说法对吗?为什么? 2.设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。在以下 的排序方法中，采用哪种方法最好?为什么?快速排序，堆排序，归并排序，基数排序的Shell排序。 3.证明对一个长度为n的任意文件进行排序，至少需要作nlog2 n比较。 4.判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。 (1) (100，85，98，77，80，60，82，40，20，10，66)； (2) (100，98，85，82，80，77，66，60，40，20，10) (3) (100，85，40，77，80，60，66，98，82，10，20)； (4) (10，20，40，60，66，77，80，82，85，98，100)； 5.什么是内部排序？什么是排序方法的稳定性和不稳定性？ 十二章 文件 一、综合题 1.试列出文件的存储结构以及其相应文件类型，并简略回答其特点。 16