葉以外の節点が必ず子を2つもち根から葉までの深さが等しい木は完全二分木と呼ばれます。
2018年度 秋期 応用情報技術者 午前 問6
難度
標準
葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、木の深さとは根から葉に至るまでの枝の個数を表す。また、節点には根及び葉も含まれる。
選択肢
解説
結論 → 詳細 → 補足 の 3 層構成
展開閉じる
解説
結論 → 詳細 → 補足 の 3 層構成
詳細Layer 2展開閉じる
深さdの完全二分木では葉の数=2^d、内部節点(葉以外)の数=2^d - 1 になるため、葉がn個なら内部節点はn-1個となりエが正解です。アは枝の個数=節点総数-1の関係になるためn=nは成り立たず誤り、イは葉の個数=2^nであって2n-1ではなく誤り、ウは節点総数=2^(d+1)-1 なのでdはlog₂((n+1)/2)で単純なlog₂nではなく誤りです。
この解説は？
分野「基礎理論」の学習ポイント
この問題の理解を「分野全体の力」に広げるための足がかり
- 何が問われるか
- 2進数・論理演算・確率・統計など、IT全般の土台となる数学・離散構造の理解度。
- 学習の進め方
- 公式の暗記ではなく、ビット表現や真理値表を「手で書ける」状態を作る。例題を3パターン以上手で解いて感覚化する。
- 関連キーワード
- 2進数論理演算シフト演算誤差確率情報量
AI コパイロット
この問題を AI と深掘りする
用語解説・選択肢分析・類題生成をその場で対話。クイズモードでは解答→解説がゼロ遷移。
関連する問題
基礎理論 の他の問題
- 応用情報技術者2009年度 秋期 午前 問12進数の表現で、2の補数を使用する理由はどれか。
- 応用情報技術者2009年度 秋期 午前 問2論理和（∨）、論理積（∧）、排他的論理和（⊕）の結合法則の成立に関する記述として、適切な組合せはどれか。
- 応用情報技術者2009年度 秋期 午前 問30~20 kHz の帯域幅のオーディオ信号をディジタル信号に変換するのに必要な最大のサンプリング周期を標本化定理によって求めると、何マイクロ秒か。
- 応用情報技術者2009年度 秋期 午前 問172台のプリンタがあり、それぞれの稼働率が0.7と0.6である。この2台のいずれか一方が稼働していて、他方が故障している確率は幾らか。ここで、2台のプリンタの稼働状態は独立であり、プリンタ以外の要因は考慮しないものとする。
- 応用情報技術者2009年度 秋期 午前 問23図の論理回路において、S=1、R=1、X=0、Y=1のとき、Sをいったん0にした後、再び1に戻した。この操作を行った後のX、Yの値はどれか。 原図の回路：上側はSとYを入力するAND回路の出力を反転してXとし、下側はRとXを入力するAND回路の出力を反転してYとする。XとYはそ…
他試験区分の同分野問題
応用情報技術者 と共通カリキュラムの他区分で「基礎理論」分野を演習する
他年度の「基礎理論」問題
応用情報技術者 の同じ分野を年度をまたいで演習する
- 令和7年度 秋期応用情報技術者 午前 問2コンピュータによる伝票処理システムがある。このシステムは、伝票データをためる待ち行列をもち、 M/M/1の待ち行列モデルが適用できるものとする。平均待ち時間がT秒以上となるのは、システムの利用率が少なくとも何%以上となったときか。ここで、伝票データをためる待ち行列の特徴は次のとお…
- 令和6年度 秋期応用情報技術者 午前 問1M/M/1 の待ち行列モデルにおいて、窓口の利用率が 25%から 40%に増えると、平均待ち時間は何倍になるか。
- 令和5年度 秋期応用情報技術者 午前 問12桁の2進数x1x2が表す整数をxとする。2進数x2x1が表す整数を、xの式で表したものはどれか。ここで、int(r) は非負の実数rの小数点以下を切り捨てた整数を表す。
- 令和4年度 秋期応用情報技術者 午前 問1aを正の整数とし, b = a²とする。aを2進数で表現するとnビットであるとき, bを2進数で表現すると最大で何ビットになるか。
- 令和3年度 秋期応用情報技術者 午前 問1非線形方程式f(x)=0の近似解法であり,次の手順によって解を求めるものはどれか。ここで、y=f(x)には接線が存在するものとし、(3)でxoと新たなxoの差の絶対値がある値以下になった時点で繰返しを終了する。 [手順] (1) 解の近くの適当なx軸の値を定め、xoとする。 (2…
応用情報技術者 の学習ガイド
応用情報技術者 勉強時間の目安｜基本情報合格者・実務経験者・初学者別の合格モデル
応用情報技術者試験の合格に必要な勉強時間を、基本情報合格者・実務経験者・初学者の3パターン別に分解。午前・午後の時間配分と社会人の週次スケジュール例を実例で解説します。
基本情報を飛ばして応用情報から受けてもいい？｜FEを省略してAPに挑む判断基準
基本情報（FE）を飛ばして応用情報（AP）からいきなり受けてもよいか。受験資格に制限はなく可能ですが、向き不向きがあります。飛ばしてよいケース・避けたほうがよいケース・注意点を、FEとAPの違いをふまえて正直に整理します。
応用情報技術者試験を取る意味はあるか｜APのメリットと「意味ない」と言われる理由を整理
応用情報技術者試験（AP）は「意味ない」と言われることがある資格です。取得メリットと「役に立たない」と言われる理由を、転職・実務・高度試験への接続の3観点で整理し、誰に向くのかを正直に解説します。
応用情報 午後 文系・非エンジニア向け選択科目4選｜暗記より読解で勝つ
応用情報技術者試験の午後選択を「文系・非エンジニア」目線で再構成。プログラミングを避けて読解力で勝てる4科目の選び方と、各科目の解答パターンを解説します。