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

．在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动从而认为该排序算法是不稳定的这种说法对吗？为什么？【燕山大学 三 (分)】

．设有个互不相同的元素abcde能否通过次比较就将其排好序？如果能请列出其比较过程;如果不能则说明原因【北方交通大学 五(分)】

．对一个由n个关键字不同的记录构成的序列能否用比n少的次数选出该序列中关键字取最大值和关键字取最小值的记录？请说明如何实现？在最坏的情况下至少进行多少次比较？【东南大学 一 (分)】

．利用比较的方法进行排序在最坏的情况下能达到的最好时间复杂性是什么？请给出详细证明【上海交通大学 六 (分)】

．以下概念的区别拓扑排序与冒泡排序【大连海事大学 三 () (分)】

．简述直接插入排序简单选择排序路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别【西北工业大学 二 (分)】

．快速排序堆排序和希尔排序是时间性能较好的排序方法也是稳定的排序方法判断正误并改错【燕山大学 二 (分)】

设LS是一个线性表LS=(aa…an)若采用顺序存储结构则在等概率的前提下插入一个元素需要平均移动的元素个数是多少？若元素插在ai与ai+之间(<=i<=n)的概率为(ni)/(n*(n+)/)则插入一个元素需要平均移动的元素个数又是多少？【西安电子科技大学 软件 二 (分)】

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