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

數據結構考研分類復習真題 第十章 排序[31]

2013-11-15 15:10:08  來源: 數據結構 

  .設有字母序列{QDFXAPNBYMCW}請寫出按路歸並排序方法對該序列進行一趟掃描後的結果_______  【北方交通大學

   閱讀下列程序說明和PASCAL程序把應填入其中______處的字句寫在答題紙上程序說明

  本題給出的是將數組a的元素aaan從大到小排序的子程序子程序采用改進的選擇排序方法該方法基於以下思想

  在選擇第一大元過程中 a與aj(j=nn)逐個比較若發現aj>a則aj與a變換變換後新的aj有性質aj≥at(j<t≤n)若再有aj>a (j<j)aj與a交換則交換後的aj也有性質aj≥at(j<t≤n)如在挑選第一大元過程中與a交換的元素有k(k≥)個依次為ajajajk則它們都滿足這一性質它們的下標滿足n≥j>j>…>jk>有了這些下標在確定第二大元時可只考慮a與aj (j=jkjk) 逐個比較倘若jk=則可不經比較就知道它是第二大元在選擇第二大元過程中將與a交換過的元素下標也標記下來可供選擇其他大元使用但在選擇第二大元時應保證與a交換的那些位置上的新值也都滿足上述性質依次類推順序選擇第一第二第n大元實現對a的排序

  設程序包含有常量和類型定義

  CONST  maxn=;
  TYPE  vector=ARRAY[maxn] OF integer;
  index= maxn;
  PROCEDURE sort(VAR a:vector;n:index)
  VAR p:vector; ijkmt:integer;
  BEGIN
  k:=; i:=; m:=n;
  WHILE i<n DO
  BEGIN
  FOR j:=m DOWNTO i+ DO
  IF a[i]<a[j] THEN
  BEGIN t:=a[i]; a[i]:=a[j]; a[j]:=t; k:=k+;(____()____)END;
  REPEAT(____()____);
  IF(____()____)THEN(____()____)
  ELSE BEGIN m:=p[k]; k:=k; END;
  UNTIL (i<m) OR (i=n);
  IF (____()___)
  BEGIN t:=a[i];(____()____);(____()____)END
  END
  END;【上海海運學院 七(分)】

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

推薦文章
Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.