[单项选择]

以下关于快速排序算法的描述中，错误的是 (104) 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素(12，25，30，45，52，67，85)构成，则初始排列为 (105) 时，排序效率最高(令序列的第一个元素为基准元素)。

105（）
A. 45，12，30，25，67，52，85
B. 85，67，52，45，30，25，12
C. 12，25，30，45，52，67，85
D. 45，12，25，30，85，67，52

[单项选择]

以下关于快速排序算法的描述中，错误的是 (104) 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素(12，25，30，45，52，67，85)构成，则初始排列为 (105) 时，排序效率最高(令序列的第一个元素为基准元素)。

（104）处填（）。
A. 快速排序算法是不稳定的排序算法
B. 快速排序算法在最坏情况下的时间复杂度为O(nlgn)
C. 快速排序算法是一种分治算法
D. 当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度

[单项选择]快速排序算法采用的设计方法是（）。
A. 动态规划法
B. 分治法
C. 回溯法
D. 分枝定界法

[单项选择]为实现快速排序算法，待排序列适合采用______。
A. 顺序存储
B. 链式存储
C. 散列存储
D. 索引存储

[多项选择]快速排序算法中，如何选取一个界值(又称为轴元素)，影响着快速排序的效率，而且界值也并不一定是被排序序列中的一个元素。例如，可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。

[填空题]对于输人的N个数进行快速排序算法的平均时间复杂度是 【1】 。

[单项选择]在Excel中，以下关于排序顺序，描述正确的是( )。
A. 先按主要关键字排序，然后再重新按次要关键字排序
B. 按主要关键字排序，次要关键字无效
C. 次要关键字字段按照次要关键字排序，其他字段按主要关键字排序
D. 先按主要关键字排序，当主要关键字的数值相同时，再按次要关键字排序

[单项选择]以下关于加密算法与解密算法的描述中，哪项是错误的______。
A. 加密算法是相对稳定的
B. 解密算法所使用的密钥称为解密密钥
C. 对密文解密时采用的一组规则称为解密算法
D. 加密算法一定要做好保密工作

[多项选择]【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot时，采用从left、right和mid=[(left+right)/2]中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为T，left和right是待排序子区间的最左端点和最右端点。
void quicksort (int a[], int left, int right)
int temp;
if (left＜right)
hat pivot = median3 (a, left, right); //三者取中子程序
int i = left, j = right-1;
for(;;)
while (i ＜j && a[i] ＜ pivot) i++;
while (i ＜j && pivot ＜ a[j]) j--;
if(i＜j)
temp = a[i]; a[j] = a[i]; a[i] = temp;
i++; j--;

else break;

if (a[i] ＞ pivot)
temp = a[i]; a[i] = a[right]; a[right] = temp;
quicksort( (1) ); //递归排序左子区间
quieksort(a,i+1 ,right); //递归排序右子区间
void median3 (int a[], int left, int right)
int mid= (2) ;
int k = left;
if(a[mid] ＜ a[k])k = mid;
if(a[high] ＜ a[k]) k = high; //选最小记录
int temp = a[k]; a[k] = a[left]; a[left] = temp; //最小者交换到 left
if(a[mid] ＜

[简答题]
阅读以下算法说明，根据要求回答问题1～问题3。

[问题2] (1)假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度(用 O记号)。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。 (2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况 (7) 。 (最佳、平均、最坏)

[简答题]【说明】
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。
1．分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组 (可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1)中的每个元素，小于 A[q+1..r]中的每个元素。q的值在划分过程中计算。
2．递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。
3．合并：快速排序在原地排序，故不需合并操作。
【问题1】
下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。
A：待排序数组
p，r: 数组元素下标，从p到r
q: 划分的位置
x：枢轴元素
i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值
j：循环控制变量，表示数组元素下标
QUICKSORT (A，p，r){
if (p ＜r){
q=PARTITION(A，p，r) ；
QUICKSORT(A，p，q-1)；
QUICKSORT(A，q+1，r)；
}
}
PARTITION(A，p，r){
x=A[r]；i=p-1；
for(j=p；j≤r-1；j++){
if (A[j]≤x){
i=i+1；
交换A[i]和A[j]
}
}
交 (1) 和 (2) //注：空(1)和空(2)答案可互换，但两空全部答对方可得分 return (3)
}