大学院-筆記試験練習线性代数和数据结构161-前言2-线性代数-题目3-线性代数-参考答案4-数据结构-题目5-数据结构-参考答案中文解释题意日语答案1234中文说明题意日语答案立命馆写法(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 / 42visit は「自分→左→右」の順先行順で出力するので表示順は[8,\ 3,\ 1,\ 6,\ 4,\ 10,\ 14]3数列が昇順に整列されている場合木は片側に偏り高さが (n) となる。このとき挿入を n 回行う最悪時間計算量は[O(n^2)]41で得られた木について各頂点の左右部分木の高さ差はすべて 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(nm))である。(3)※この設問は本来「図のグラフ」が必要です頂点 1 を始点として BFS を行い隣接頂点が複数ある場合は頂点番号の昇順に探索する。訪問順はグラフの辺の向きと隣接関係に依存するため図のグラフが与えられた場合にそれに従って列挙する。もし「図1のグラフ頂点と矢印」を送ってくれればその図に対して訪問順を一発で確定して書ける。(4)キュー Q に格納されうる要素数の最大値は最悪でも頂点数を超えない。したがって(O(n))である。(5)BFS を DFS に変更するには探索に用いるデータ構造をキューFIFOからスタックLIFOに変更すればよい。すなわちENQUEUE/DEQUEUE を PUSH/POP に置き換えるまたは再帰呼び出しによりスタックを暗黙的に用いる。6-总结训练成长。