熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第二章 答案[28]

2013-11-15 15:23:53  來源: 數據結構 

  [算法討論]本題用一維數組存儲線性表結果線性表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)的要求

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


From:http://tw.wingwit.com/Article/program/sjjg/201311/23345.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.