数据结构第十章考试题库(含答案)[精品].doc

第10章 排序 一、选择题 1．某内排序方?法的稳定性?是指( )。 【南京理工大?学 1997 一、10（2分）】 A．该排序算法?不允许有相?同的关键字?记录 B．该排序算法?允许有相同?的关键字记?录 C．平均时间为?0（n log n）的排序方法? D．以上都不对? 2．下面给出的?四种排序法?中( )排序法是不?稳定性排序?法。【北京航空航?天大学 1999 一、10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算?法中，其中（ ）是稳定的。 【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排?序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序?方法是（ ） 【北方交通大?学 2000 二、3（2分）】 A．直接插入排?序和快速排?序 B．折半插入排?序和起泡排?序 C．简单选择排?序和四路归?并排序 D．树形选择排?序和she?ll排序 5．下列排序方?法中，哪一个是稳?定的排序方?法？（ 　） 【北方交通大?学 2001 一、8（2分）】 A．直接选择排?序 B．二分法插入?排序 C．希尔排序 D．快速排序 6．若要求尽可?能快地对序?列进行稳定?的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。 【北京邮电大?学 2001 一、5（2分）】 7．如果待排序?序列中两个?数据元素具?有相同的值?，在排序前后?它们的相互?位置发生颠?倒，则称该排序?算法是不稳?定的。（ ）就是不稳定?的排序方法?。【清华大学 1998 一、3 (2分）】 A．起泡排序 B．归并排序 C．Shell?排序 D．直接插入排?序 E．简单选择排?序 8．若要求排序?是稳定的，且关键字为?实数，则在下列排?序方法中应?选（ ）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数 【中科院计算?所 2000 一、5（2分）】 9．若需在O(nlog2?n)的时间内完?成对数组的?排序，且要求排序?是稳定的，则可选择的?排序方法是?（ ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排?序 【中国科技大?学 1998 二、4（2分）】 【中科院计算?所 1998 二、4（2分）】 10．下面的排序?算法中，不稳定的是?（ ） 【北京工业大?学 1999 一、2 (2分)】 A.起泡排序 B.折半插入排?序 C.简单选择排?序 D.希尔排序 E.基数排序 F.堆排序。 11．下列内部排?序算法中： 【北京工业大?学 2000 一 、1 (10分 每问2分)】 A．快速排序 B.直接插入排?序 C. 二路归并排?序 D. 简单选择排?序 E. 起泡排序 F. 堆排序 （1） 其比较次数?与序列初态?无关的算法?是（ ） （2）不稳定的排?序算法是（ ） （3）在初始序列?已基本有序?（除去n个元?素中的某k?个元素后即?呈有序，kn）的情况下，排序效率最?高的算法是?（ ） （4）排序的平均?时间复杂度?为O(n?logn)的算法是（ ）为O(n?n)的算法是（ ） 12．排序趟数与?序列的原始?状态有关的?排序方法是?( )排序法。【北京航空航?天大学 1999 一、9（2分）】 A．插入 B. 选择 C. 冒泡 D. 快速 13．下面给出的?四种排序方?法中，排序过程中?的比较次数?与排序方法?无关的是。( ) A．选择排序法? B. 插入排序法? C. 快速排序法? D. 堆积排序法? 【北京航空航?天大学 2000 一、10（2分）】 14．对下列四种?排序方法，在排序中关?键字比较次?数同记录初?始排列无关?的是( )。 A．直接插入 B. 二分法插入? C. 快速排序 D. 归并排序 【南京理工大?学 2000 一、7 （1.5分）】 15．在下列排序?算法中,哪一个算法?的时间复杂?度与初始排?序无关（ ）。【北京理工大?学 2001 六、4 （2）】