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

數據結構考研分類復習真題 第五章 數組和廣義表[28]

2013-11-15 15:02:47  來源: 數據結構 

   指出下列算法中錯誤低效之處並將其改成一個正確且高效的算法

  PROCEDURE  delk(A m lasti k) ;
  {從數組A[1last]中刪除第i個元素起的 k個元素m為A上限}
  BEGIN
  IF(i<) OR (i>last) OR(k<) OR(last>m)
  THEN   write  (error)
  ELSE  FOR count: =   TO  k  TO
  [FOR  j:=last  DOWNTO   i+  DO
  A[j]:=A[j];
  last:=last]
  ENDP;{delk} 【北方交通大學   一 (分)】

   設輸入為整數數組A[n]其中<=A[i]<=k(<=i<=n)輸出數組為b[n]c[k]是臨時工作空間閱讀下述算法後回答下列問題

  PROC Demo(ABk){
  ()FOR i:= TO k  DO  C[i]:=;
  ()FOR j:= TO n  DO   C[A[j]]:= C[A[j]]+;
  ()FOR i:= TO k  DO   C[i]:= C[i]+ C[i]
  ()FOR j:=n DOWNTO DO {
  () B[C[A[j]]]:=A[j];
  ()C[A[j]]:=C[A[j]] }  }
  (a)當標號()行的循環執行完後C[i](<=i<=n)的值有何意義?
  (b)當標號()行的循環執行完後C[i](<=i<=n)的值有何意義?
  (c)算法執行後B的內容有何特點?
  (d)當k=O(n)時算法的時間復雜度是多少? 【中科院軟件所 分)】

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


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