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

1-前言

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

2-线性代数-题目

3-线性代数-参考答案

4-数据结构-题目

5-数据结构-参考答案

中文解释（题意）

(1)把数列 (S={8,3,10,1,6,14,4}) 按顺序一个个用insert插入到二分搜索树(BST)里，画出最后生成的BST结构。

(2)对(1)得到的树，从根开始执行visit。注意这份visit是：
先输出当前节点 → 再访问左子树 → 再访问右子树（也就是先序遍历），把输出顺序写出来。

(3)如果输入数列本来就是升序（例如 1,2,3,…），BST会退化成“单链条”。问此时插入（构建整棵树）的最坏时间复杂度用 (n) 的大O表示。

(4)把(1)得到的BST通过AVL的旋转操作调整，使得任意节点左右子树高度差≤1。画出旋转后的树。（有可能不需要旋转，这是常见陷阱）

日语答案

（1）

数列 (S={8,3,10,1,6,14,4}) を先頭から順に挿入すると，最終的な二分探索木は次のとおり。

8 / \ 3 10 / \ \ 1 6 14 / 4

（2）

visit は「自分→左→右」の順（先行順）で出力するので，表示順は

[
8,\ 3,\ 1,\ 6,\ 4,\ 10,\ 14
]

（3）

数列が昇順に整列されている場合，木は片側に偏り，高さが (n) となる。
このとき挿入を n 回行う最悪時間計算量は

[
O(n^2)
]

（4）

（1）で得られた木について，各頂点の左右部分木の高さ差はすべて 1 以下である。
よって回転操作は不要であり，回転後の木構造も（1）と同じである。

8 / \ 3 10 / \ \ 1 6 14 / 4

中文说明（题意）

(1)如果图用邻接矩阵表示，判断“两个顶点是否相邻（有没有边）”要看矩阵某个格子，问时间复杂度。

(2)如果图用邻接表表示，存储整张图需要多少空间？用 (|V|=n, |E|=m) 表示。

(3)从顶点1开始跑BFS，写出所有顶点的访问顺序。并且：若某顶点的邻接点有多个，要按顶点编号升序依次处理。

(4)BFS运行过程中，队列Q里最多可能同时放多少个元素？用 (n) 的大O表示（上界）。

(5)要把这个BFS改成DFS，需要把“队列相关处理”改成什么？（本质：FIFO→LIFO，或递归）

日语答案（立命馆写法）

(1)

隣接行列では，頂点 (u,v) が隣接しているかの判定は，行列の要素 (A[u][v]) を 1 回参照すればよい。
したがって時間計算量は(O(1))である。

(2)

隣接リストでは，各頂点ごとのリスト（頂点分）と，各辺に対応する要素（辺分）を保持する。
よって空間計算量は(O(n+m))である。

(3)

（※この設問は本来「図のグラフ」が必要です）
頂点 1 を始点として BFS を行い，隣接頂点が複数ある場合は頂点番号の昇順に探索する。
（訪問順は，グラフの辺の向きと隣接関係に依存するため，図のグラフが与えられた場合にそれに従って列挙する。）

もし「図1のグラフ（頂点と矢印）」を送ってくれれば，その図に対して訪問順を一発で確定して書ける。

(4)

キュー Q に格納されうる要素数の最大値は，最悪でも頂点数を超えない。
したがって(O(n))である。

(5)

BFS を DFS に変更するには，探索に用いるデータ構造をキュー（FIFO）からスタック（LIFO）に変更すればよい。
すなわち，ENQUEUE/DEQUEUE を PUSH/POP に置き換える（または再帰呼び出しによりスタックを暗黙的に用いる）。

6-总结

训练成长。！！