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

．对由n个记录所组成的表按关键码排序时下列各个常用排序算法的平均比较次数分别是:二路归并排序为( )直接插入排序为( )快速排序为( )其中归并排序和快速排序所需要的辅助存储分别是( )和( ) 【上海海运学院 二 (分)】

:A O() B O(nlogn) C O(n) D O(n) E O(n(logn)) F O(logn)

．将两个各有N个元素的有序表归并成一个有序表其最少的比较次数是( )【中科院计算所 二 (分)】 【中国科技大学 二 (分)】

A．N B．N C．N D．N

基于比较方法的n个数据的内部排序最坏情况下的时间复杂度能达到的最好下界是( )【南京理工大学 一 (分)】

A O(nlogn) B O(logn) C O(n) D O(n*n)

．已知待排序的n个元素可分为n/k个组每个组包含k个元素且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素若采用基于比较的排序其时间下界应为( )【中国科技大学 二 (分)】

A O(nlogn) B O(nlogk) C O(klogn) D O(klogk)

类似本题的另外叙述有

()已知待排序的N个元素可分为N/K个组每个组包含K个元素且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素若采用基于比较的排序其时间下界应为( )【中科院计算所 二 (分)】

A O(klogk) B O(klogn) C O(nlogk) D O(nlogn)

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