電気通信大学情報理工学研究科情報学専攻 2024年8月実施選択問題アルゴリズムとデータ構造

标签：

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

問1.

次の条件を満たすヒープについて考える。

2 分木であり、親ノードの値はその子ノードの値以下である。
最大の深さを除くすべての深さのノードが完全に埋まっており、最大の深さではノードが 2 分木の左から詰められている。

以下の C 言語で書かれたプログラムは、このヒープを配列で表現して処理するものであり、配列の先頭要素はヒープの根ノードを表す。

void proc1(int a[], int p, int n) {
    int cr, c = p * 2 + 1;
    if (c >= n) return;
    cr = c + 1;
    if (cr < n && a[cr] < a[c]) c = cr;
    if (a[p] <= a[c]) return;
    swap(&a[p], &a[c]);  // (S)行目
    proc1(a, c, n);
}

void proc2(int b[], int n) {
    int p = n / 2 - 1;
    if (p < 0) return;
    for (; p >= 0; p--)
        proc1(b, p, n);
}

void proc3(int c[], int n) {
    for (int i = n - 1; i > 0; i--) {
        swap(&c[0], &c[i]); proc1(c, 0, i);  // (T)行目
    }
}

void proc4(int a[], int n) {
    int c = 3;
    while (c < n) {
        if (a[0] < a[c]) {
            swap(&a[0], &a[c]);
            proc1(a, 0, 3);
        }
        c++;
    }
}

void swap(int *x, int *y) {
    int ex = *x;
    *x = *y;
    *y = ex;
}

問題で用いる配列は次のとおりである。

A = {5, 10, 15, 35, 30, 40, 20, 60, 65, 50, 45, 55, 70, 75, 25}
B = {35, 65, 75, 60, 20, 55, 40, 10}  // ヒープではない
C = {20, 30, 25, 35, 40, 70, 60, 50}
D = {5, 15, 20, 30, 50, 40, 25, 60}

ヒープを表す配列 A の先頭要素の値 5 を 100 に置き換えて、proc1(A, 0, 15) を実行する。実行後の配列 A と、(S) 行目の実行回数を示しなさい。
proc2 は、ヒープでない配列 b からヒープを構成する。配列 B を用いて proc2(B, 8) を実行した後の配列 B を示しなさい。また、(S) 行目の実行回数を示しなさい。
proc3 は、proc1 を使ってヒープを表す配列 c の要素を降順に並び替えるヒープソートのプログラムである。配列 C を用いて proc3(C, 8) を実行するとき、(T) 行目が 4 回繰り返された後の配列 C を示しなさい。
proc4 は、ヒープを表す配列 a を処理する。配列 D を用いて proc4(D, 8) を実行した後の D[0]〜D[2] の値を答えなさい。また、proc4 の実行後、配列 a の根ノードにはどんな値が得られるか答えなさい。

問2.

最大で $N$ 個までのデータの列を蓄えるキューを考える。キューには整数データを順に入力し、先入れ先出しの方式でデータを蓄積・出力する。キューから出力されたデータは破棄される。ここでは要素数 $N$ の配列 Q を用いてキューを表現し、 $N=8$ とする。

#include <stdio.h>
#include <stdlib.h>
int N = 8;  // 蓄積データの最大数

int f, r, e;

void algo2(int q[]) {
    if (e == 1) return;
    f++; f = f % N;
    if (f == r) e = 1;
}

void algo1(int q[], int v) {
    if (f == r && e == 0) algo2(q);
    q[r++] = v; e = 0;
    r = r % N;
}

int main() {
    int i; int Q[N];
    f = r = 0; e = 1;
    for (i = 10; i < 20; i++) algo1(Q, i);  // (A)
    for (i = 1; i <= 5; i++) algo2(Q);       // (B)
    algo1(Q, 20); algo1(Q, 21);
    for (i = 1; i <= 6; i++) algo2(Q);       // (C)
    return 0;
}

algo1 は、キューである配列 q にデータ v を入力する。(A) の実行後、配列 Q と変数 f, r の値を示しなさい。また、配列 Q が蓄えているデータ列を先頭から答えなさい。
algo2 は、配列 q からデータを出力する。(A) の後に (B) を実行した。その実行後の配列 Q と、Q が蓄えているデータ列を先頭から答えなさい。
(C) を実行した後の変数 f, r の値と、配列 Q が蓄えているデータ列を先頭から答えなさい。
変数 e の値が 1 の時は、キューがどういう状態を表すか答えなさい。

题目描述

问 1 给出用数组实现的小根堆及四个操作：向下调整、建堆、堆排序，以及用大小为 3 的堆处理数组。需要写出指定操作后的数组，并回答交换次数及根节点的含义。

问 2 给出一个容量为 8 的循环队列程序。依次执行标记为 (A)、(B)、(C) 的操作后，需要写出数组的物理内容、首尾下标、从队首开始的逻辑数据序列，并说明标志变量 e 的含义。

Kai

問1.

(1)

$100$ は添字 $0\to1\to4\to10$ と移動する。したがって、

A = {10, 30, 15, 35, 45, 40, 20, 60, 65, 50, 100, 55, 70, 75, 25}

$\boxed{\text{(S) は 3 回}}$

(2)

B = {10, 20, 40, 60, 35, 55, 75, 65}

$\boxed{\text{(S) は 6 回}}$

(3)

C = {40, 60, 50, 70, 35, 30, 25, 20}

(4)

\boxed{(D[0],D[1],D[2])=(40,60,50)}

根ノードには、配列全体で 3 番目に大きい値 が得られる。本例では $40$ である。

問2.

(1)

Q = {18, 19, 12, 13, 14, 15, 16, 17}
f = 2, r = 2
データ列：12, 13, 14, 15, 16, 17, 18, 19

(2)

Q = {18, 19, 12, 13, 14, 15, 16, 17}
データ列：17, 18, 19

(3)

f = 4, r = 4
データ列：空列

(4)

$\boxed{e=1\text{ はキューが空であることを表す。}}$

Author​

Description​

問1.​

問2.​

题目描述​

Kai​

問1.​

(1)​

(2)​

(3)​

(4)​