数据�l�构�W�五章应用题及答案[7]_跨考网

1. 设数�l?/span>A的长度�ؓ2N�Q�前N个元�?/span>A[1..N]递减有序�Q�后N个元�?/span>A[N+1.. 2N]递增有序�Q�且2N�?/span>2的整数次�q�，�?/span>k=log22N为整数。例�?/span>A[1..8]=[90,85,50,10,30,65,80,100]满��上述要求�Q�这�?/span>N=4,k=3,A的前4个元素和�?/span>4个元素分别递减和递增有序。用此例调用如下�?/span>Demo�q�程�Q��ƈ要求�Q?/span>

　　�Q?/span>1�Q�给�?/span>for循环中每�ơ执�?/span>PerfectShuffle�Q?/span>A,N�Q�和CompareExchange�Q?/span>A,N�Q�的�l�果�Q?/span>

　　�Q?/span>2�Q�解�?/span>Demo的功能；

　　�Q?/span>3�Q�给�?/span>Demo的时间复杂度�?/span>

　　PROCEDURE PerfectShuffle(VAR A:arraytype; N:integer)

　　{ i:=1; j:=1;

　　WHILE i<=N DO

　　{ B[j]:=A[i]; B[j+1]:=A[i+N]; i:=i+1; j:=j+2;}

　　A[1..2N]:=B[1..2N]; //B copy to A

　　}

　　PROCEDURE CompareExchange(VAR A:arraytype; N:integer)

　　{ j:=1;

　　WHILE j<2N DO

　　{ IF A[j]>A[j+1] THEN A[j]←→A[j+1]; //交换A[j]�?/span>A[j+1]

　　j:=j+2; }

　　}

　　PROCEDURE Demo (VAR A:arraytype;N:integer)

　　//A的长度�ؓ2N,k=log22N为整�?/span>

　　{ FOR i:=1 TO log22N DO

　　{ PerfectShuffle(A,N); CompareExchange(A,N); }

　　} 【中�U�院计算所 1998 �?/span> �Q?/span>15分）�?/span> 【中国科技大学 1998 4�Q?/span>15分）�?/span>

　　【参考答案�?/span>

　　�Q?/span>1�Q?/span>FOR循环中，每次执行PerfectShuffle(A,N)�?/span>CompareExchange(A,N)的结果：

　　�W?/span>1�ơ：A[1..8]=[90,30,85,65,50,80,10,100]

　　A[1..8]=[30,90,65,85,50,80,10,100]

　　�W?/span>2�ơ：A[1..8]=[30,50,90,80,65,10,85,100]

　　A[1..8]=[30,50,80,90,10,65,85,100]

　　�W?/span>3�ơ：A[1..8]=[30,10,50,65,80,85,90,100]

　　A[1..8]=[10,30,50,65,80,85,90,100]

　　�Q?/span>2�Q?/span>Demo的功能是���数�l?/span>A中元素按递增��序排序�?/span>

　　�Q?/span>3�Q?/span>PerfectShuffle �?/span>WHILE循环内是赋��D��句，�?/span>2N�ơ，WHILE外成�l�赋��D��句，相当2N个简单赋��D��句；CompareExchange�?/span>WHILE循环内是交换语句�Q�最好情况下不发生交换，最差情况下发生N�ơ交换，相当�?/span>3N个赋��D��句；Demo�?/span>FOR循环循环�ơ数log22N�Q�故按赋��D��句次数计��?/span>Demo的时间复杂度为：最好情况：O(4N*log22N)�?/span>O(Nlog(2*N))�Q�最差情况：O((4N+3N)*log22N)�?/span>O(Nlog(2*N))�?/span>