资源描述：
《第7章-排序-习题参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、习题七参考答案一、选择题 1．内部排序算法的稳定性是指(D)。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（nlogn）的排序方法 D．以上都不对2．下面给出的四种排序算法中，(B)是不稳定的排序。 A．插入排序 B．堆排序 C．二路归并排序 D．冒泡排序3.在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D）。 A．直接插入排序B．冒泡排序 C．快速排序 D．直接选择排序4．关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(C)的两趟排序后的结果。
2、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}，进行直接插入排
3、序时，把65插入，需要比较(A)次。A.2B.4C.6D.88.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为(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,
4、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.在归并排序中，若
5、待排序记录的个数为20，则共需要进行5趟归并。9.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据元素的移动。10．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是快速排序，需要内存容量最多的是基数排序。三、算法设计题1．试设计算法，用插入排序方法对单链表进行排序。参考答案:publicstaticvoidinsertSort(LinkListL){Nodep,q,r,u;p=L.getHead().getNext();L.getHead().setNext(null);//置空表，然后将原链
6、表结点逐个插入到有序表中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.setNext(r.getNext());r.setNext(p);p=u;//将P结点链入链表
7、中，r是q的前驱，u是下一个待插入结点的指针}}2．试设计算法，用选择排序方法对单链表进行排序。参考答案://单链表选择排序算法publicstaticvoidselectSort(LinkListL){//p为当前最小,r为此过程中最小,q为当前扫描接点Nodep,r,q;NodenewNode=newNode();newNode.setNext(L.getHead());L.setHead(newNode);//制造一个最前面的节点newNode，解决第一个节点的没有前续节点需要单独语句的问题。p=L.getHead();while(p.getNext().g
8、etNex
