习题七 参考答案
一、选择题
  1.内部排序算法的稳定性是指(  D  )
  A.该排序算法不允许有相同的关键字记录
  B.该排序算法允许有相同的关键字记录
  C.平均时间为0n log n)的排序方法
二叉树中序遍历非递归算法  D.以上都不对
2.下面给出的四种排序算法中,(  B  )是不稳定的排序。
  A.插入排序      B.堆排序        C.二路归并排序      D.冒泡排序
3. 在下列排序算法中,哪一种算法的时间复杂度与初始排序序列无关()。
  A.直接插入排序  B.冒泡排序      C.快速排序    D.直接选择排序
4.关键字序列(89104562012)只能是下列排序算法中( C  )的两趟排序后的结果。
  A.选择排序      B.冒泡排序          C.插入排序      D.堆排序
5.下列排序方法中,(  D    )所需的辅助空间最大。
  A.选择排序      B.希尔排序      C.快速排序    D.归并排序
6.一组记录的关键字为(467956384084),则利用快速排序的方法,以第一个记录为支点得到的一次划分结果为()。
  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.在对一组关键字序列{7055100153365504095},进行直接插入排序时,把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.Next());
            r.setNext(p);
            p = u;
//P结点链入链表中,rq的前驱,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) {  //交换pr
                Node swap = r.getNext();
                r.Next().getNext());  //rnext指向其后继的后继
                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--) {

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。