相關(guān)文章：

2008年上半年軟件設(shè)計(jì)師上午試卷I

2008年上半年軟件設(shè)計(jì)師上午試卷II

2008年上半年軟件設(shè)計(jì)師下午試卷I

試題四(共15分)

閱讀下列說(shuō)明，回答問(wèn)題1至問(wèn)題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

快速排序是一種典型的分治算法。采用快速排序?qū)?shù)組A[p..r]排序的三個(gè)步驟如下:

分解：選擇一個(gè)樞軸(pivot)元素劃分?jǐn)?shù)組。將數(shù)組A[p..r]劃分為兩個(gè)子數(shù)組(可能為空) A[p..q-1]和A[q+1..r]，使得A[q]大于等于A(yíng)[p..q-1]中的每個(gè)元素，小于A(yíng)[q+1..r]中的每個(gè)元素。q的值在劃分過(guò)程中計(jì)算。

遞歸求解：通過(guò)遞歸的調(diào)用快速排序，對(duì)子數(shù)組A[p..q-1]和A[q+1..r]分別排序。

合并：快速排序在原地排序，故不需合并操作。

【問(wèn)題1】(6 分)

下面是快速排序的偽代碼，請(qǐng)?zhí)钛a(bǔ)其中的空缺。偽代碼中的主要變量說(shuō)明如下：

A：待排序數(shù)組

p, r：數(shù)組元素下標(biāo)，從p到r

q：劃分的位置

x：樞軸元素

i：整型變量，用于描述數(shù)組下標(biāo)。下標(biāo)小于或等于i的元素的值小于或等于樞軸元素的值

j：循環(huán)控制變量，表示數(shù)組元素下標(biāo)

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]