電気通信大学 情報理工学研究科 情報学専攻 2023年8月実施 選択問題 アルゴリズムとデータ構造
Author
祭音Myyura
Description
int A[] = {7, 3, 2, 8, 5, 1, 6, 4};
int B[] = {5, 4, 3, 1, 2};
int C[] = {1, 5, 4, 3, 2};
void swap(int *a, int *b) {
int tmp = *a; *a = *b; *b = tmp;
}
void algo1(int a[], int n) {
int i, j, v; // n は配列要素数
for (i = 1; i < n; i++) {
v = a[i]; j = i;
while (j >= 1 && a[j-1] < v) {
a[j] = a[j-1]; // Y 行目
j--;
}
a[j] = v; // X 行目
}
}
void algo2 (int a[], int l, int r) {
int i, j, k, m; // l は左端添字, r は右端添字
int b[SIZE]; // SIZE は十分に大きな値
if (l < r) {
// 分割処理
m = (r + l) / 2;
algo2(a, l, m); algo2(a, m+1, r);
// 合併のための前処理
for (i = m; i >= l; i--) b[i] = a[i];
i = l;
for (j = m+1; j <= r; j++)
b[r - (j - (m+1))] = a[j];
j = r;
// 合併処理
for (k = l; [ (a) ]; k++)
if (b[i] [ (b) ] b[j])
a[k] = b[i++];
else
a[k] = b[[ (c) ]];
}
}
void algo3(int a[], int n) {
int i, last; // n は配列要素数
if (n <= 1) return;
last = 0;
for (i = 1; i < n; i++)
if (a[i] > a[0])
swap(&a[++last], &a[i]); // W 行目
swap(&a[0], &a[last]); // Z 行目
algo3(a, last);
algo3(a+last+1, n-last-1);
}
問1.
関数 algo1 は与えられた配列をソートする関数である。
これに関する以下の問いに答えよ。
(1) algo1(A, 8) としてソートを実行するとき、X 行目が５回実行された後の配列 A を示しなさい。
(2) Y 行目の最大実行回数を、ソート対象となる配列の要素数
問2.
関数 algo2 は降順にマージソートを行う関数である。
これに関する以下の問いに答えよ。
(1) algo2(A, 0, 7) としてソートを実行するとき、algo2 が再帰呼び出しされる回数を答えなさい。
(2) algo2 中の空欄 [ (a) ] ~ [ (c) ] を埋めなさい。
(3) algo2 の最悪計算量をオーダー表記で表しなさい。
問3.
関数 algo3 は降順にクイックソートを行う関数である。
これに関する以下の問いに答えよ。
(1) algo3(B, 5) としてソートを実行するとき、最初にピボットとなる配列要素を答えなさい。
(2) algo3(B, 5) および algo3(C, 5) としてソートを実行するとき、再帰する過程で Z 行目が３回実行された後の各配列を示しなさい。
(3) W 行目の最大実行回数を、ソート対象となる配列の要素数
Kai
問1.
(1)
7 3 2 8 5 1 6 4
7 3 2 8 5 1 6 4
8 7 3 2 5 1 6 4
8 7 5 3 2 1 6 4
8 7 5 3 2 1 6 4
8 7 6 5 3 2 1 4
8 7 6 5 4 3 2 1
答えは
8 7 5 3 2 1 6 4
(2)
Y 行目の最大実行回数は
問2.
(1)
(2)
[ (a) ]: k <= r[ (b) ]: >=[ (c) ]: j--
(3)
問3.
(1)
最初にピボットとなる配列要素は
(2)
algo3(B, 5): 5, 4, 3, 1, 2
algo3(C, 5): 4, 5, 3, 2, 1
(3)
W 行目の最大実行回数は
[1, n, n-1, n-2, ..., 2]