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

．关键码序列( QHCYQAMSRDFX)要按照关键码值递增的次序进行排序若采用初始步长为的Shell排序法则一趟扫描的结果是_____;若采用以第一个元素为分界元素的快速排序法则扫描一趟的结果是______【北京大学 一 (分)】

类似本题的另外叙述有

()设有字符序列QHCYPAMSRDFX要求按字符升序排序采用初始步长为４的希尔(shell)排序一趟扫描的结果是____;采用以首元素为分界元素的快速排序一趟扫描的结果是_____【北京工业大学 一 (分)】

．外部排序的基本方法是归并排序但在之前必须先生成____【北京邮电大学 二(分)】

．磁盘排序过程主要是先生成____然后对____合并而提高排序速度很重要的是_____我们将采用_____方法来提高排序速度【山东工业大学 一(分)】

．设输入的关键字满足k>k>…>kn缓沖区大小为m用置换选择排序方法可产生____个初始归并段【武汉大学 一】

．下面是一改进了的快速排序算法请填空并简要说明支持improveqsort递归所需要的最大栈空间用量

PROCEDURE improveqsort(VAR list:afile;mn:integer);

{设list[m]key<=list[n+]key}

VAR ijk:integer;

BEGIN

WHILE m<n DO

BEGIN

i:=m; j:=n+; k:=list[m]key;

REPEAT

REPEAT i:=i+ UNTIL list[i]key>=k;

REPEAT j:=j UNTIL list[j]key<=k;

IF i<j THEN interchange(list[i]list[j]);

UNTIL i>=j;

interchange(list[m]list[j]);

IF nj>=jm

THEN BEGIN

improveqsort(list ()____); ()____;

END

ELSE BEGIN

improveqsort(list ()____); ()____;

END

END; {OF WHILE}

END;【东南大学 五(分)】

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