56.归并排序中,归并的趟数是( 【南京理工大学2000一、19(1.5分)】 A.0(n) B. o(logn) C. o(nlogn) D.0(n*n) 类似本题的另外叙述有 (1)归并排序的时间复杂性是()。【中山大学1999、12】 A.0(N*N) C. 0(N=*LOG (N)) D. 0(LOG (N)) 57.在排序算法中每一项都与其它各项进行比较,计算出小于该项的项的个数,以确定该 项的位置叫() A.插入排序B.枚举排序C.选择排序D.交换排序【北京邮电大学2000二、6(20/8 分)】 58.就排序算法所用的辅助空间而言,堆排序,快速排序,归并排序的关系是() A.堆排序〈快速排序〈归并排序B.堆排序〈归并排序〈快速排序 C.堆排序〉归并排序〉快速排序D.堆排序〉快速排序〉归并排序 E.以上答案都不对【西安交通大学1996三、1(3分)】 59.排序方法有许多种,(1)法从未排序的序列中依次取出元素,与已排序序列(初始时为 空)中的元素作比较,将其放入已排序序列的正确位置上:(2)法从未排序的序列中挑选元 素,并将其依次放入已排序序列(初始时为空)的一端:交换排序方法是对序列中的元素 进行一系列比较,当被比较的两元素逆序时,进行交换:(3)和(4)是基于这类方法的两 种排序方法,而(4)是比(3)效率更高的方法:(5)法是基于选择排序的一种排序方法 是完全二叉树结构的一个重要应用。【北方交通大学1999一、3(5分)】 (1)一(5):A.选择排序B.快速排序C.插入排序D.起泡排序 归并排序F. shell排序G.堆排序 H.基数排序 类似本题的另外叙述有 (1)排序的方法有很多种,()法从未排序的序列中依次取出元素与已排序序列中的 元素比较,将其放在已排序序列的正确位置上:()法从未排序序列中挑选元素,并将 其依次放入已排序序列的一端;交换排序法是对序列中的元素进行一系列比较,当被比较的 两元素逆序时,进行交换。()和()是基于这类方法的两种排序方法,而() 是比()效率更高的方法。供选择的答案: A.快速排序B.选择排序 归并排序D.冒泡排序E.直接 插入排序 【山东大学1998三、2(5分)】【山东工业大学2000三、2(7分)】 60.设要将序列(q,h,c,y,p,a,m,s,r,d,f,x)中的关键码按字母升序重新排序 (1)()是初始步长为4的 shell排序一趟扫描的结果:(2)()是对排序初始 建堆的结果 (3)()是以第一个元素为分界元素的快速一趟扫描的结果 从下面供选择的答案中选出正确答案填入括号内。【厦门大学2000六、3(16%/3分)】 B. p, a,c,s,q, C. 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 类似本题的另外叙述子 (1)在内排序的过程中,通常需要对待排序的关键码进行多编扫描,采用不同重新排序 方法,会产生不同的排序中间结果。设要将序列<Q,H,C,Y,P,A,M,S,R,D,F,X>中的关键码按字 母序的升序排列,则(1)是冒泡排序一趟扫描的结果,(2)是初始步长为4的希尔 (SHEL排序一趟扫描的结果,(3)是合并排序一趟扫描的结果,(4)是以第一个元 素为分界元素的快速排序一趟扫描的结果,(5)是堆排序初始建堆的结果。供选择的答案
56. 归并排序中，归并的趟数是( )。【南京理工大学 2000 一、19（1.5 分）】 A．O（n） B．O(logn) C．O(nlogn) D．O(n*n) 类似本题的另外叙述有： (1)归并排序的时间复杂性是（ ）。 【中山大学 1999 一、12】 A.O（N*N） B. O（N） C. O（N*LOG（N）） D. O（LOG（N）） 57． 在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该 项的位置叫( ) A．插入排序 B．枚举排序 C．选择排序 D．交换排序【北京邮电大学 2000 二、6 （20/8 分）】 58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 （ ） A．堆排序〈 快速排序〈归并排序 B．堆排序〈 归并排序〈 快速排序 C．堆排序〉 归并排序 〉快速排序 D．堆排序 > 快速排序 > 归并排序 E．以上答案都不对 【西安交通大学 1996 三、1 (3 分)】 59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为 空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元 素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素 进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两 种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法， 是完全二叉树结构的一个重要应用。 【北方交通大学 1999 一、3 （5 分）】 （1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序 E．归并排序 F．shell 排序 G．堆排序 H．基数排序 类似本题的另外叙述有： （1）排序的方法有很多种，（ ）法从未排序的序列中依次取出元素与已排序序列中的 元素比较，将其放在已排序序列的正确位置上；（ ）法从未排序序列中挑选元素，并将 其依次放入已排序序列的一端；交换排序法是对序列中的元素进行一系列比较，当被比较的 两元素逆序时，进行交换。（ ）和（ ）是基于这类方法的两种排序方法，而 ( ) 是比( )效率更高的方法。供选择的答案： A. 快速排序 B. 选择排序 C. 归并排序 D．冒泡排序 E．直接 插入排序 【山东大学 1998 三、2 (5 分)】 【山东工业大学 2000 三、2 （7 分）】 60．设要将序列（q,h,c,y,p,a,m,s,r,d,f,x） 中的关键码按字母升序重新排序， （1）（ ）是初始步长为 4 的 shell 排序一趟扫描的结果； （2）（ ）是对排序初始 建堆的结果； （3）（ ）是以第一个元素为分界元素的快速一趟扫描的结果。 从下面供选择的答案中选出正确答案填入括号内。 【厦门大学 2000 六、3 （16%/3 分）】 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 类似本题的另外叙述有： （1）在内排序的过程中,通常需要对待排序的关键码进行多编扫描,采用不同重新排序 方法,会产生不同的排序中间结果。设要将序列<Q,H,C,Y,P,A,M,S,R,D,F,X>中的关键码按字 母序的升序排列，则( 1 )是冒泡排序一趟扫描的结果,( 2 )是初始步长为 4 的希尔 (SHELL)排序一趟扫描的结果,( 3 ) 是合并排序一趟扫描的结果,( 4 )是以第一个元 素为分界元素的快速排序一趟扫描的结果,( 5 )是堆排序初始建堆的结果。供选择的答案:
【上海海运学院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】
8.在初始数据表已经有序时,快速排序算法的时间复杂度为0(nlog2n)。() 【合肥工业大学2000二、9(1分)】 9.在待排数据基本有序的情况下,快速排序效果最好。()【南京理工大学1997二、 4(2分)】 10.当待排序记录已经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省。 【上海交通大学1998、16】 11.快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。() 【北京邮电大学1998一、7(2分)】 12.堆肯定是一棵平衡二叉树。()【南京航空航天大学1997一、6(1分)】 13.堆是满二叉树。()【南京航空航天大学1996六、6(1分)】 14.(101,88,46,70,34,39,45,58,66,10)是堆。()【北京邮电大学1999二 1(2分)】 15.在用堆排序算法排序时,如果要进行增序排序,则需要采用“大根堆”。( 【合肥工业大学2000二、10(1分)】 16.堆排序是稳定的排序方法。()【上海交通大学1998、19】 17.归并排序辅助存储为0(1)。()【青岛大学2000四、9(1分)】 18.在分配排序时,最高位优先分配法比最低位优先分配法简单。()【上海交通大学1998 19.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间 复杂性是0(n*n),而快速排序算法的最坏时间复杂性是0(nlog2),所以快速排序比冒泡排 序算法效率更高。() 【上海海运学院1997一、9(1分)】 20.交换排序法是对序列中的元素进行一系列比较,当被比较的两个元素逆序时,进行交换, 冒泡排序和快速排序是基于这类方法的两种排序方法,冒泡排序算法的最坏时间复杂性是 0(n湘n),而快速排序算法的最坏时间复杂性是( nlog,n):所以快速排序比冒泡排序效 率更高。() 【上海海运学院1998一、10(1分)】【上海海运学院1995一、10(1分)】 21.快速排序和归并排序在最坏情况下的比较次数都是0( nlog2n)。() 【上海海运学院1996一、9(1分)】 22.在任何情况下,归并排序都比简单插入排序快。()【北京邮电大学2000一、4(1 分)】 23.归并排序在任何情况下都比所有简单排序速度快。()【北京邮电大学2002一、9 (1分)】 24.快速排序总比简单排序快。()【东南大学2001一、9(1分)】 25.中序周游(遍历)平衡的二叉排序树,可得到最好排序的关键码序列。( 【中山大学1994一、4(2分)】 26.外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间 取决于内部排序的时间。()【北京邮电大学1998、8(2分)】 27.在外部排序时,利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的 平均长度为2m个记录。()【上海海运学院1999、10(1分)】 28.为提高在外排序过程中,对长度为N的初始序列进行“置换一选择”排序时,可以得到 的最大初始有序段的长度不超过N/2。() 29.排序速度,进行外排序时,必须选用最快的内排序算法。(
8．在初始数据表已经有序时，快速排序算法的时间复杂度为 O(nlog2n )。（ ） 【合肥工业大学 2000 二、9（1 分）】 9．在待排数据基本有序的情况下，快速排序效果最好。（ ）【南京理工大学 1997 二、 4（2 分）】 10．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 （ ） 【上海交通大学 1998 一、16】 11．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ ） 【北京邮电大学 1998 一、7 （2 分）】 12．堆肯定是一棵平衡二叉树。（ ）【南京航空航天大学 1997 一、6 （1 分）】 13．堆是满二叉树。（ ）【南京航空航天大学 1996 六、6 （1 分）】 14．（101，88，46，70，34，39，45，58，66，10）是堆。（ ）【北京邮电大学 1999 二、 1 （2 分）】 15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ） 【合肥工业大学 2000 二、10（1 分）】 16．堆排序是稳定的排序方法。（ ）【上海交通大学 1998 一、19】 17．归并排序辅助存储为 O（1）。（ ）【青岛大学 2000 四、9（1 分）】 18．在分配排序时，最高位优先分配法比最低位优先分配法简单。（ ）【上海交通大学 1998 一、20】 19．冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间 复杂性是 O(n*n),而快速排序算法的最坏时间复杂性是 O(nlog2 n ),所以快速排序比冒泡排 序算法效率更高。 （ ） 【上海海运学院 1997 一、9（1 分）】 20．交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换， 冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是 O（n*n） ，而快速排序算法的最坏时间复杂性是 O（nlog2n）；所以快速排序比冒泡排序效 率更高。（ ） 【上海海运学院 1998 一、10 （1 分）】【上海海运学院 1995 一、10（1 分）】 21．快速排序和归并排序在最坏情况下的比较次数都是 O(nlog2n)。（ ） 【上海海运学院 1996 一、9（1 分）】 22．在任何情况下，归并排序都比简单插入排序快。（ ）【北京邮电大学 2000 一、4 （1 分）】 23．归并排序在任何情况下都比所有简单排序速度快。（ ）【北京邮电大学 2002 一、9 （1 分）】 24．快速排序总比简单排序快。（ ）【东南大学 2001 一、9 （1 分）】 25. 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（ ） 【中山大学 1994 一、4 （2 分）】 26．外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间 取决于内部排序的时间。( )【北京邮电大学 1998 一、8 （2 分）】 27．在外部排序时，利用选择树方法在能容纳 m 个记录的内存缓冲区中产生的初始归并段的 平均长度为 2m 个记录。( )【上海海运学院 1999 一、10（1 分）】 28．为提高在外排序过程中，对长度为 N 的初始序列进行“置换—选择”排序时，可以得到 的最大初始有序段的长度不超过 N/2。( ) 29．排序速度，进行外排序时，必须选用最快的内排序算法。( )
0.在完成外排序过程中,每个记录的I/0次数必定相等。()【大连海事大学2001一、 20(每题1分)】 31.影响外排序的时间因素主要是内存与外设交换信息的总次数。()【东北大学1997二 5(2分)】 三、填空题 1.若不考虑基数排序,则在排序过程中,主要进行的两种基本操作是关键字的和记 录的 【北京邮电大学2001二、7(4分)】 2.外排序的基本操作过程是 和 。【西安电子科技大学1998二、3(3分)】 类似本题的另外叙述有 (1)外部排序中两个相对独立的阶段是和。【西安电子科技大学1999软件一、8 (2分)】 3.属于不稳定排序的有 【青岛大学2002三、5(2分)】 4.分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为有序的表,则最省时间的 是算法,最费时间的是算法。【福州大学1998二、10(2分)】 类似本题的另外叙述有 (1)设表中元素的初始状态是按健值递增的,分别用堆排序,快速排序,冒泡排序和归并 排序方法对其进行排序(按递增顺序),_排序最省时间,排序最费时间。【厦门大学2001 5(14%/5分)】 5.不受待排序初始序列的影响,时间复杂度为0N2)的排序算法是 在排序算法的最 后一趟开始之前,所有元素都可能不在其最终位置上的排序算法是 【中国人民大学 2001 3(2分)】 6.直接插入排序用监视哨的作用是 【南京理工大学2001二、8(2分)】 7.对n个记录的表r[1.n进行简单选择排序,所需进行的关键字间的比较次数为 【华中理工大学2000一、10(1分)】 8.用链表表示的数据的简单选择排序,结点的域为数据域data,指针域next:链表首 指针为head,链表无头结点 selectsort(head) p=head {q =p;r= while((3) if((4 r=(5) tmp=g->data: g->data=p->data; p->data=tmp: p=(6): }【南京理工大学2000三、2(6分)】 9.下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从 小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式: #include <stdio. h> typedef struct node ( char data; struct node *link; node node *select(node *head) Inode *p, *q, *r,*s p=(node *)malloc(sizeof (node))
30．在完成外排序过程中，每个记录的 I/O 次数必定相等。( )【大连海事大学 2001 一、 20 (每题 1 分)】 31．影响外排序的时间因素主要是内存与外设交换信息的总次数。( )【东北大学 1997 二、 5 (2 分)】 三、填空题 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记 录的_____。 【北京邮电大学 2001 二、7 （4 分）】 2. 外排序的基本操作过程是_______和_______。【西安电子科技大学 1998 二、3 （3 分）】 类似本题的另外叙述有： （1）外部排序中两个相对独立的阶段是___和___。【西安电子科技大学 1999 软件 一、8 （2 分）】 3. 属于不稳定排序的有__________。【青岛大学 2002 三、5 （2 分）】 4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的 是_____算法，最费时间的是______算法。【福州大学 1998 二、10 (2 分)】 类似本题的另外叙述有： （1）设表中元素的初始状态是按健值递增的，分别用堆排序，快速排序，冒泡排序和归并 排序方法对其进行排序（按递增顺序），__排序最省时间，__排序最费时间。【厦门大学 2001 一、5 （14%/5 分）】 5. 不受待排序初始序列的影响，时间复杂度为 O(N2 )的排序算法是_____，在排序算法的最 后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____。【中国人民大学 2001 一、3 （2 分）】 6．直接插入排序用监视哨的作用是_______。【南京理工大学 2001 二、8 （2 分）】 7．对 n 个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。 【华中理工大学 2000 一、10 （1 分）】 8. 用链表表示的数据的简单选择排序，结点的域为数据域 data ，指针域 next ；链表首 指针为 head ，链表无头结点。 selectsort(head) p=head; while (p(1)_______) {q=p; r=(2)_______ while((3)______ ) {if ((4)_______ ) q=r; r=(5)_______ ; } tmp=q->data; q->data=p->data; p->data=tmp; p= (6)_______ ; } 【南京理工大学 2000 三、2 （6 分）】 9．下面的 c 函数实现对链表 head 进行选择排序的算法,排序完毕,链表中的结点按结点值从 小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式： #include <stdio.h> typedef struct node {char data; struct node *link; }node; node *select(node *head) {node *p,*q,*r,*s; p=(node *)malloc(sizeof(node));
p->link=head head=p while(p->link!=null) if (q->link->data<r->link->data)r=g g=q->link if((2))(s=r->link; r->link=s->link; s->link=((3));((4)): (5) p=head; head=head->link; free(p); return(head) }【复旦大学1999六(15分)】 10.下面的排序算法的思想是:第一趟比较将最小的元素放在r[1]中,最大的元素放在r[n] 中,第二趟比较将次小的放在r[2]中,将次大的放在r[n-1]中,…,依次下去,直到待排 序列为递增序。(注:<->)代表两个变量的数据交换) void sort(Sqlist &r, int n) t while((1))i for(j=i+1;(2) if(3) min=j: else if(r[j]. key>r [max]. key) max=j if((4) >rail if(max!=n-i+)if((5))r[min]<->r[n-i+1; else((6)) i++ }//sort【南京理工大学2001三、2(10分)】 11.表插入排序的基本思想是在结点中设一指针字段,插入Ri时Rl到Ri-1己经用指针按 排序码不减次序链结起夹,这时采用顺序比较的方法找到Ri应插入的位置,做链表插入。 如此反复,直到把Rn插入为止。 (1)(6分)请完成下列表插人的算法【山东工业大学2000五(16分)】【山东大学1998 ①.R[O].LINK←(1;R[N.LIN←(2 ②.循环,I以-1为步长,从(3)到(4)执行 (1)P←R[O].LIN;Q-0 (2)循环,当P>0且(⑤5)时,反复执行 (3)R[Q].LINK←I;R[I].LINK←P (2)(2分)表插入排序的最大比较次数是(7) (3)(2分)表插入排序的最小比较次数是(8) (4)(2分)记录移动的次数是(9) (5)(2分)需要附加的存储空间是(10 (6)(2分)该排序算法是否是稳定的(11)
p->link=head; head=p; while(p->link!=null) {q=p->link; r=p; while ((1)____) { if (q->link->data<r->link->data) r=q; q=q->link; } if ((2)____) {s=r->link; r->link=s->link; s->link= ((3)_____); ((4)_____);} ((5)____) ; } p=head; head=head->link; free(p); return(head); } 【复旦大学 1999 六（15 分）】 10．下面的排序算法的思想是：第一趟比较将最小的元素放在 r[1]中，最大的元素放在 r[n] 中，第二趟比较将次小的放在 r[2]中，将次大的放在 r[n-1]中，…,依次下去，直到待排 序列为递增序。（注：<-->）代表两个变量的数据交换）。 void sort(SqList &r,int n) { i=1; while((1)__) { min=max=1; for (j=i+1;(2)____ ;++j) {if((3)____) min=j; else if(r[j].key>r[max].key) max=j; } if((4)_____) r[min] < ---- >r[j]; if(max!=n-i+1){if ((5)___) r[min] < ---- > r[n-i+1]; else ((6)__); } i++; } }//sort 【南京理工大学 2001 三、2 （10 分）】 11．表插入排序的基本思想是在结点中设一指针字段，插入 Ri 时 Rl 到 Ri-1 己经用指针按 排序码不减次序链结起夹，这时采用顺序比较的方法找到 Ri 应插入的位置，做链表插入。 如此反复，直到把 Rn 插入为止。 （1）(6 分)请完成下列表插人的算法；【山东工业大学 2000 五（16 分）】【山东大学 1998 五】 ①. R[0].LINK←(1)___; R[N].LINK←(2)___; ②. 循环，I 以-1 为步长，从(3)___到(4)___执行 （1）P← R[0].LINK; Q← 0 （2）循环，当 P>0 且(5)__ 时，反复执行 Q←P； P←(6)___ （3）R[Q].LINK←I; R[I].LINK←P （2）(2 分) 表插入排序的最大比较次数是(7)__； （3）（2 分）表插入排序的最小比较次数是(8)__； （4）（2 分）记录移动的次数是(9)__； （5）（2 分）需要附加的存储空间是(10)__； （6）（2 分）该排序算法是否是稳定的(11)____