数据结构第10章作业VIP免费

第10 章排序作业 作业一： 1） 对人意的7 个关键字进行排序，至少要进行_______次关键字之间的两两比较。 A. 13 B.11 C.15 D.16 E.19 【参考答案】C 【解题思路】任何一个借助“比较”进行排序的算法，在最坏的情况下所需进行得比较次数至少为[)!(log2 n ]。[)!7(log2]=15。 2） 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_________。 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 【参考答案】C 【解题思路】插入排序的思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排序的序列中的适当位置。直到全部的记录插入完成为止。 3） 对记录的关键字为{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为： 50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90 其使用的排序方法是_________。 A. 快速排序 B. 希尔排序 C.基数排序 D.归并排序 【参考答案】B 【解题思路】由排序的结果直接可以确知（即使不知道其他几中排序方法）该排序是增量序列为5,3,1的希尔排序。 4） 已知序列{70，83，100，65，10，32，7，9},请给出采用插入排序法对该序列作升序排序时的每一趟的结果。 【参考答案】采用插入排序方法排序的各趟的结果如下： 初始：（70），83，100，65，10，32，7，9 第一趟：（70，83）， 100，65，10，32，7，9 第二趟：（70，83，100），65，10，32，7，9 第三趟：（65，70，83，100），10，32，7，9 第四趟：（10，65，70，83，100），32，7，9 第五趟：（10，32，65，70，83，100），7，9 第六趟：（7，10，32，65，70， 83，100），9 第七趟：（7，9，10，32，65，70，83，100） 作业二： 1） 快速排序方法在_____情况下最不利于发挥其长处。 A. 要排序的数据量太大 B.要排序的数据中含有多个相同值 C.要排序的数据已基本有序 D.要排序的数据个数为奇数 【参考答案】C 【解题思路】要排序的数据（个数为n）已基本有序，采用快速排序则需要n-1趟，其时间复杂度升至O(n2)。 2） 用快速排序方法对线性表(24,84,20,47,15,26,68,35,19)进行排序时，写出元素序列的变化情况： 【参考答案】 （1）24,84,20,47,15,26,68,35,19 （2）19,1...