习题七 参考答案
一、选择题
A．该排序算法不允许有相同的关键字记录
B．该排序算法允许有相同的关键字记录
C．平均时间为0（n log n）的排序方法
D．以上都不对
2．下面给出的四种排序算法中，( B )是不稳定的排序。
A．插入排序 B．堆排序 C．二路归并排序 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
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.Next());
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.Head());
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.Next().getNext()); //r的next指向其后继的后继
swap.Next());
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--) {
发布评论