大学院-筆記試験練習：线性代数和数据结构（16）
- 1-前言
- 2-线性代数-题目
- 3-线性代数-参考答案
- 4-数据结构-题目
- 5-数据结构-参考答案
- 中文解释（题意）
- 日语答案
- （1）
- （2）
- （3）
- （4）
- 中文说明（题意）
- 日语答案（立命馆写法）
- (1)
- (2)
- (3)
- (4)
- (5)
- 6-总结
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-总结
训练成长。！！
