数据结构 Java语言版 教学课件 王学军习题答案 第10章 排序.doc

《数据结构 Java语言版 教学课件 王学军习题答案 第10章 排序.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第十章习题参考答案一、简答题：1．【参考答案】：排序使数据更加清晰，方便阅读，有利于进行数据的统计分析，排序应用：图书列表查阅，提高数据检索速度（如索引）2．【参考答案】：冒泡排序是待排序序列中的元素相邻的两个数据进行比较，满足条件时进行交换，每一趟完成，序列中最大（最小）的数据被调整到最上面的位置，类似水中的冒泡，因此称作冒泡排序。3．【参考答案】：快速排序的基本思想是：待排序的n个元素中任取一个元素，以该元素的关键字作为排序的标准，将所有元素分为两组，对于比标准关键字小或者相等的元素，放在标准元素的左边一组，比关键字大的放在关键字右边，即为一趟快速排序。4．【参考答案】：可以，因为未

2、发生交换说明没有满足条件的数据存在，表明数据已经按照预期的效果排序。5．【参考答案】：希尔排序是直接插入排序的改进，直接插入排序对打数据量排序效率较低6．【参考答案】：归并排序法思想：如果待排序序列中又n个记录，设这n个记录分别都是有序的，然后进行归并，将相邻的有序子序列归并成一个新的有序子序列，再将有序子序列继续归并，该过程循环进行，直至整个序列有序7．【参考答案】：如图：8．【参考答案】：（以降序为例）输出33，12置顶336975325612输出85，33置顶7533325669调整堆输出75，12置顶调整堆输出69，12置顶调整堆85697532561233初始堆12123332

3、5669693332125612333256563312321输出56，12置顶563312321调整堆1233321输出33，12置顶331232112321输出32，12置顶32121调整堆32121最后输出1212排序顺序为：85756956333212二、实验题1．算法：【参考答案】：privateLinkNodeinsert(LinkNodelink,LinkNodeln){if(link.getData()>ln.getData()){ln.setNext(link);link=ln;returnlink;}LinkNodenode=link;LinkNodetmp=node

4、.getNext();while(tmp!=null){if(tmp.getData()>ln.getData()){node.setNext(ln);ln.setNext(tmp);returnlink;}tmp=tmp.getNext();node=node.getNext();}node.setNext(ln);returnlink;}publicLinkNodeinsertSort(){LinkNodelink=head;LinkNodenode=head.getNext();LinkNodenode1=node.getNext();link.setNext(null);whil

5、e(node!=null){node.setNext(null);insert(link,node);node=node1;if(node1!=null)node1=node1.getNext();}head=link;returnlink;}2．该题目中所有算法可参见教材：【参考答案】：序号排序方法算法1希尔排序参见P2292归并排序参见P2373快速排序参见P2324堆排序参见P2365插入排序参见P238三、思考题1．该题所使用的算法可参考教材：【参考答案】：序号排序方法算法1冒泡排序参见P2302插入排序参见P2383快速排序参见P2322．该题所使用的算法可参考教材：【参考答案

6、】：序号排序方法算法1希尔排序参见P2292选择排序参见P2333堆排序参见P236