数据结构考研分类复习真题 第十章 排序[56]

．给定一个关键字序列{}请写出快速排序第一趟的结果;堆排序时所建的初始堆;归并排序的全过程然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？【西安电子科技大学 五(分)】

．奇偶交换排序如下所述对于初始序列A[]A[]…A[n]第一趟对所有奇数i(<=i<n)将A[i]和A[i+]进行比较若A[i]>A[i+]则将两者交换;第二趟对所有偶数i(<=i<n)将A[i]和A[i+]进行比较若A[i]>A[i+]则将两者交换;第三趟对所有奇数i(<=i<n);第四趟对所有偶数i(<=i<n)…依次类推直至到整个序列有序为止

() 分析这种排序方法的结束条件

() 写出用这种排序方法对进行排序时每一趟的结果【山东科技大学 四(分)】

．设某文件经内排序后得到个初始归并段(初始顺串)若使用多路归并排序算法并要求三趟归并完成排序问归并路数最少为多少？【山东大学 一(分)】【东南大学一(分)】

．证明置换选择排序法产生的初始归并段的长度至少为m(m是所用缓沖区的长度)【西安电子科技大学 二 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []