1、数据结构练习试卷 4及答案与解析 1 在长度为 64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。 （ A） 63 （ B） 64 （ C） 6 （ D） 7 2 对长度为 n的线性表进行顺序查找，在最坏情况下，所需要的比较次数为_。 （ A） 1og2n （ B） n/2 （ C） n2 （ D） n+1 3 设有 100个结点，用二分法查找时，最大比较次数是 _。 （ A） 25 （ B） 50 （ C） 10 （ D） 7 4 如果要求一个线性表既能较快地查找，又能适应动态变化 的要求，则可采用_的方法。 （ A）分块 （ B）顺序 （ C）二分法 （ D）基于属性 5 在最
2、坏情况下，下列排序方法中时间复杂度最小的是 _。 （ A）冒泡排序 （ B）快速排序 （ C）插入排序 （ D）堆排序 6 对于长度为 n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 _。 （ A）冒泡排序为 n/2 （ B）冒泡排序为 n （ C）快速排序为 n （ D）快速排序为 n(n-1)/2 7 n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 _。 （ A） O(1) （ B） O(1og2n) （ C） O(n2) （ D） O(n) 8 若原始数据序列 (23,4,45,67,12,8,19,7)采用直接插入排序法 (顺序地将每个元素插入到它之前的适当位
3、置 )排序，则进行完第 4趟后的排序结果是 _。 （ A） 4,8,45,23,67,12,19,7 （ B） 4,7,8,12,23,45,67,19 （ C） 4,12,8,19,7,23,45,67 （ D） 4,12,23,45,67,8,19,7 9 下面的排序方法中，关键字比较次数与 记录的初始排列无关的是 _。 （ A）希尔排序 （ B）冒泡排序 （ C）直接插入排序 （ D）直接选择排序 10 在排序算法中每一项都与其他诸项进行比较，计算出小于该项的项的个数，以确定该项的位置叫 _。 （ A）插入排序 （ B）交换排序 （ C）选择排序 （ D）枚举排序 11 在下列算法中，
4、_算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。 （ A）堆排序 （ B）冒泡排序 （ C）插入排序 （ D）快速排序 12 在文件 “局部有序 ”或 文件长度较小的情况下，最佳内部排序方法是 _。 （ A）直接插入排序 （ B）冒泡排序 （ C）简单选择排序 （ D）归并排序 13 从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为 _。 （ A）插入排序 （ B）选择排序 （ C）希尔排序 （ D）归并排序 14 如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是
5、不稳定的。 _是稳定的排序方法，因为这种方法在比较相邻元素时 ，值相同的元素并不进行交换。 （ A）冒泡排序 （ B）希尔排序 （ C）快速排序 （ D）简单选择排序 15 对长度为 n的线性表排序，在最坏的情况下，比较次数不是 n(n-1)/2的排序方法是 _。 （ A）快速排序 （ B）冒泡排序 （ C）直接插入排序 （ D）堆排序 16 冒泡排序在最坏情况下的比较次数是 _。 （ A） n(n+1)/2 （ B） n1og2n （ C） n(n-1)/2 （ D） n/2 17 在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的排序 算法是 _。 （ A）冒泡排序 （ B
6、）基数排序 （ C）快速排序 （ D）归并排序 18 为了用一个数代表一批数，人们常用这批数据的算术平均值 (简称平均值 )或中位数来代表。中位数就是位于这批数中间的数 (大于它的数与小于它的数一样多 )。对于奇数个数而言，排序后很容易确定中间那个数；对于偶数个数而言，排序后中间会有两个数，再取这两个数的算术平均，就是中位数。以下关于平均值与中位数的叙述中， _是不正确的。 （ A）中位数比平均值稳健，不易受极端值影响 （ B）每个数据加倍后，平均值也加倍 ；每个数据增加 1后，平均值也增加 1 （ C）三组各有 n个数据有三个中位数，它们的中位数就是这三组数据全体的中位数 （ D）三组各有
7、n个数据有三个平均值，它们的平均值就是这三组数据全体的平均值 19 已知递归函数 f(n)的功能是计算 1+2+n ，且 n1，应采用的代码段是_。 （ A） if n 1 then return 1 else return n+f(n-1) （ B） if n 1 then return 1 else return n+f(n+1) （ C） if n 1 then return 0 else return n+f(n-1) （ D） if n 1 then return 0 else return n+f(n+1) 20 设最优的分配方案为完成这三项工作所需的总天数最少，则在最优分配方案中
8、， _。 （ A）甲执行 P （ B）甲执行 Q （ C）乙执行 P （ D）乙执行 R 21 在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更它们的相对位置，这就是 (1)排序。每次从未排序的记录中挑出最小 (或最大 )关键码值的记录，加入到已排序记录的末尾，这是 (2)排序。 （ A）插入 （ B）枚举 （ C）交换 （ D）归并 （ E）基数 （ A）插入 （ B）枚举 （ C）交换 （ D）归并 （ E）选择 23 设有 n个结点进行排序，不稳定排序是 (1)；快速排序的最坏时间是 (2)。 （ A）直接插入排序 （ B）冒泡排序 （ C）希尔排序 （ D）归并排序 （
9、 A） O(n1og2n) （ B） O(n2) （ C） O(n2/2) （ D） O(n) 25 设有 n个结点进行排序，不稳定排序是 (1)；快速排序的最大比较次数是 (2)。 （ A）直接插入排序 （ B） 冒泡排序 （ C） Shell排序 （ D）归并排序 （ A） n1og2n （ B） n2 （ C） n2/2 （ D） n 27 堆排序是一种基于 _的排序方法， _不是堆。 （ A）计数 （ B）插入 （ C）选择 （ D）归并 （ A） 15,28,25,56,68,63,30 （ B） 15,28,25,30,68,63,56 （ C） 68,28,63,25,15,56
10、,30 （ D） 68,56,39,63,28,25,15 29 正规式 (1|3|5)(202)(c|de)表示的正规集合 中元素数目为 (1)， (2)是该正规集合中的元素。 （ A） 6 （ B） 7 （ C） 8 （ D）无穷 （ A） 135202cde （ B） 1202c （ C） 302cde （ D） 52c 31 阅读下列说明、流程图和算法进行填空。 下面的流程图用 N-S盒图形式描述了数组 A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于 Ai，并且数组中下
11、标小于 i的元素的值均小于基准数，下标大于 i的元素的值均大 于基准数。设数组 A的下界为 low，上界为 high，数组中的元素互不相同。例如，对数组 (4,2,8,3,6)，以 4为基准数的划分过程如图8-34所示。 算法说明：将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数 int p(int A,int low,int high)实现了上述流程图的划分过程并返回基准数在数组 A中的下标。递归函数 void sort(int A,int L,int H)的功能是实现数组 A中元素的递增排序。 算法如下。 void sort(int A， int L，
12、 int H) if (L H) k=p(A,L,H)； /p()返回基准数在数组 A中的下标 sort(4)； /小于基准数的元素排序 sort(5)； /大于基准数的元素排序 数据结构练习试卷 4答案与解析 1 【正确答案】 B 【试题解析】 在长度为 64的有序线性表中，其中的 64个数据元素是按照从大到小或从小到大的顺序排列有序的。在这样的线性表中进行顺序查找，最坏的情况就是查找的数据元素不在线性表中或位于线性表的最后。按照线性表的顺序查找算法，首 先用被查找的数据和线性表的第一个数据元素进行比较，若相等，则查找成功，否则，继续进行比较，即和线性表的第二个数据元素进行比较。同样，若相等
13、，则查找成功，否则，继续进行比较。依次类推，直到在线性表中查找到该数据或查找到线性表的最后一个元素，算法才结束。因此，在长度为 64的有序线性表中进行顺序查找，最坏的情况下需要比较 64次。因此，本题的正确答案为B。 【知识模块】 数据结构 2 【正确答案】 C 【试题解析】 在长度为 n的线性表中进行顺序查找，最坏情况下需要比较 n次。选项 C正确。 【知识 模块】 数据结构 3 【正确答案】 D 【试题解析】 在最坏情况下，二分法查找的比较次数均为 1og2(n+1)L。 n为 100时，最大比较次数为 7。所以，本题应该选择 D。 【知识模块】 数据结构 4 【正确答案】 A 【试题解析
14、】 二分法是快速查找方法，但要求线性表是有序的。如果把线性表按趋势分块，也就是说，块之间有序，块内不一定有序。这样就可以既能较快地查找，又能适应动态变化的要求。本题正确答案为选项 A。 【知识模块】 数据结构 5 【正确答案】 D 【试题解析】 在最 坏情况下：冒泡排序、快速排序和插入排序需要的比较次数均为 n(n-1)/2，堆排序需要比较的次数为 O(n1og2n)。可知，在最坏情况下，堆排序的时间复杂度最小，本题的正确答案为选项 D。 【知识模块】 数据结构 6 【正确答案】 D 【试题解析】 假设线性表的长度为 n，在最坏情况下，冒泡排序和快速排序需要的比较次数为 n(n-1)/2。由此
15、可见，选项 D正确。 【知识模块】 数据结构 7 【正确答案】 D 【试题解析】 最好情况下至少需要一趟排序，即比较 n-1次。选项 D为本题正确答案。 【知识模块】 数据结构 8 【正确答案】 D 【试题解析】 直接插入排序的思想是，从序列的第 2个元素开始遍历，每次将遍历的元素插入到其前面序列的适当位置，使该元素及其之前的元素有序。所以， 4趟排序后，原序列的前 5个元素已排序。故本题应该选择 D。 【知识模块】 数据结构 9 【正确答案】 D 【试题解析】 如果初始排列基本有序，则对希尔排序来说，前几趟的插入工作大为减少。冒泡排序和直接插入排序都与初始排序序列有关，只有直接选择排序与初始
16、序列无关。本题正确答案为选项 D。 【知识模块】 数据结构 10 【正确答案】 D 【试题解析】 在排序算法中每一项都与其他诸项进行比较，计算出小于该项的项的个数，以确定该项的位置，这种排序方式是枚举排序，也是选择排序的一种。本题正确答案为选项 D。 【知识模块】 数据结构 11 【正确答案】 C 【试题解析】 在插入排序中，如果待排序列中的最后一个元素其关键字值为最小，则在最后一趟开始之前，前 n-1个排好序的元素都不在其最终位置上，与排好序后的位置相差一个位置。因此，本题正确答案为选项 C。 【知识模块】 数据结构 12 【正确答案】 A 【试题解析】 当待排序列基本有序时： 直接插入排序
17、在待排序列基本有序时，每趟的比较次数大为降低，也即 n-1趟比较的时间复杂度由 O(n2)降至 O(n)。 对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其 “下沉 ”一个位置，要使其下沉到底部仍需 n-1趟排序，也即时间复杂度仍为 O(n2)。 对简单选择排序来说，其比较次数与待排序列的初始状态无关。 归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为 O(n1og2n)。综上所述，本题正确答案为选项 A。 【知识模块】 数据结构 13 【正确答案】 A 【试题解析】 对于选项 A，插入排序是将一个记录插入
18、到已排好序的有序表中，从而得到一个新的、记录数增 1的有序表。本题的正确答案为选项 A。对于选项B，通过 n-i次关键字间的比较，从 n-i+1个记录中选择出关键字 最小的记录，并与第 i个记录交换。对于选项 C，希尔排序是先将整个记录序列分割成若干个子序列，分别进行排序，待整个序列中的记录基本有序时，再对全体记录进行一次排序。对于选项 D，归并排序是将两个或两个以上的有序表组合成一个新的有序表。 【知识模块】 数据结构 14 【正确答案】 A 【试题解析】 根据表 8-1，冒泡排序是稳定的排序方法。在冒泡排序中，相邻元素进行比较，大元素交换到后面，相同元素不交换次序。故本题应该选择 A。 【
19、知识模块】 数据结构 15 【正确答案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，快速排序算法、冒泡排序算法和直接插入排序算法需要的比较次数均为 n(n-1)/2。而堆排序的比较次数为n1og2n。所以，本题应该选择 D。 【知识模块】 数据结构 16 【正确答案】 C 【试题解析】 冒泡排序的基本思想是：将相邻的两个元素进行比较，如果反序，则交换；对于一个待排序的序列，经一趟排序后，最大值的元素移动到最后的位置，其他值较大的元素也向最终位置移动，此过程称为一趟冒泡。对于有 n个数据的序列，共需 n-1趟排序，第 i趟对从 1到 n-i个数据进行比 较、交换。冒泡排序的最坏情
20、况是待排序序列逆序，第 1趟比较 n-1次，第 2趟比较 n-2次，依此类推，最后一趟比较 1次，一共进行 n-1趟排序。因此，冒泡排序在最坏情况下的比较次数是 (n-1)+(n-2)+1 ，结果为 n(n-1)/2。本题的正确答案是选项 C。 【知识模块】 数据结构 17 【正确答案】 A 【试题解析】 对于选项 A，冒泡排序将被排序的记录数组 R1n)垂直排列，每个记录 Ri看作是重量为 ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R凡扫描到违反本原则的轻气 泡，就使其向上 “飘浮 ”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。由此可见，冒泡排序第
21、1趟排序之后，最轻的 “气泡 ”一定会被浮到最上面，即能把数据表中最大或最小元素放在其最终位置上。故本题应该选择 A。对于选项 B，基数排序的基本思想是：从低位到高位依次对待排序的关键码进行分配和收集，经过 d趟分配和收集，就可以得到一个有序序列。所以，基数排序第 1趟排序之后，得到的是以数据表中各元素的个位进行排序的结果，不一定能把数据表中最大或最小元素放在其最终位置上。对于选项 C，快速排序的基本思想是：将原问题 分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序第 1趟排序之后，只能使某个关键元素被插入到一个位置，使得该位置
22、之前的所有元素均小于 (或大于 )关键元素，之后的所有元素均大于 (或小于 )关键元素。所以，也不一定能把数据表中最大或最小元素放在其最终位置上。对于选项 D，归并排序是将两个或两个以上的有序子表合并成一个新的有序表。所以，归并排序第 1趟排序之后，只能得到两两有序的一个序列，并不能把数据表中最大或最小元素放在其最终位置上。 【知识模块】 数据结构 18 【正确答案】 C 【试题解析】 选项 C的说法是错误的。举个反例即可，比如， (1,4,7)的中值是4， (5,6,9)的中值是 6， (10,12,15)的中值是 12。三个中值组为一组 (4,6,12)，其中值为 6。这 9个数字的中值
23、(1,4,5,6,7,9,10,12,15)为 7。 【知识模块】 数据结构 19 【正确答案】 C 【试题解析】 根据题意， f(n)的功能是计算 1+2+n 。因此， f(n-1)=1+2+(n -1)=f(n)-n。所以，当 n =1时， f(n)可以表示为 f(n-1)+n，当 n l时，不妨令f(n)=0。故本题的 4个选项中，只有 C符合题意。 【知识模块】 数据结构 20 【正确答案】 C 【试题解析】 根据题意，总共有 6种分配方案，如表 8-3所示。结果是，在分配方案 4中，乙做工作 P， 12天；丙做工作 Q， 11天；甲做工作 R， 10天。共 33天。所以，本题正确答案
24、为选项 C。 【知识模块】 数据结构 21 【正确答案】 C 【知识模块】 数据结构 22 【正确答案】 E 【试题解析】 交换排序的基本思想是：两两比较 待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。第 1空的正确答案为选项 C。选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。第 2空的正确答案为选项 F。 【知识模块】 数据结构 23 【正确答案】 C 【知识模块】 数据结构 24 【正
25、确答案】 B 【试题解析】 各种排序方法的性能比较如表 8-1所示。由表中可以看出，题目中提供出直接插入排序、冒泡排序和归并排序都是稳定排序。希尔排序是不稳定排序，所以，第 1空的正确答案为选项 C。 快速排序的最坏时间为 O(n2)，对于第 2空，选项 B为正确答案。 【知识模块】 数据结构 25 【正确答案】 C 【知识模块】 数据结构 26 【正确答案】 B 【试题解析】 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字 的记录之间的相对次序发生变化 ，则称这种排序方法是不稳定的。题目选项中，只有
26、 shell排序是不稳定的。第 1空的正确答案为选项 C。 快速排序利用分治法的基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。它的最坏情况是，每次划分选取的基准都是当前无序区中关键字最小 (或最大 )的记录，划分的结果是基准左边的子区间为空 (或右边的子区间为空 )，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做 n-1次划分，第 i次划分开始时区 间长度为 n-i+1，所需的比较次数为 n-i(1in-1)，故总的比较次数达到最大值： Cmax=n(n-1)/
27、2=n2 第 2空的正确答案为选项 B。 【知识模块】 数据结构 27 【正确答案】 C 【知识模块】 数据结构 28 【正确答案】 D 【试题解析】 堆排序是在选择排序的基础上改进而得，所以，第 1空的正确答案为选项 C。对题目中的 4个序列构造完全二叉树，结果如图 8-33所示。根据堆的含义，完全二叉树中，所有非终端结点的值均不大于或者不小于其左右孩子的值。根据这个特点，选项 D中的 56不符合要求。所以，选项 D为正确答案。 【知识模块】 数据结构 29 【正确答案】 A 【知识模块】 数据结构 30 【正确答案】 B 【试题解析】 在正规式中， “|”表示或，头一个括号 (1|3|5)
28、的意思是，第 1个字符是 1或 3或 5，一共 3种情况。第 2个括号 (202)表示，第 2 4个字符一定要是202。最后一个括号 (c|de)表示，最后一部分字符必须是 c或者 de这两种情况。所以，该正则表达式总共可能出现的情况是 312=6种，分别是 1202c、 1202de、3202c、 3202de、 5202c、 5202de。由此可见，第 2空应该选择 B。 【知识模块】 数据结构 31 【正确答案】 (1)j-;(2)i+;(3)Aipivot 或 Ajpivot;(4)A, L, k -1;(5)A, k+1,H 【试题解析】 本题的快速排序思想是：首先，以待排序序列的第
29、 1个元素为基准，将序列中所有小于基准元素的元素排到基准元素的一边，将序列中所有大于基准元素的元素排到基准的另一边。具体放在哪一边，要根据排序的升降而定。这样，就以基准元素为界，将原序列划分成了两个 部分，然后再分别对这两个部分递归进行快速排序，直到无法再划分为止。这样，整个序列就被排序了。 题目中已经给出了快速排序的划分算法，我们要做的就是将划分算法的流程图和 快速排序的递归函数补充完整。 先看来流程图， pivotAlow 就是将数组 A的第 1个元素赋给 pivot，作为基准元素。然后，分别将数组的下界和上界赋给 i和 j(ilow;jhigh) ，我们可以将 i和 j理解为分别指向数组
30、首和尾的两个指针。注意，其中的 i指向的位置是基准元素所在位置。接下来是一个循环，循环条件为 i j。 在 循环体中，首先从后往前寻找比基准元素小的元素，这是通过一个子循环来完成的。循环条件 i j&Aj pivot的意思是，如果 j所指的元素比基准元素大，并且 j还在 i的后面的话，我们应该把 j往前移动 1位，所以第 1空应该填 j-或其他等价形式。如果找到比基准元素小的元素或者 j已经移动到 i的位置了，则循环结束。下面的语句 AiAj 刚就是将找到的元素移动到 i所指位置。注意，现在可以将 j所指位置看作是基准元素的位置，但是可以暂时不用把基准元素赋给Aj。接下来的子循环跟前面的很类似
31、，循环条件是 i j&Ai pivot，如果 i所指元素小于基准元素，且 i并没有超过 j，那么就应该将 i往前移动 1位，所以第 2空应该填 i+或其他等价的形式。直到 i =j(i和 j已经重合，所有元素都遍历完了 )，或者 Ai =pivot(在基准元素位置 j的左边找到比基准元素大的元素了 )，则该子循环结束。然后执行 AjAi ，将找到的元素跟基准元素交换位置，不过基准元素可以暂时不用赋给 Ai，因为它还要跟其他元素交换位置。 如果子循环不是因为 i =j结束的，那么外循环就会继续。直到所有大于基准元素的元素都被排到基准元素后 面，小于基准元素的元素都被排到基准元素前面。外循环结束时
32、， i和 j一定是重合的，现在可以把基准元素写入它们所指的位置中去了。所以，第 3空可以填 Aipivot 或 Ajpivot 。 现在来看快速排序的递归函数 sort()，在函数中首先判断下界 L是否小于上界H，这一点很重要，因为它是递归函数回溯的条件。如果 L H，则表示需排序的元素个数不为 0。在 if子句中，首先调用前面分析过的划分算法 p()函数，将数组A的 L H范围进行一次划分，然后递归调用了两次 sort()。很显然，这两次应该分别对划分出的前半 部分和后半部分分别排序。所以，第 (4)、 (5)空应该分别填A,L, k-1和 A,k+1,H,或者把它们的位置交换也可以。 【知识模块】 数据结构
