数据结构考研分类复习真题 第五章 数组和广义表[25]

数据结构考研分类复习真题 第五章 数组和广义表[25]  

　　 算法Print及所引用的数组A的值如下 写出调用Print( )的运行结果（其中n= ）

　　PROCEDURE print（i integer） 　　BEGIN　　IF（i<=n〉 AND （A[i] <> ） THEN　　BEGIN  Print（ *i） write（A[i]） Print（ *i+ ） END 　　END 【合肥工业大学 四 （ 分）】

　　 设数组A的长度为 N 前N个元素A[ N]递减有序 后N个元素A[N+ N]递增有序 且 N是 的整数次幂 即k=log N为整数 例如A[ ]=[ ]满足上述要求 这里N= k= A的前 个元素和后 个元素分别递减和递增有序 用此例调用如下的Demo过程 并要求

　　（ ）给出for循环中每次执行PerfectShuffle（A N）和CompareExchange（A N）的结果

　　（ ）解释Demo的功能 （ ）给出Demo的时间复杂度

　　PROCEDURE PerfectShuffle(VAR A:arraytype; N:integer)　　[ i:= ; j:= ;　　WHILE i<=N DO　　[ B[j]:=A[i]; B[j+ ]:=A[i+N]; i:=i+ ; j:=j+ ; ]　　A[ N]:=B[ N]; //B copy to A　　]　　PROCEDURE CompareExchange(VAR A:arraytype; N:integer)　　[ j:= ;　　WHILE  j< N  DO　　[ IF  A[j]>A[j+ ] THEN  A[j]←→A[j+ ]; //交换A[j]和A[j+ ]　　j:=j+ ; ]　　]　　PROCEDURE Demo (VAR A:arraytype;N:integer)　　//A的长度为 N k=log N为整数　　[ FOR  i:= TO  log N  DO　　[  PerfectShuffle(A N);   CompareExchange(A N);  ]　　] 【中科院计算所 四 （ 分）】【中国科技大学   （ 分）】