习题七参考答案
一、选择题
1.内部排序算法的稳定性是指( D )。
A.该排序算法不允许有相同的关键字记录
B.该排序算法允许有相同的关键字记录
C.平均时间为0(n log n)的排序方法
D.以上都不对
2.下面给出的四种排序算法中,( B )是不稳定的排序。
A.插入排序B.堆排序C.二路归并排序D.冒泡排序
3. 在下列排序算法中,哪一种算法的时间复杂度与初始排序序列无关(D )。
A.直接插入排序B.冒泡排序C.快速排序D.直接选择排序4.关键字序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中( C )的两趟排序后的结果。
A.选择排序 B.冒泡排序 C.插入排序 D.堆排序5.下列排序方法中,( D )所需的辅助空间最大。
A.选择排序B.希尔排序C.快速排序D.归并排序6.一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为支点得到的一次划分结果为( C )。
A.(38,40,46,56,79,84) B.(40,38,46,79,56,84)
C.(40,38,46,56,79,84) D.(40,38,46,84,56,79)
7.在对一组关键字序列{70,55,100,15,33,65,50,40,95},进行直接插入排序时,把65插入,需要比较( A)次。
A. 2
B. 4
C. 6
D. 8
8.从待排序的序列中选出关键字值最大的记录放到有序序列中,该排序方法称为( B )。
A. 希尔排序
B. 直接选择排序
C. 冒泡排序
D. 快速排序
9.当待排序序列基本有序时,以下排序方法中,( B )最不利于其优势的发挥。
A. 直接选择排序
B. 快速排序
C.冒泡排序
D.直接插入排序
10.在待排序序列局部有序时,效率最高的排序算法是( B )。
A. 直接选择排序
B. 直接插入排序
C. 快速排序
D.归并排序
二、填空题
1.执行排序操作时,根据使用的存储器可将排序算法分为内排序和外排序。
2.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时,当把第7个记录
60插入到有序表中时,为寻找插入位置需比较 3 次。
3.在直接插入排序和直接选择排序中,若初始记录序列基本有序,则选用直接插入排
序。
4.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时,第4次交换和选
择后,未排序记录为{50,70,60,95,80}。
5.n个记录的冒泡排序算法所需的最大移动次数为3n(n-1)/2 ,最小移动次数为
0 。
6.对n个结点进行快速排序,最大的比较次数是n(n-1)/2 。
7.对于堆排序和快速排序,若待排序记录基本有序,则选用堆排序。
8.在归并排序中,若待排序记录的个数为20,则共需要进行5 趟归并。
9.若不考虑基数排序,则在排序过程中,主要进行的两种基本操作是关键字的比较
和数据元素的移动。
10.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的是快速排序,需要内存容量最多的是基数排序。
三、算法设计题
1.试设计算法,用插入排序方法对单链表进行排序。
参考答案:
public static void insertSort(LinkList L) {
Node p, q, r, u;
p = L.getHead().getNext();
L.getHead().setNext(null);
//置空表,然后将原链表结点逐个插入到有序表中
while (p != null) { //当链表尚未到尾,p为工作指针
r = L.getHead();
q = L.getHead().getNext();
while (q != null && (Integer.parseInt((String) q.getData())) <= (Integer.parseInt((String) p.getData()))) {
//查P结点在链表中的插入位置,这时q是工作指针
r = q;
q = q.getNext();
}
u = p.getNext();
p.setNext(r.getNext());
r.setNext(p);
p = u;
//将P结点链入链表中,r是q的前驱,u是下一个待插入结点的指针
}
}
2.试设计算法,用选择排序方法对单链表进行排序。
参考答案:
//单链表选择排序算法
public static void selectSort(LinkList L) {
//p为当前最小,r为此过程中最小,q为当前扫描接点
Node p, r, q;
Node newNode = new Node();
newNode.setNext(L.getHead());
L.setHead(newNode);
//制造一个最前面的节点newNode,解决第一个节点的没有前续节点需要单独语句的问题。
p = L.getHead();
while (p.getNext().getNext() != null) {
r = p.getNext();
q = p.getNext().getNext();
while (q.getNext() != null) {
if (Integer.parseInt((String) q.getNext().getData()) <= (Integer.parseInt((String) r.getNext().getData()))) {
r = q;
}
q = q.getNext();
}
if (r != p) { //交换p与r
Node swap = r.getNext();
r.setNext(r.getNext().getNext()); //r的next指向其后继的后继
swap.setNext(p.getNext());
p.setNext(swap); //p的后继为swap
}
p = p.getNext();
}//while
p.setNext(null);
}
3.试设计算法,实现双向冒泡排序(即相邻两遍向相反方向冒泡)。
参考答案:
//产生随机数方法
public static int[] random(int n) {
if (n > 0) {
int table[] = new int[n];
for (int i = 0; i < n; i++) {
table[i] = (int) (Math.random() * 100);
//产生一个0~100之间的随机数
}
return table;
}
return null;
}
//输出数组元素方法
public static void print(int[] table)
{
if (table.length > 0) {
for (int i = 0; i < table.length; i++) {
System.out.print(table[i] + " ");
}
System.out.println();
}
}
//双向冒泡排序方法
public static void dbubblesort(int[] table) {
int high = table.length;
int left = 1;
int right = high - 1;
int t = 0;
do {
//正向部分
for (int i = right; i >= left; i--) {
if (table[i] < table[i - 1]) {
int temp = table[i];
table[i] = table[i - 1];
table[i - 1] = temp;
t = i;
}
}
left = t + 1;
//反向部分
for (int i = left; i < right + 1; i++) {
if (table[i] < table[i - 1]) {
int temp = table[i];
table[i] = table[i - 1];
table[i - 1] = temp;
t = i;
}
}
right = t - 1;
} while (left <= right);
}
4.试设计算法,使用非递归方法实现快速排序。
参考答案:
public static void NonrecursiveQuickSort(int[] ary) { if (ary.length < 2) {
return;
}
//数组栈:记录着高位和低位的值
int[][] stack = new int[2][ary.length];
//栈顶部位置
int top = 0;
//低位,高位,循环变量,基准点
//将数组的高位和低位位置入栈
stack[1][top] = ary.length - 1;
stack[0][top] = 0;
top++;
//要是栈顶不空,那么继续
while (top != 0) {
//将高位和低位出栈
//低位:排序开始的位置
top--;
int low = stack[0][top];
//高位:排序结束的位置
int high = stack[1][top]; //将高位作为基准位置
//基准位置
int pivot = high;
int i = low;
for (int j = low; j < high; j++) {
if (ary[j] <= ary[pivot]) {
int temp = ary[j];
ary[j] = ary[i];
ary[i] = temp;
i++;
}
}
//如果i不是基准位,那么基准位选的就不是最大值
//而i的前面放的都是比基准位小的值,那么基准位
//的值应该放到i所在的位置上
if (i != pivot) {
int temp = ary[i];
ary[i] = ary[pivot];
ary[pivot] = temp;
}
if (i - low > 1) {
//此时不排i的原因是i位置上的元素已经确定了,i前面的都是比i小的,i后面的都是比i大的
stack[1][top] = i - 1;
stack[0][top] = low;
top++;
}
//当high-i小于等于1的时候,就不往栈中放了,这就是外层while循环能结束的原因
//如果从i到高位之间的元素个数多于一个,那么需要再次排序
if (high - i > 1) {
//此时不排i的原因是i位置上的元素已经确定了,i前面的都是比i小的,i后面的都是比i大的
stack[1][top] = high;
stack[0][top] = i + 1;
top++;
}
}
}
5.试设计算法,判断完全二叉树是否为大顶堆。
参考答案:
boolean checkmax(BiTreeNode t) //判断完全二叉树是否为大顶堆 {
BiTreeNode p = t;
if (p.getLchild() == null && p.getRchild() == null) {
return true;
} else {
if (p.getLchild() != null && p.getRchild() != null) {
if ((((RecordNode)
p.getLchild().getData()).getKey()).compareTo(((RecordNode)
p.getData()).getKey()) <= 0 && (((RecordNode)
p.getRchild().getData()).getKey()).compareTo(((RecordNode)
p.getData()).getKey()) <= 0) {
return checkmax(p.getLchild()) &&
checkmax(p.getRchild());
} else
{
return false;
}
} else if (p.getLchild() != null && p.getRchild() == null) { if ((((RecordNode)
p.getLchild().getData()).getKey()).compareTo(((RecordNode)
p.getData()).getKey()) <= 0) {
return checkmax(p.getLchild());
} else
{
return false;
}
} else if (p.getLchild() == null && p.getRchild() != null) { if ((((RecordNode)
p.getRchild().getData()).getKey()).compareTo(((RecordNode)
p.getData()).getKey()) <= 0) {
return checkmax(p.getRchild());
} else
{
return false;
}
} else {
return false;
}
}
}
四、上机实践题
1. 编写程序,对直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序和归并排序进行测试。
参考答案:
package ch07Exercise;
import ch07.*;
import java.util.Scanner;
public class Exercise7_4_1 {
public static void main(String[] args) throws Exception {
int[] d = {52, 39, 67, 95, 70, 8, 25, 52};
int[] dlta = {5, 3, 1}; //希尔排序增量数组
int maxSize = 20; //顺序表空间大小
SeqList L = new SeqList(maxSize); //建立顺序表
for (int i = 0; i < d.length; i++) {
RecordNode r = new RecordNode(d[i]);
L.insert(L.length(), r);
}
System.out.println("排序前:");
L.display();
System.out.println("请选择排序方法:");
System.out.println("1-直接插入排序");
System.out.println("2-希尔排序");
System.out.println("3-冒泡排序");
System.out.println("4-快速排序");
System.out.println("5-直接选择排序");
System.out.println("6-堆排序");
System.out.println("7-归并排序");
Scanner s = new Scanner(System.in);
int xz = s.nextInt();
switch (xz) {
case 1:
L.insertSort();
break; //直接插入排序
case 2:
L.shellSort(dlta);
break; //希尔排序
case 3:
L.bubbleSort();
break; //冒泡排序 case 4:
L.quickSort();
break; //快速排序
case 5:
L.selectSort();
break; //直接选择排序 case 6:
L.heapSort(); //堆排序
break;
case 7:
L.mergeSort(); //归并排序
break;
}
System.out.println("排序后:");
L.display();
}
}
运行结果:
2.编写程序,对带监视哨的直接插入排序进行测试。参考答案:
package ch07Exercise;
import ch07.RecordNode;
import ch07.SeqList;
public class Exercise7_4_2 extends SeqList {
public Exercise7_4_2(int maxSize) {
super(maxSize);
}
public void display() { //输出数组元素
for (int i = 1; i < length(); i++) {
System.out.print(" " + getRecord()[i].getKey().toString()); }
System.out.println();
}
public static void main(String[] args) throws Exception {
int[] d = {52, 39, 67, 95, 70, 8, 25, 52};
int maxSize = 20; //顺序表空间大小
SeqList L = new Exercise7_4_2(maxSize); //建立顺序表
RecordNode r = new RecordNode(0);
L.insert(L.length(), r);
for (int i = 0; i < d.length; i++) {
r = new RecordNode(d[i]);
L.insert(L.length(), r);
}
System.out.println("排序前:");
L.display();
L.insertSortWithGuard();
System.out.println("排序后:");
L.display();
}
}
运行结果:
3.编写程序,要求随机生成10000个数,并比较直接插入排序、直接选择排序、冒泡排序、快速排序和堆排序的排序性能。
参考答案:
package ch07Exercise;
import ch07.*;
public class Exercise7_4_3 {
static int maxSize = 10000; //排序关键码个数
public static void main(String[] args) throws Exception {
int[] d = new int[maxSize]; //顺序表空间大小
for (int i = 0; i < maxSize; i++) {
d[i] = (int) (Math.random() * 100);
}
SeqList L;
L = createList(d);
System.out.println("直接插入排序所需时间:" + testSortTime(L, 'i') + "毫秒");
L = createList(d);
System.out.println("冒泡排序所需时间:" + testSortTime(L, 'b') + "毫秒"); L = createList(d);
System.out.println("快速排序所需时间:" + testSortTime(L, 'q') + "毫秒"); L = createList(d);
System.out.println("直接选择排序所需时间:" + testSortTime(L, 's') + "毫秒");
L = createList(d);
System.out.println("堆排序所需时间:" + testSortTime(L, 'h') + "毫秒"); }
private static SeqList createList(int[] d) throws Exception {
SeqList L = new SeqList(maxSize); //建立顺序表
for (int i = 0; i < d.length; i++) {
RecordNode r = new RecordNode(d[i]);
L.insert(L.length(), r);
}
return L;
}
public static long testSortTime(SeqList L, char sortmethod) {
long startTime, endTime, testTime;
startTime = System.currentTimeMillis();
switch (sortmethod) {
case 'i':
L.insertSort();
break;
case 's':
L.selectSort();
break;
case 'b':
L.bubbleSort();
break;
case 'q':
L.quickSort();
break;
case 'h':
L.heapSort();
break;
}
endTime = System.currentTimeMillis(); testTime = endTime - startTime;
return testTime;
}
}
运行结果: