哈尔滨工程大学考研-数据结构-10.doc

一、选择题1下面给出的四种排序法中,( )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆积2下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序 3下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A 冒泡 B. 希尔 C. 快速 D. 堆 4. 就平均性能而言，目前最好的内排序方法是( )排序法。A. 冒泡 B. 希尔插入 C. 交换 D. 快速 5. 下列排序算法中，占用辅助空间最多的是：( ) 。A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序二、判断题1当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。2内排序要求数据一定要以顺序方式存储。 3在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。4在待排数据基本有序的情况下，快速排序效果最好。5堆排序是稳定的排序方法。三、填空题1若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_。2分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。3. 在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_。4. 用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为head ，链表无头结点。selectsort(head) p=head;while (p(1)_)q=p; r=(2)_ while(3)_ )if (4)_ ) q=r; r=(5)_ ; tmp=q->data; q->data=p->data; p->data=tmp; p= (6)_ ; 5下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：#include <stdio.h>typedef struct node char data; struct node *link; node;node *select(node *head)node *p,*q,*r,*s; p=(node *)malloc(sizeof(node); p->link=head; head=p;while(p->link!=null) q=p->link; r=p; while (1)_) if (q->link->data<r->link->data) r=q; q=q->link; if (2)_) s=r->link; r->link=s->link; s->link= (3)_); (4)_); (5)_) ; p=head; head=head->link; free(p); return(head); 四、应用题1简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。2对下列关键字序列进行快速排序(从小至大) (48, 38, 65, 95, 73, 13, 27, 50)要求给出快速排序的算法思想,并画出排序过程示意图。 3对于输入关键字序列48，70，65，33，24，56，12，92进行： 建立堆排序的初始堆（小顶堆），要求画出主要过程。 建一棵平衡二叉树，画出过程（至少每次调整有一张，标出最小不平衡子树的根）。4给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列； (1) 希尔排序（第一趟排序的增量为5） (2) 快速排序（选第一个记录为枢轴（分隔）(3) 链式基数排序（基数为10）