搜索
第十章作业一、选择题1.排序算法的稳定性是指()。A.经过排序后，能使值相同的数据保持原顺序中的相对位置不变B.经过排序后，能使值相同的数据保持原顺序中的绝对位置不变C.经过排序后，数据序列的存放数组的结构保持不变D.经过排序后，数据序列的存放数组的结构随之变化2.若要求在最坏情况下也能尽快地对序列进行稳定的排序，则应选()。A.起泡排序B.快速排序C.归并排序D.堆排序3.每次从未排序的序列中取出一个元素与已排序的序列中的元素依次进行比较，然后把它插入到已排序序列中的适当位置，此种排序方法叫做()A.起泡排序B.直接插入排序C.简单选择排序D.二路归并排序4.对5个不同数据元素做直接插入排序，其数据比较次数最多是()。A.8B.10C.15D.255.直接插入排序在最好情况下的时间复杂度是()A.)(log2nOB.)(nOC.)log(2nnOD.)(2nO6.每次直接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法是()A.堆排序B.选择排序C.起泡排序D.基数排序7.一个元素序列的排序码为{46,79,56,38,40,84}，采用快速排序(以第一个元素为枢轴)得到的第一次划分结果为()A.{38,46,79,56,40,84}B.{38,79,56,46,40,84}C.{40,38,46,79,56,84}D.{38,46,56,79,40,84}8.每次从待排序序列中挑选从一个最小或最大元素，吧它们交换到该序列的最前端，此种排序方法是()。A.起泡排序B.直接插入排序C.简单选择排序D.二路归并排序9.堆是一种有用的数据结构。在以下排序码序列中小顶堆是()。A.{16,72,31,23,94,53}B.{94,53,31,72,16,53}C.{16,53,23,94,31,72}D.{16,31,23,94,53,72}10.向具有n个元素的堆中插入一个新元素的时间复杂度为()。A.)1(OB.)(nOC.)log(2nOD.)log(2nnO11.从具有n个元素的堆中删除一个元素的时间复杂度为()。A.)1(OB.)(nOC.)log(2nOD.)log(2nnO12.在用二叉树实现的应用中，从任意结点出发到根的路径上所经过的结点序列是按其排序码有序的，这样的树是()。A.完全二叉树B.AVL树C.堆D.二叉排序树13.下列排序算法中最坏情况下的时间代价不高于)log(2nnO的是()。A.插入排序B.归并排序C.快速排序D.希尔排序14.下列算法中不稳定的算法是()。A.起泡排序B.直接插入排序C.基数排序D.快速排序15.以下不属于内排序方法的是()。A.起泡排序B.拓扑排序C.基数排序D.快速排序二、应用题16.设待排序的排序码序列为{12,2,16,30,28,10,16*,20,6,18}，试写出使用希尔排序(增量为5,2,1)方法每趟排序后的结果，并说明做了多少次排序码比较。17.设待排序的排序码序列为{38,07,72,12,43,65,62,88,31,27,15,54}，试给出使用快速排序算法(以第一个元素为枢轴)每一趟排序结束时的排序码状态。18.设待排序的排序码序列为{12,2,16,30,10,16*,15,6}，试写出使用堆排序进行从小到大排序，每趟排序后的结果。19.如果只想得到一个序列中第K个最小元素之前的部分排序序列，那么最好应采用哪种排序算法？为什么？如由这样一个序列：57,40,38,11,13,34,48,75,25,6,19,9,7得到其第3个最小元素之前的部分排序序列：6,7,9,用你选用算法实现时，共执行多少次比较？