排序算法 - Problem Detail - lizikid

ID: 14

Type: Objective

Difficulty: 8

Uploaded By:

Tags>

初赛选择题

体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 {{ select(1) }}

快速排序
插入排序
冒泡排序
归并排序

以下排序算法中，不需要进行关键字比较操作的算法是（）。 {{ select(2) }}

基数排序
冒泡排序
堆排序
直接插入排序

排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的（）：。 {{ select(3) }}

冒泡排序
插入排序
归并排序
快速排序

快速排序最坏情况下的算法时间复杂度为（）： {{ select(4) }}

$O(log_2^n)$
$O(n)$
$(nlog_2^n)$
$O(n^2)$

快速排序平均情况和最坏情况下的算法时间复杂度分别为（）： {{ select(5) }}

平均情况 $O(nlog_2^n)$ ，最坏情况 $O(n^2)$
平均情况 $O(n)$ ，最坏情况 $O(n^2)$
平均情况 $O(n)$ ，最坏情况 $O(nlog_2^n)$
平均情况 $O(log_2^n)$ ，最坏情况 $O(n^2)$

如果不在快速排序中引入随机化，有可能导致的后果是（）。 {{ select(6) }}

数组访问越界
陷入死循环
排序结果错误
排序时间退化为平方级

基于比较的排序时间复杂度的下限是（），其中n表示待排序的元素个数。 {{ select(7) }}

$O(n)$
$O(n log ^n)$
$O(log ^n)$
$O(n^2)$

（）的平均时间复杂度为 $O(n log^n)$ ，其中n是待排序的元素个数。 {{ select(8) }}

快速排序
插入排序
冒泡排序
基数排序

以下时间复杂度不是 $O(n^2)$ 的排序方法是（）。 {{ select(9) }}

插入排序
归并排序
冒泡排序
选择排序

对于给定的序列 ${a_k}$ ，我们把 $(i, j)$ 称为逆序对当且仅当 $i < j$ 且 $a_i > a_j$ 。那么序列1, 7, 2, 3, 5, 4 的逆序对数为（）个。 {{ select(10) }}

4
5
6
7

使用冒泡排序对序列进行升序排序，每执行一次交换操作将会减少 1 个逆序对，因此序列5,4, 3, 2, 1需要执行（）次交换操作，才能完成冒泡排序。 {{ select(11) }}

0
5
10
15

设A 和B 是两个长为n 的有序数组，现在需要将A 和B 合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（）次比较。 {{ select(12) }}

$n^2$
$nlog^n$
$2n$
$2n-1$