名古屋工業大学 工学研究科 情報工学専攻 2017年度 計算機ソフトウェア（データ構造とアルゴリズム）

标签：

• Nagoya-Institute-of-Technology
• Algorithm-Complexity
• Binary-Search-Tree

Author

GPT-5.6 Sol, 祭音Myyura

Description

次の問い (1)、(2) に答えよ。

(1)

非負整数が格納された配列 $s[0\ldots n-1]\ (n\geq 2)$ に対して、条件 $i<j$ のもとで $s[j]-s[i]$ の最大値を求める問題を考える。以下のアルゴリズム A に関する問いに答えよ。

// アルゴリズム A
m = 0;
for (i = 0 to n - 2)
    for (j = i + 1 to n - 1) {
        k = s[i] - s[j];
        if (k > m) m = k;
    }
m を出力;

• (ア) アルゴリズム A の開始から終了までに、配列の要素 $s[0]$ と $s[n-1]$ が参照される回数をそれぞれ示せ。
• (イ) アルゴリズム A は問題を正しく解けない場合が存在する。$n=5$ のとき、正しく解けない配列 $s[0\ldots n-1]$ の中身の例を一つ挙げよ。

(2)

二分木とそれを使った探索に関する問いに答えよ。

• (ア) 頂点数 3 の二分木をすべて描け。左右の子が明確に区別できるように描くこと。
• (イ) 各頂点 $v$ に、$v$ の左部分木のデータがすべて $v$ のデータ以下であり、$v$ の右部分木のデータがすべて $v$ のデータ以上であるようにデータを格納した二分木を、一般に何と呼ぶか答えよ。以下、この二分木を「(イ) の二分木」と呼ぶ。
• (ウ) 次のアルゴリズム B は「(イ) の二分木」から値 $x$ を探索するアルゴリズムである。空欄 (i)、(ii) に適切な命令を答えよ。

// 「(イ) の二分木」の頂点のデータ構造 node の定義
// data: v に格納されたデータ、lson: v の左の子、rson: v の右の子
struct node { int data; struct node *lson, *rson; };

// 探索アルゴリズム
x を入力する; v = root（根）とする;
while (v が NULL でない) {
    if (x == v->data) v を出力して終了;
    if (x < v->data) v = (i); else v = (ii);
}
見つからなかったと報告して終了;

• (エ) 「(イ) の二分木」の高さが $h$ であるとき、アルゴリズム B の (i) 最悪時間計算量、(ii) 最良時間計算量として正しいものを、それぞれ以下からすべて選べ。

$$\begin{array}{llll} \text{(a) }O(h),&\text{(b) }O(h^2),&\text{(c) }\Omega(\log h),&\text{(d) }\Omega(h),\\ \text{(e) }\Theta(\log h),&\text{(f) }\Theta(h),&\text{(g) }\Theta(1).& \end{array}$$

Kai

(1)

(ア)

$s[0]$ は $i=0$ のときに $j=1,\ldots,n-1$ で参照されるので $n-1$ 回である。

$s[n-1]$ は $j=n-1$ のときに $i=0,\ldots,n-2$ で参照されるので $n-1$ 回である。

(イ)

一例は

$$s=[1,2,3,4,5]$$

である。本来の最大値は $s[4]-s[0]=4$ である。一方、アルゴリズム A が調べる $s[i]-s[j]$ は常に負であるため、$m$ は初期値 $0$ のままであり、誤った値 $0$ を出力する。

(2)

(ア)

/ を左の子、\ を右の子への枝とすると、次の 5 通りである。

    ○
   /
  ○
 /
○

  ○
 /
○
 \
  ○

  ○
 / \
○   ○

○
 \
  ○
 /
○

○
 \
  ○
   \
    ○

(イ)

二分探索木である。

(ウ)

$$\text{(i) }v\mathbin{\to}\mathrm{lson},\qquad \text{(ii) }v\mathbin{\to}\mathrm{rson}$$

すなわち、命令はそれぞれ v = v->lson、v = v->rson である。

(エ)

(i) 最悪時間計算量は $\Theta(h)$ である。したがって、これを含む正しい選択肢は

$$\boxed{\text{(a), (b), (c), (d), (f)}}$$

である。実際、根から深さ $h$ まで一つの経路だけをたどるので $O(h)$ であり、最深部までたどる入力があるため $\Omega(h)$ でもある。また、$\Theta(h)$ ならば $O(h^2)$ および $\Omega(\log h)$ も成り立つ。

(ii) 最良の場合は根で直ちに見つかるので $\Theta(1)$ である。したがって、正しい選択肢は

$$\boxed{\text{(a), (b), (g)}}$$

である。定数時間は $O(h)$ および $O(h^2)$ でもある。

検算

一時プログラムで長さ 5 の非負整数配列を列挙し、上の例では真の最大値が $4$、アルゴリズム A の出力が $0$ となることを確認した。また、左右を区別する 3 頂点二分木を再帰生成すると 5 通りとなり、各形に昇順の 3 キーを中順配置した二分探索木で探索規則を確認した。