数据结构考研分类复习真题 第五章 答案[32]

[题目分析] 因为数组中存放的是从到N的自然数原程序运行后数组元素A[i](<=i<=N)中存放的是A[]到A[i]中比原A[i]小的数据元素的个数易见A[N]+就是原A[N]的值(假定是j<=j<=N)设一元素值为的辅助数组flag采用累加确定一个值后flag中相应元素置零下面程序段将A还原成原来的A:

VAR flag:ARRAY[N] OF integer;

FOR i:= TO N DO flag[i]:=; //赋初值

FOR i:=N DOWNTO DO

BEGIN sum:=; j:=; found:=false;

WHILE j<=N AND NOT found DO

BEGIN sum:=sum+flag[j];

IF sum=A[i]+ THEN BEGIN flag[j]:=; found:=true; END;

END;

A[i]:=j;

END;

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