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

已知某文件的记录关键字集为{}选择一种从平均性能而言是最佳的排序方法进行排序且说明其稳定性【西安电子科技大学 五 (分)】

在内排序算法中待排序的数据已基本有序时花费时间反而最多的排序方法是哪种？【西安电子科技大学 计应用 一 (分)】

．我们知道对于n个元素组成的线性表进行快速排序时所需进行的比较次数与这n个元素的初始排序有关问【西安电子科技大学 计应用 五(分)】【中国矿业大学 六 (分)】

() 当n=时在最好情况下需进行多少次比较？请说明理由

() 当n=时给出一个最好情况的初始排序的实例

() 当n=时在最坏情况下需进行多少次比较？请说明理由

() 当n=时给出一个最坏情况的初始排序的实例

类似本题的另外叙述有

() 快速排序(quick sorting)的效率与原始序列有关现用快速排序算法对关键字分别为—的 个元素进行排序

① 在最好情况下要进行几遍比较给出一种原始序列实例;

② 在最坏情况下要进行几遍比较给出一种原始序列实例【浙江大学 七(分)】

() 对N个元素组成的线性表进行快速排序时所需进行的比较次数依赖于这N个元素的初始排列对N=给出快速排序的一个最好情况的初始排列实例(个元素可取自集合{l})【西北大学 二(分)】

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