企业官网建设流程全解析

企业网站备案资料,网站建设之婚礼摄影网站设计,沈阳网站建设技术支持,建工网校题库大学院-筆記試験練習#xff1a;线性代数和数据结构#xff08;#xff11;8#xff09;1-前言2-线性代数-题目3-线性代数-参考答案4-数据结构-题目【問題1】二分探索木#xff08;BST#xff09;と計算量#xff08;**模拟**#xff09;(1)(2)(3)(4)【問題2】グラフ探…大学院-筆記試験練習线性代数和数据结构81-前言2-线性代数-题目3-线性代数-参考答案4-数据结构-题目【問題1】二分探索木BSTと計算量**模拟**(1)(2)(3)(4)【問題2】グラフ探索とデータ構造**模拟**(1)(2)(3)(4)【問題3】ヒープ構造と優先度付きキュー**预测**(1)(2)(3)(4)【問題4】ハッシュ法**预测**(1)(2)(3)(4)5-数据结构-参考答案【問題1】二分探索木BSTと計算量【解答】(1) 解答(2) 解答(3) 解答(4) 解答【問題2】グラフ探索とデータ構造【解答】(1) 解答(2) 解答(3) 解答(4) 解答【問題3】ヒープ構造と優先度付きキュー【解答】(1) 解答(2) 解答(3) 解答(4) 解答【問題4】ハッシュ法【解答】(1) 解答(2) 解答(3) 解答(4) 解答6-总结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(nm)]である。(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-总结训练成长。