单元测验10
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就【没】有实用价值。
（√）（2）希尔排序是不稳定的排序。
（ㄨ）（3）冒泡排序是【不】稳定的排序。
（√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。
（ㄨ）（5）堆排序所需的时间与待排序的记录个数【无】有关。
（√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。
（ㄨ）（7）快速排序不是在任何情况下都比其它排序方法速度快。
（√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。
（√）（9）采用归并排序可以实现外排序。
（√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高
（√）（11）快速排序算法在每一趟排序中都能到一个元素放在其最终位置上。
（√）（12）冒泡排序的时间复杂度是O（n2）。
二．填空题
（1） 大多数排序算法都有两个基本的操作：  比较  和移动。
（2） 评价排序算法优劣的主要标准是    时间复杂度    和算法所需的附加空间。
（3） 根据被处理的数据在计算机中使用不同的存储设备，排序可分为：  内排序  和外排序。
（4） 外排序是指在排序过程中，数据的主要部分存放在计算机的  外存  中。
（5） 对n个关键字进行冒泡排序，其可能的最小比较次数为：  n-1  次。
（6） 在最坏情况下，在第i趟直接插入排序中，要进行  i-1  次关键字的比较。
（7） 对n个关键字进行冒泡排序，时间复杂度为  O(n2)  。
（8） 快速排序在最坏情况下的时间复杂度是  O(n2)  。
（9） 对于n数据结构与算法分析答案个记录的集合进行归并排序，所需要的平均时间为：  O(log2n)  。
（10） 对于n个记录的集合进行归并排序，所需要的附加空间是    O(n)  。
（11） 若原始数据接近无序，则选用    快速排序    最好。
（12） 在排序前，关键字值相等的不同记录，排序后相对位置保持  不变   的排序方法，称为稳定排序方法。
（13） 在插入排序和选择排序中，若初始数据基本正序，则选用    插入排序    较好。
（14） 当增量为1时，该趟希尔排序与  直接插入  排序基本一致。
（15） 第一趟排序后，序列中键值最大的记录交换到最后的排序算法是    冒泡排序    。
（16） 依次将每个记录插入到一个有序的子文件中的排序方法称为    直接插入    排序。
（17） 在插入排序、选择排序和归并排序中，排序是不稳定的为：    选择排序    。
（18） 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻插入位置需比较  3  次。
（19） 两个序列分别为：
  L1={25，57，48，37，92，86，12，33}
  L2={25，37，33，12，48，57，86，92}。
  用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：  L2  。
（20）对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是  54，72，60，96，80  。
三．选择题
（1）排序是根据（  A  ）的大小重新安排各元素的顺序。
    A．关键字          B．数组            C．元素件          D．结点
（2）评价排序算法好坏的标准主要是（  D  ）。
A．执行时间                          B．辅助空间
C．算法本身的复杂度                  D．执行时间和所需的辅助空间
（3）直接插入排序的方法是（  B  ）的排序方法。
    A．不稳定          B．稳定            C．外部            D．选择
（4）直接插入排序的方法要求被排序的数据（  B  ）存储。
    A．必须链表        B．必须顺序        C．顺序或链表      D．可以任意
（5）排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为 (  D  )。
    A．希尔排序        B．归并排序        C．插入排序        D. 选择排序
（6）每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（  C  ）。
A．冒泡排序        B．堆排序          C．快速排序        D. 归并排序
（7）快速排序在（  C  ）情况下最易发挥其长处。
A．待排序的数据中含有多个相同的关键字 B．待排序的数据已基本有序
C．待排序的数据完全无序              D．待排序的数据中最大值与最小值相差悬殊
（8）下述几种排序方法中，要求内存量最大的是：（  D  ）。
    A．插入排序        B．选择排序        C．快速排序        D. 归并排序
（9）直接插入排序的方法是从第（  B  ）个元素开始，插入到前边适当位置的排序方法。
    A．1              B．2              C．3              D．n
（10）堆的形状是一棵（  C  ）。
A．二叉排序树      B．满二叉树        C．完全二叉树      D．平衡二叉树
（11）内排序是指在排序的整个过程中，全部数据都在计算机的（  A  ）中完成的排序。
    A．内存            B．外存            C．内存和外存      D．寄存器
（12）快速排序的方法是（  A  ）的排序方法。
    A．不稳定          B．稳定            C．外部            D．选择
（13）下列排序方法中，关键字比较次数与记录的初始排列次序无关的是（  A ）。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。