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

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

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

  .堆是一種有用的數據結構試判斷下面的關鍵碼序列中哪一個是堆_____

  ①      ②    ③  ④    ⑤

  堆排序是一種___()___類型的排序它的一個基本問題是如何建堆常用的建堆算法是年Floyd提出的___()___對含有n個元素的序列進行排序時堆排序的時間復雜度是___()___所需要的附加結點是___()___【山東工業大學 (分)】

  .堆是一種有用的數據結構 堆排序是一種___()___排序堆實質上是一棵___()___結點的層次序列對含有N個元素的序列進行排序時堆排序的時間復雜度是___()___所需的附加存儲結點是___()___關鍵碼序列是否滿足堆的性質___()___ 【山東工業大學 (分)】

  .將如下的堆排序算法補寫完整說明如下

  TYPE heaptype=ARRAY[n]OF integer;

  過程heapsort的功能是將數組h中的前n個記錄按關鍵字遞減的次序排序heapsort調用過程sift時的參數hkr有如下定義以 h[k+]h[k+]h[r]為根的子樹已經是堆;執行sift後以h[k]h[k+]h[k+]h[r] 為根的子樹都成為堆

  PROC sift(VAR hheaptype;krinteger);
  VAR  ijxinteger;finishboolean;
  BEGIN  i:=k;x:=h[i];j:=*j;
  (____()____);
  WHILE  (j<=r) AND  NOT finish DO
  [IF (j<r) AND (h[j]>h[j+]) THEN j:=j+;
  IF x>h[j] THEN [____()____]
  ELSE finish:=true;
  ____()____]
  END;
  PROC heapsort(VAR h:heaptype; n:integer);
  VAR  krij:integer;
  BEGIN
  FOR  k:=n DIV   DOWNTO    DO
  sift (____()____)  ;
  FOR r:=n  DOWNTO    DO
  [x:=h[];  h[]:=h[r];  h[r]:=x; (____()____)]
  END;【北京工業大學 (分)】

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


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