第二章测试1.假设对N个元素进行归并排序，则需要的归并操作的次数约为（ ）。
A:logN B:N/2 C:N D:NlogN
答案:A
2.假设要从2000个元素中得到10个最小元素，最好采用（ ）。
A:插入排序 B:快速排序 C:归并排序 D:堆排序
答案:D
A:{10, 3, 8, 16, 22, 24, 18} B:{3, 8, 10, 16, 18, 22, 24} C:{10, 8, 3, 16, 24, 22, 18} D:{8, 3, 10, 16, 24, 18, 22}
答案:C
自然的归并排序。编写一个自底向上的归并排序，当需要将两个子数组排序时能够利用数组中已经有序的部分。首先找到一个有序的子数组（移动指针直到当前元素比上一个元素小为止），然后再找出另一个并将它们归并。
public class MergeBUN {
//GetIndex函数功能： 从index[1]开始记录第二个自然分组以及之后每个自然分组的"开始下标"
private static int GetIndex(Comparable[] a, int[] a_index)
{
int j = 0;
a_index[j++] = 0; //第一个自然分组开始下标默认为0
for(int i = 0; i < a.length-1; i++) {
if(less(a[i+1],a[i])) {
a_index[j++] = i+1;
}
}
//j为自然分组的个数
return ( ？ );
}
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public static void sort(Comparable[] a) {
int n = a.length;
Comparable[] aux = new Comparable[n];
int[] index=new int[n];
int num = GetIndex(a,index); //识别数组中的自然分组
int mergeNum=num; //保存自然分组的个数
for (int i = 2; i/2 < num; i*=2) { //
int count=0;
int j=0;
for (int temp = 0; temp < mergeNum/2; temp++) { //内循环次数是分组个数除以2的整数部分，如分组个数为5，则内循环2次
int lo=index[j]; //记录归并起始位
int mid = index[j+i/2]-1; //记录两个归并分组中第一个分组的最后一位
int hi =0;
if(j+i>num-1) hi=a.length-1;
else hi=index[j+i]-1; //记录两个归并分组中第二个分组的最后一位
merge(a, aux, lo, mid, hi);
count++; //记录每次内循环完成的归并次数
j=j+i;
}
mergeNum=mergeNum-count; //得到剩余需要归并的分组个数
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i]);
}
}
public static void main(String[] args) {
String[] a = {"D","R","T","E","X","A","M","C","L","B","O","R","T","E","X","A","M","G","L","A","M","I","L" };
MergeBUN.sort(a);
show(a);
}
}
A:
a_index
B:a C:i D:j答案:D
找出最小元素。在 MaxPQ中加入一个min()方法。你的实现所需的时间和空间都应该是常数。
public class MaxPQ<Key> implements Iterable<Key> {
private Key[] pq;
private int n;
private key min;
……
public void insert(Key x) {
if (n == pq.length - 1) resize(2 * pq.length);
if(isEmpty()) min=x;
else if(((Comparable<Key>)x).compareTo(min)<0) min=x;
pq[( ？ )] = x;
swim(n);
}
public Key delMax() {
if (isEmpty()) return null;
if(n==1) min=null;
Key max = pq[1];
exch(1, n--);
sink(1);
pq[n+1] = null;
if ((n > 0) && (n == (pq.length - 1) / 4))
resize(pq.length / 2);
return max;
}
public Key getMin(){
return min;
}
……
}
A:其他选项均不正确 B:n++ C:++n D:n
答案:C
