高考申論題
108年
[資訊處理] 資料結構
第 三 題
三、給予如下程式，假設 x[] = [30, 75, 53, 47, 21, 94, 88, 39]，lb = 0，ub = 7，請問執行完下列程式後，x[]的內容為何？（25 分）
void divide&conquer(int x[], int lb, int ub, int *pj)
{
int a, down, temp, up;
a = x[lb];
up = ub;
down = lb;
while(down < up){
while(x[down] <= a && down < ub)
down++;
while(x[up] > a)
up--;
if(down < up){
temp = x[down];
x[down] = x[up];
x[up] = temp;
}
}
x[lb] = x[up];
x[up] = a;
*pj = up;
}
void divide&conquer(int x[], int lb, int ub, int *pj)
{
int a, down, temp, up;
a = x[lb];
up = ub;
down = lb;
while(down < up){
while(x[down] <= a && down < ub)
down++;
while(x[up] > a)
up--;
if(down < up){
temp = x[down];
x[down] = x[up];
x[up] = temp;
}
}
x[lb] = x[up];
x[up] = a;
*pj = up;
}
📝 此題為申論題
思路引導 VIP
- 演算法識別：觀察程式碼，這是快速排序（Quick Sort）中的 Partition（分割）演算法，以陣列第一個元素為基準值（Pivot）。
- 初始化：
x = [30, 75, 53, 47, 21, 94, 88, 39],lb=0,ub=7,a = x[0] = 30。
🤖
AI 詳解
AI 專屬家教
【考點分析】 本題考查「快速排序法（Quick Sort）」的分割程序（Partition Procedure）。此方法透過基準值（Pivot）將數列分為兩部分，左側小於等於基準值，右側大於基準值。 【理論/法規依據】
▼ 還有更多解析內容