数据结构（山东联盟-青岛大学）章节测试课后答案2024春

第九章测试

1.每次从未排序的序列中取出一个元素与已排序的序列中的元素依次进行比较，然后把它插入到已排序序列中的适当位置，此种排序方法叫做（       ）排序。
A:简单选择排序        B:起泡排序        C:直接插入排序        D:二路归并排序
答案:C
2.对5个不同的数据元素进行直接插入排序，最多需要进行（     ）次比较。
A:10 B:15 C:25 D:8 3.有一种排序方法，如果最小的元素位于待排序序列的最后，则在最后一趟排序开始之前，所有元素都不在其最终位置上，这种排序方法是（    ）。
A:快速排序 B:起泡排序        C:简单选择排序        D:直接插入排序        4.每次直接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做（ ）排序。
A:堆排序            B:冒泡排序        C:基数排序 D:选择排序        5.每次从待排序序列中挑选出一个最小或最大元素，把它交换到该序列的最前端，此种排序方法叫做（     ）排序。
A:起泡排序        B:直接插入排序        C:简单选择排序        D:二路归并排序 6.在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将序列{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（    ）是冒泡排序一趟扫描的结果。
A:deng,an,tang,shi,bai,fang,li,wan B:deng,tang,an,wan,bai,shi,fang,li C:deng,tang,an,wan,bai,shi,li,fang D:an,deng,bai,li,shi,tang,fang,wan 7.在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（    ）是初始步长为4的希尔排序一趟扫描的结果。
A:li,deng,an,shi,bai,fang,tang,wan B:an,tang,deng,wan,shi,bai,fang,li C:shi,bai,an,li,tang,deng,fang,wan D:an,bai,deng,fang,li,shi,tang,wan  8.在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（    ）是以第一个元素为分界元素的快速排序一趟扫描的结果。
A:deng,an,tang,shi,bai,fang,li,wan    B:li,deng,an,shi,bai,fang,tang,wan C:shi,bai,an,li,tang,deng,fang,wan D:deng,tang,an,wan,bai,shi,fang,li 9.一个元素序列的关键字为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的元素为基准）得到的第一次划分结果为（    ）。
A:{40,38,46,79,56,84} B:{38,46,56,79,40,84} C:{38,79,56,46,40,84} D:{38,46,79,56,40,84}   10.在快速排序中，要使最坏情况下的空间复杂度为O(log2n)，要对快速排序做（  ）修改。
A:先排小子区间                      B:采用链表排序 C:划分轴点为三者取中            D:先排大子区间 11.在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{ tang, deng, an, wan, shi, bai,fang, li }中的关键字按升序排列，则（    ）是大根堆排序初始建堆的结果。
A:wan, tang, fang, li, shi, bai, an, deng B:an, tang, deng, wan, shi, bai, fang, li C:an, bai, deng, fang, li, shi, tang, wan D:deng, tang, an, wan, bai, shi, fang, li 12.堆是一种有用的数据结构。例如关键字序列（    ）就是一个小根堆。
A:94, 53, 31, 72, 16, 53 B:16, 53, 23, 94, 31, 72 C:16, 72, 31, 23, 94, 53   D:16, 31, 23, 94, 53, 72 13.向具有 n 个结点的堆中插入一个新元素的时间复杂度为（    ）。
A:O(log2n) B:O(n) C:O(1) D:O(nlog2n) 14.在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（    ）是二路归并排序一趟扫描的结果。
A:deng,tang,an,wan,bai,shi,li,fang B:deng,tang,an,wan,bai,shi,fang,li C:deng,an,tang,shi,bai,fang,li,wan   D:an,deng,bai,li,shi,tang,fang,wan 15.将两个各有m个元素的有序序列归并成一个有序序列，关键字比较次数最少为（      ）。
A:m B:2m-1 C:m-1 D:2m 16.排序算法的稳定性是指（）。
A:经过排序后，数据序列的存放数组的结构随之变化 B:经过排序后，数据序列的存放数组的结构保持不变 C:经过排序后，能使值相同的数据保持原顺序中的绝对位置不变 D:经过排序后，能使值相同的数据保持原顺序中的相对位置不变 17.若要求在最坏情况下也能尽快地对序列进行稳定的排序，则应选（）。
A:堆排序 B:归并排序 C:快速排序 D:冒泡排序 18.设一个待排序序列为{92,83,77,64,54,43,38,27,15},将该序列排好序经过了16次关键字比较，使用的排序方法是（ ）。
A:简单选择排序 B:冒泡排序 C:折半插入排序 D:直接插入排序 19.对序列{27,21,15,18,41,7,12}用希尔排序法进行排序， 经过一趟排序后，序列变为{27,7,12,18,41,21,15 }，那么这一趟采用的增量是（）。
A:2 B:4 C:3 D:5 20.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需执行的关键字比较次数是（ ）。
A:15 B:10 C:3 D:25 21.若元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序方法只能是（ ） 。
A:二路归并排序 B:选择排序 C:插入排序 D:冒泡排序 22.从一个具有 n 个元素的堆中删除一个元素的时间复杂度为（）。
A:O(logn) B:O(n) C:O(1) D:O(nlogn) 23.对由n个元素所组成的序列按关键字排序时，二路归并排序算法，所需要的辅助存储是（）。
A:O(n) B:O(logn) C:O(nlogn) D:O(1) 24.下列排序算法中，最坏情况下的时间代价不高于 O(nlogn)的是（）。
A:归并排序 B:快速排序 C:堆排序 D:插入排序 25.如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么下列排序算法中，排序速度最快的算法是（）。
A:快速排序 B:基数排序 C:希尔排序 D:归并排序