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

《哈尔滨工程大学考研-数据结构-10.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题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、了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。2．内排序要求数据一定要以顺序方式存储。3．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。4．在待排数据基本有序的情况下，快速排序效果最好。5．堆排序是稳定的排序方法。三、填空题1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。2．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。3.在排序算法的最后一趟开始之前，所有元素都可

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进行选择排序的算法,排序完毕,链表中的结

4、点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：#includetypedefstructnode{chardata;structnode*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->datalink->data

5、)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．对于输入关键字

6、序列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）