第7章排序习题参考答案
- 格式:doc
- 大小:29.51 KB
- 文档页数:3
习题七参考答案
一、选择题
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 = ().getNext();
().setNext(null);
etNext();
while (q != null && ((String) ())) <= ((String) ()))) {
etNext() != null) {
r = ();
q = ().getNext();
while () != null) {
if ((String) ().getData()) <= ((String) ().getData()))) {
r = q;
}
q = ();
}
if (r != p) { etNext()); etData()).getKey())pareTo(((RecordNode) ()).getKey())
<= 0 && (((RecordNode) ().getData()).getKey())pareTo(((RecordNode) ()).getKey()) <= 0) { return checkmax()) && checkmax());
} else
{
return false;
}
} else if () != null && () == null) {
if ((((RecordNode) ().getData()).getKey())pareTo(((RecordNode) ()).getKey())
<= 0) {
return checkmax());
} else
{
return false;
}
} else if () == null && () != null) {
if ((((RecordNode) ().getData()).getKey())pareTo(((RecordNode) ()).getKey())
<= 0) {
return checkmax());
} else
{
return false;
}
} else {
return false;
}