第10章 排序.doc

第十章习题参考答案一、简答题：1【参考答案】 ：排序使数据更加清晰，方便阅读，有利于进行数据的统计分析，排序应用：图书列表查阅，提高数据检索速度（如索引）2【参考答案】 ：冒泡排序是待排序序列中的元素相邻的两个数据进行比较，满足条件时进行交换，每一趟完成，序列中最大（最小）的数据被调整到最上面的位置，类似水中的冒泡，因此称作冒泡排序。3【参考答案】 ：快速排序的基本思想是：待排序的n个元素中任取一个元素，以该元素的关键字作为排序的标准，将所有元素分为两组，对于比标准关键字小或者相等的元素，放在标准元素的左边一组，比关键字大的放在关键字右边，即为一趟快速排序。4【参考答案】 ：可以，因为未发生交换说明没有满足条件的数据存在，表明数据已经按照预期的效果排序。5【参考答案】 ：希尔排序是直接插入排序的改进，直接插入排序对打数据量排序效率较低6【参考答案】 ：归并排序法思想：如果待排序序列中又n个记录，设这n个记录分别都是有序的，然后进行归并，将相邻的有序子序列归并成一个新的有序子序列，再将有序子序列继续归并，该过程循环进行，直至整个序列有序7【参考答案】 ：如图：8【参考答案】 ：（以降序为例）输出33，12置顶336975325612输出85，33置顶7533325669调整堆输出75，12置顶调整堆输出69，12置顶调整堆85697532561233初始堆121233325669693332125612333256563312321输出56，12置顶563312321调整堆1233321输出33，12置顶331232112321输出32，12置顶32121调整堆32121最后输出1212排序顺序为：85 75 69 56 33 32 12二、实验题1算法：【参考答案】 ： private LinkNode insert(LinkNode link, LinkNode ln) if(link.getData() ln.getData() ln.setNext(link); link = ln; return link; LinkNode node = link; LinkNode tmp = node.getNext(); while(tmp!=null) if(tmp.getData()ln.getData() node.setNext(ln); ln.setNext(tmp); return link; tmp = tmp.getNext(); node = node.getNext(); node.setNext(ln); return link; public LinkNode insertSort() LinkNode link = head; LinkNode node = head.getNext(); LinkNode node1 = node.getNext(); link.setNext(null); while(node != null) node.setNext(null); insert(link, node); node = node1; if(node1!=null) node1 = node1.getNext(); head = link; return link; 2该题目中所有算法可参见教材：【参考答案】 ：序号排序方法算法1希尔排序参见P2292归并排序参见P2373快速排序参见P 2324堆排序参见P 2365插入排序参见P 238三、思考题1该题所使用的算法可参考教材：【参考答案】 ：序号排序方法算法1冒泡排序参见P2302插入排序参见P23