【上海海运学院1997二、3(5分)】 1-5: A. f, h, c, d, p, a, m, g, r, s, y, X B. p, a, c, s, g, d, f, x, r, h, m, y a, d, c, r, f, g, m, s, y, p, h, x D. h, c, g , p, a, m, s, r, d, f, X,y E. h, g, c, y, a, p, m, s, d, r, f, x 61.对由n个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别 是:二路归并排序为(1),直接插入排序为(2),快速排序为(3),其中,归并排 序和快速排序所需要的辅助存储分别是(4)和(5)。【上海海运学院1998二 4(5分)】 1-5:A.0(1)B.0(nlog2n)C.0(n)D.0(n2)E.0(n(log2n)2)F.0(logn) 62.将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是() B.2N-1 【中科院计算所 7(2分)】【中国科技大学1998 (2分)】 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是 A.0( nlogn)B.0(logn)C.0(m)D.0(m*n)【南京理工大学1996一、2(2分)】 64.已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均 分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其 时间下界应为()。 A.0 logan)B.o( logik)C.0( logan)D.0(klog2k)【中国科技大学1998二、 9(2分)】 类似本题的另外叙述有 (1)已知待排序的N个元素可分为NK个组,每个组包含K个元素,且任一组内的各元素 均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时 间下界应为() A.0(klog2k)B.0(klog2n)C.0(nlog2k)D.0(nlog2n)【中科院计算所1998二、9(2 分)】 65.采用败者树进行k路平衡归并的外部排序算法,其总的归并效率与k 有关 无关【北京工业大学2000一、2(3分)】 66.采用败者树进行K路平衡归并时,总的(包括访外)归并效率与K()。 A.有关 B.无关【北京工业大学2001一、4(2分)】 判断题: 1.当待排序的元素很大时,为了交换元素的位置,移动元素要占用较多的时间,这是影响 时间复杂度的主要因素。()【长沙铁道学院1998一、10(1分)】 2.内排序要求数据一定要以顺序方式存储。()【南京理工大学1997二、2(2分)】 3.排序算法中的比较次数与初始元素序列的排列无关。()【南京航空航天大学1997 8(1分)】 4.排序的稳定性是指排序算法中的比较次数保持不变,且算法能够终止。() 【南京航空航天大学1996六、9(1分)】 5.在执行某个排序算法过程中,出现了排序码朝着最终排序序列位置相反方向移动,则该 算法是不稳定的。()【上海交通大学1998一、18】 6.直接选择排序算法在最好情况下的时间复杂度为0(N)。()【合肥工业大学2001二 10(1分)】 7.两分法插入排序所需比较次数与待排序记录的初始排列状态相关。(X上海交通大学1998 、15】【上海海运学院 1997 二、3 （5 分）】 1-5:A. f,h,c,d,p,a,m,q,r,s,y,x B. p,a,c,s,q,d,f,x,r,h,m,y C. a,d,c,r,f,q,m,s,y,p,h,x D. h,c,q,p,a,m,s,r,d,f,x,y E. h,q,c,y,a,p,m,s,d,r,f,x 61．对由 n 个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别 是:二路归并排序为( 1 ),直接插入排序为( 2 ),快速排序为( 3 ),其中,归并排 序和快速排序所需要的辅助存储分别是( 4 )和( 5 )。 【上海海运学院 1998 二、 4 （5 分）】 1-5:A. O(1) B. O（nlog2n） C. O（n） D. O（n 2） E. O（n(log2n)2） F. O（log2n） 62．将两个各有 N 个元素的有序表归并成一个有序表,其最少的比较次数是( ) A．N B．2N-1 C．2N D．N-1 【中科院计算所 1998 二、7 （2 分）】 【中国科技大学 1998 二、7 （2 分）】 63. 基于比较方法的 n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是 （ ）。 A. O(nlogn) B. O(logn) C. O(n) D. O(n*n) 【南京理工大学 1996 一、2 （2 分）】 64．已知待排序的 n 个元素可分为 n/k 个组，每个组包含 k 个元素，且任一组内的各元素均 分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其 时间下界应为（ ）。 A. O(nlog2n) B. O(nlog2k) C. O(klog2n) D. O(klog2k) 【中国科技大学 1998 二、 9 （2 分）】 类似本题的另外叙述有： (1)已知待排序的 N 个元素可分为 N/K 个组，每个组包含 K 个元素，且任一组内的各元素 均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时 间下界应为( ) A. O(klog2k) B. O(klog2n) C. O(nlog2k) D. O(nlog2n) 【中科院计算所 1998 二、9 （2 分）】 65．采用败者树进行 k 路平衡归并的外部排序算法，其总的归并效率与 k （ ） A． 有关 B．无关 【北京工业大学 2000 一 、2 (3 分)】 66．采用败者树进行 K 路平衡归并时，总的（包括访外）归并效率与 K（ ）。 A．有关 B．无关 【北京工业大学 2001 一、4 (2 分)】 二、判断题： 1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响 时间复杂度的主要因素。（ ）【长沙铁道学院 1998 一、10 (1 分)】 2．内排序要求数据一定要以顺序方式存储。 （ ）【南京理工大学 1997 二、2（2 分）】 3．排序算法中的比较次数与初始元素序列的排列无关。（）【南京航空航天大学 1997 一、 8 （1 分）】 4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 【南京航空航天大学 1996 六、9 （1 分）】 5．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该 算法是不稳定的。（ ）【上海交通大学 1998 一、18】 6．直接选择排序算法在最好情况下的时间复杂度为 O（N）。（ ）【合肥工业大学 2001 二、 10（1 分）】 7．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）【上海交通大学 1998 一、15】