跳到主要内容

電気通信大学 情報理工学研究科 情報学専攻 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]
目录