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

[算法讨论]本题用一维数组存储线性表结果线性表B和C中分别有j+和k+个元素若采用教材中的线性表则元素的表示作相应改变例如Aelem[i]而最后B和C表应置上表的长度如Blength=j和Clength=k

() 本题与第题本质上相同第题要求分开正数和负数这里要求分开奇数和偶数判别方式是a[i]%==满足时为偶数反之为奇数

() 本题与第题相同只是叙述不同

() 本题与第题基本相同不同之处在于这里的分界元素是整数(链表中并不要求一定有)本题要求用标准pascal描述算法如下所示

TYPE arr=ARRAY[] OF integer;

VAR aarr;

PROCEDURE Rearrange(VAR aarr);∥a是n(设n=)个整数组成的线性表用一维数组存储本算法将n个元素中所有大于等于的整数放在所有小于的整数之后

VAR ijt: integer;

BEGIN

i:=;j:=n;t:=a[];∥ij指示顺序表的首尾元素的下标t暂存分界元素

WHILE(i<j)DO

BEGIN

WHILE (i<j)AND(a[j]>=) DO j:=j;

IF(i<j)THEN BEGIN A[i]:=A[j];i:=i+ END;

WHILE (i<j)AND(a[i] <) DO i:=i+;

IF(i<j)THEN BEGIN A[j]:=A[i];j:=j END;

END;

a[i]:=t;

END;

[算法讨论] 分界元素t放入a[i]而不论它的值如何算法中只用了一个t中间变量符合空间复杂度O()的要求算法也满足时间复杂度O(n)的要求

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