学年

教科

質問の種類

情報 大学生・専門学校生・社会人

3-1-cのwの範囲が分かりません 最小値になりうるのは葉だけであることは分かるのですが、条件式はどのようになるでしょうか

3. 以下のような条件 (A), (B) を満たす2分木を考える. (A) 子節点が存在する全ての節点について, その節点の値が子節点の値より大きいか等しい. (B) 一番深いレベル以外は節点が全て詰まっており, 一番深いレベルでは節点が左に詰まって いる. このような木を以下ではヒープ木と呼ぶ. ヒープ木を幅優先で左から走査しながら節点の値を順番に格納 した配列を以下ではヒープ配列と呼ぶ. 配列の添字は0から始まるものとし, n個の要素からなる配列♭を b[0.n-1] と表記する. 図 3.1 は, ヒープ木の例とそれに対応するヒープ配列 c[0..9] である. 1) b[0.n-1] ヒープ配列として, それに対応するヒープ木をTとする. a) T の高さを h とするとき, n の最大値をnで表せ.ここで木の高さとは, 根節点と一番深いレベ ルの節点間にある枝の数とする. 例えば,図 3.1 のヒープ木は高さ3である. b) Tにおいて節点p の左の子節点をq,右の子節点をェとし, p, q, r がそれぞれ b[s],b[t], b [u] に対応するとき, tとusで表せ. c) b[0.n-1] におけるn個の要素が相異なる値を持ち、その最大値と最小値を持つ要素をそれぞ れ b [v], b [w] とするとき, v と w それぞれの値もしくは値の範囲を答えよ.

回答募集中 回答数: 0
情報 大学生・専門学校生・社会人

この問題が分かりません。どなたか教えてください(T_T)

問 6.1 本章の説明と似た考え方で, ● 入力:4ビットで表現された2進数 a4a3a201 出力: 入力に1を加えた結果 cS4838281 となる回路を作ることができる(具体的には, p.63 の図 6.2 で 「入力2」を「0001」に 固定して考えれば「1を加える回路」ができる)以下のヒントを参考に,そのような回路 を作りなさい. ヒント] ● 4ビット加算器のときと同様に一番下の桁の処理部分とそれ以外の部分に分けて考 える.一番下の桁(入力 α1) を処理する回路 (半加算器に相当) は,図 6.3 (p.63) の 「入力 2 (= b)」を1に固定して考えればできる. 半加算器の真理値表 (p.63 の表 6.1) から「b = 0」となっているすべての行を取り除いたものが、作りたい回路の真理値表 である.実際に真理値表を書いてみると、左下の表のようになり,さらに「b」の列を 省略すれば,入力 「a」と出力 「c」 「s」の関係を表す真理値表 (右下) が得られる. b a a C S C S 01 201 (0+1=01) 0 0 1 (0 +1 = 01) 1 1 1 0 (1 +1 = 10) 1 1 0 (1 + 1 = 10) 入力 a2,a3, 4 を処理する回路 (全加算器に相当) は,図 6.5 (p.65) の 「入力 2 (= b)」 を0とみなしたものに相当する. 全加算器の真理値表 (p.65 の表 6.2) から「6 = 1」 の部分を取り除いたものが、左下の表であり,さらに 「b」 の列を省略すれば,入力 「a」「d」 と出力 「c」 「s」 の関係を表す真理値表 (右下) が得られる.

回答募集中 回答数: 0