大学院-筆記試験練習：线性代数和数据结构（１8）

1-前言

为了升到自己目标的大学院，所作的努力和学习，这里是线性代数和数据结构部分。

2-线性代数-题目

3-线性代数-参考答案

4-数据结构-题目

【問題1】二分探索木（BST）と計算量（模拟）

整数値を格納する二分探索木を考える。
各節点は 1 つの整数値を保持し，左部分木にはその値より小さい要素，右部分木には大きい要素のみが格納されるものとする。
同じ値は挿入されない。

(1)

数列
[
S={20, 9, 25, 5, 12, 11, 14}
]
を先頭から順に挿入したときに得られる二分探索木を図示せよ。

(2)

(1) で得られた木に対して，
「左部分木 → 節点 → 右部分木」の順で訪問する操作を行ったとき，出力される値を順に示せ。

(3)

挿入される数列が常に降順である場合，
二分探索木への挿入処理全体の最悪時間計算量を，要素数 (n) を用いてオーダー表記で答えよ。

(4)

(1) の木を AVL 木とするために必要な回転操作をすべて行った後の木構造を図示せよ。

【問題2】グラフ探索とデータ構造（模拟）

連結な有向グラフ (G=(V,E)) に対して探索を行う。
頂点数を (n)，辺数を (m) とする。

(1)

グラフを隣接行列で表現した場合，
ある 1 つの頂点から出るすべての辺を列挙するために要する時間計算量を答えよ。

(2)

同じグラフを隣接リストで表現した場合の空間計算量を，
(n,m) を用いてオーダー表記で答えよ。

(3)

幅優先探索（BFS）と深さ優先探索（DFS）について，
必ず成り立つ性質を 1 つ挙げ，簡潔に説明せよ。

(4)

DFS を再帰ではなく明示的なデータ構造を用いて実装する場合，
どのような構造を用いるか答えよ。

【問題3】ヒープ構造と優先度付きキュー（预测）

最大ヒープを用いて優先度付きキューを実装する。

(1)

要素数 (n) の最大ヒープに対して，新たな要素を 1 つ挿入する操作の時間計算量を答えよ。

(2)

最大ヒープから最大要素を削除する操作の概要を，
ヒープ条件の回復方法に着目して説明せよ。

(3)

ヒープソートが安定なソートでない理由を簡潔に述べよ。

(4)

ヒープを配列で実装した場合において，
添字 (i) の要素の親要素の添字を数式で表せ
（配列の先頭を添字 1 とする）。

【問題4】ハッシュ法（预测）

要素数 (n) の集合を管理するためにハッシュ表を用いる。
衝突解決法として**オープンアドレス法（線形探索）**を採用するものとする。

(1)

ハッシュ表の負荷率（ロードファクタ）を定義せよ。

(2)

負荷率が高くなると探索時間が増加する理由を説明せよ。

(3)

線形探索法において，
削除操作を単純に行うと問題が生じる理由を説明せよ。

(4)

(3) の問題を解決するために一般に用いられる方法を 1 つ挙げ，
その概要を述べよ。

5-数据结构-参考答案

【問題1】二分探索木（BST）と計算量【解答】

(1) 解答

数列
[
S={20, 9, 25, 5, 12, 11, 14}
]
を先頭から順に挿入すると，得られる二分探索木は次のとおりである。

20 / \ 9 25 / \ 5 12 / \ 11 14

(2) 解答

「左部分木 → 節点 → 右部分木」の順は中順探索である。
よって出力される値の順序は次のとおりである。

[
5,\ 9,\ 11,\ 12,\ 14,\ 20,\ 25
]

(3) 解答

数列が常に降順で与えられる場合，
二分探索木は片側にのみ伸び，高さが (n) となる。

このとき挿入処理を (n) 回行うため，
最悪時間計算量は

[
O(n^2)
]

である。

(4) 解答

(1) の木において，各節点の左右部分木の高さ差はすべて 1 以下である。
したがって AVL 木の条件をすでに満たしており，回転操作は不要である。

よって回転後の木構造は (1) と同一である。

【問題2】グラフ探索とデータ構造【解答】

(1) 解答

隣接行列では，ある 1 つの頂点から出るすべての辺を列挙するには，
対応する行の全要素を調べる必要がある。

したがって時間計算量は

[
O(n)
]

である。

(2) 解答

隣接リストでは，頂点数分のリストと，辺数分の要素を保持する。
よって空間計算量は

[
O(n+m)
]

である。

(3) 解答

幅優先探索および深さ優先探索では，
各頂点は高々 1 回だけ訪問され，最終的にすべての到達可能な頂点が探索される。

(4) 解答

DFS を再帰を用いずに実装する場合には，
スタック（LIFO 構造）を用いる。

【問題3】ヒープ構造と優先度付きキュー【解答】

(1) 解答

要素数 (n) の最大ヒープに対して要素を 1 つ挿入する操作の時間計算量は，

[
O(\log n)
]

である。

(2) 解答

最大要素を削除する際には，
根の要素を削除し，末尾の要素を根に移動させた後，
ヒープ条件を満たすまで下方向に調整を行う。

(3) 解答

ヒープソートでは，要素の交換により同じ値をもつ要素の相対的な順序が変化する可能性があるため，
安定なソートではない。

(4) 解答

配列の先頭を添字 1 とした場合，
添字 (i) の要素の親要素の添字は

[
\left\lfloor \frac{i}{2} \right\rfloor
]

である。

【問題4】ハッシュ法【解答】

(1) 解答

負荷率（ロードファクタ）とは，
格納されている要素数をハッシュ表の大きさで割った値である。

(2) 解答

負荷率が高くなると衝突が増加し，
探索時に複数の位置を調べる必要が生じるため，探索時間が増加する。

(3) 解答

線形探索法では，削除した要素を単に空にすると，
その後方にある要素が探索できなくなる場合がある。

(4) 解答

この問題を防ぐために，
削除済みを示す特別な印（削除マーク）を用いる方法が一般に用いられる。

6-总结

训练成长。！！