数据结构考研分类复习真题 第十章 排序[31]

．设有字母序列{QDFXAPNBYMCW}请写出按路归并排序方法对该序列进行一趟扫描后的结果_______ 【北方交通大学 二】

阅读下列程序说明和PASCAL程序把应填入其中______处的字句写在答题纸上程序说明

本题给出的是将数组a的元素aa…an从大到小排序的子程序子程序采用改进的选择排序方法该方法基于以下思想

在选择第一大元过程中 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≥)个依次为ajaj…ajk则它们都满足这一性质它们的下标满足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;【上海海运学院 七(分)】

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