仮の宿 学習室 資格 応用情報技術者 合格ラボ 基礎理論とアルゴリズム 応用情報技術者 APPLIED IT ENGINEER
基礎理論とアルゴリズム
講義 5 本・確認問題 50 問 ｜ 本試験では「テクノロジ系」（50問）の一部 ｜ 最終更新 2026-09-24
この章で学ぶこと 基数変換と浮動小数点を「表せる範囲」と「表せない値」の両面から見て、計算のどこで誤差が生まれるかを言い当てられるようにします。 AND・OR・XOR をビット操作の道具として使い分け、集合の数え上げと期待値・分散・相関の読み方までを一続きで押さえます。 M/M/1 で「利用率が上がると待ち時間が跳ね上がる」ことを数で押さえ、情報量・ハフマン符号・誤り検出訂正までをまとめます。 O記法でアルゴリズムの伸び方を見積り、探索と整列を「データの性質からどれを選ぶか」で判断できるようにします。 2分探索木・ヒープ・B木を用途で選び分け、グラフの最短経路と、再帰を動的計画法に置き換える考え方を身につけます。 1. 数値の表し方と誤差の見積り
基数変換と浮動小数点を「表せる範囲」と「表せない値」の両面から見て、計算のどこで誤差が生まれるかを言い当てられるようにします。
コンピュータの中の数は、有限の桁数に押し込められた近似値です。整数なら nビットで 2ⁿ 通りしか区別できず、2の補数なら −2ⁿ⁻¹ から 2ⁿ⁻¹−1 までしか表せません。この上限を超えた瞬間に符号が反転するのが桁あふれ（オーバーフロー）で、8ビットなら 90 + 70 は 160 ではなく −96 になります。応用情報では「変換できるか」より「どこで壊れるか」を問われるので、範囲の端を先に思い浮かべる癖をつけてください。
小数はもっと厄介です。2進数の小数は 1/2, 1/4, 1/8 …の和でしか作れないため、分母が2のべき乗でない有理数は必ず無限に続きます。10進数の 0.1 は 2進数で 0.0001100110011… と循環し、どこかで打ち切るしかありません。これが丸め誤差の正体で、0.1 を10回足しても 1.0 にならない理由です。金額計算に2進浮動小数点を使ってはいけない、という実務上の判断はここから出ています。
浮動小数点数は符号部・指数部・仮数部の3つに分けて値を持ちます。IEEE 754 の単精度は符号1ビット・指数8ビット・仮数23ビットで、指数はバイアス127を足した形（下駄履き表現）で格納されます。仮数は先頭の1を省略する正規化により実質24ビットぶんの精度を持ちます。10進の有効桁数は 仮数のビット数 × log10(2) で見積もれ、倍精度の53ビットなら約15桁になります。「有効桁数は仮数のビット数で決まる」「表せる範囲は指数のビット数で決まる」と分けて覚えると、精度不足と桁あふれを混同しなくなります。
誤差には名前がついていて、原因が違えば対策も違います。丸め誤差は表せない桁を切り捨て・切上げ・四捨五入したときに生じるもの。打切り誤差は無限に続く計算（級数展開や数値積分）を途中でやめたときに生じるもの。桁落ちは値がほぼ等しい2数の減算で有効桁が一気に失われるもの。情報落ちは絶対値が大きく違う2数の加算で小さいほうが無視されるもの。桁落ちは式を変形して減算を避ける、情報落ちは小さい値から先に足す、というのが定石です。
誤差の4類型と、原因・対策の対応 誤差 起きる場面 原因 主な対策 丸め誤差 0.1 を2進で持つ 有限桁に収まらない 10進小数型や整数化で扱う 打切り誤差 級数展開を途中で止める 無限回の計算を有限回にした 項数を増やす／収束の速い式に変える 桁落ち 1.234567 − 1.234566 近い値の減算で上位桁が消える 式変形して減算を避ける 情報落ち 1.0 に 0.000000001 を足す 小さい値が仮数からあふれる 絶対値の小さい順に加算する
単精度浮動小数点の3つの部分と、精度・範囲の決まり方
IEEE 754 単精度（32ビット）の内訳 [S:1][ E:8 ][ M:23 ] 符号 指数部 仮数部 符号: S が 0 なら正、1 なら負 指数 = E − 127 /* バイアス127を引く */ 仮数 = 1.M /* 先頭の1は省略されている */ 精度: 仮数は実質24ビット → 24 × log10(2) ≒ 7.2 したがって10進で約7桁が信用できる 範囲: 指数8ビット → おおよそ 10⁻³⁸ 〜 10³⁸ 用語 2の補数 nビットで負数を表す方式。全ビットを反転して1を加えると符号が反転する。減算を加算回路だけで実現でき、0の表現が1通りに定まる。表現範囲は −2ⁿ⁻¹ から 2ⁿ⁻¹−1 までで、負のほうが1つ多い。 正規化 浮動小数点数で仮数の最上位が必ず有効な桁になるよう指数を調整すること。同じ値の表し方が1通りに定まり、仮数のビットを無駄なく使えるので精度が最大になる。IEEE 754 では先頭の1を省略して1ビットぶん得をしている。 丸め誤差 有限桁で表せない値を、表せる最も近い値に置き換えたときに生じる誤差。切捨て・切上げ・四捨五入・最近接偶数への丸めなど方式によって偏り方が変わる。累積すると無視できない大きさになる。 打切り誤差 本来は無限に続く計算を有限回で止めたことによる誤差。級数展開の項を途中で切る、反復計算を収束前にやめる、といった場面で生じる。計算量と精度のトレードオフとして意図的に受け入れることが多い。 桁落ち 値がきわめて近い2つの数の減算で、上位の有効桁が打ち消し合って残る有効桁数が激減する現象。2次方程式の解の公式などで起きやすく、分子と分母を有理化するなど式変形で減算そのものを避けるのが対策。 情報落ち 絶対値の差が大きい2数を加減算したとき、小さいほうの値が仮数の桁からあふれて計算結果に反映されない現象。多数の値を合計するときは絶対値の小さいものから順に足すと影響を抑えられる。 けたあふれ 演算結果が表現可能な範囲を超えること。整数のオーバーフローでは符号が反転した値になり、浮動小数点では無限大や非数になる。上位側があふれるのがオーバーフロー、絶対値が小さすぎて0になるのがアンダーフロー。 例題
例題：16進数 2A.4C を10進数で表すといくつか。
答えと考え方 整数部 2A は 2 × 16 + 10 = 42。小数部 .4C は 4/16 + 12/256 = 0.25 + 0.046875 = 0.296875。合わせて 42.296875 になる。16進小数の重みは 1/16, 1/256, 1/4096 と進む点を押さえておく。
例題：真値 1/3 を 0.333 と近似したときの相対誤差は何パーセントか。
答えと考え方 絶対誤差は 1/3 − 0.333 = 1/3000。相対誤差は絶対誤差を真値で割るので (1/3000) ÷ (1/3) = 1/1000 で 0.1 パーセント。絶対誤差だけでは精度の良し悪しは判断できず、値の大きさで割った相対誤差で比べるのが原則。
出典・根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
2. 論理演算・集合と確率統計
AND・OR・XOR をビット操作の道具として使い分け、集合の数え上げと期待値・分散・相関の読み方までを一続きで押さえます。
論理演算はビット単位の道具として見ると使い道がはっきりします。AND は「残したいビットだけ1のマスク」と組み合わせて不要な桁を落とす（クリアする）道具。OR は「立てたいビットだけ1のマスク」で特定の桁を1にする道具。XOR は「反転したいビットだけ1のマスク」で桁を反転する道具で、同じ値で2回 XOR すると元に戻るという性質から、簡易な暗号化やパリティ計算、値の入替えにも使われます。NOT との組合せではド・モルガンの法則、すなわち「和の否定は否定の積」「積の否定は否定の和」が、条件式の書き換えでそのまま効きます。
集合の数え上げでは包除原理が要です。2つなら |A ∪ B| は |A| + |B| − |A ∩ B|、3つなら |A| + |B| + |C| から2つずつの共通部分を引き、最後に3つの共通部分を足し戻します。「引きすぎたぶんを足し戻す」という形を覚えておけば、要素数を数える問題でもデータベースの件数見積りでも同じ式が使えます。集合は論理式と1対1に対応していて、∪ が OR、∩ が AND、補集合が NOT にあたります。
確率では、期待値と分散を分けて考えます。期待値は「値 × 確率」の総和で、平均的にいくらになるかを表す1点の指標。分散は「偏差の2乗の平均」で、期待値からのばらつきの大きさを表します。分散は E[X²] − (E[X])² という形でも計算でき、こちらのほうが手計算では速いことが多いです。標準偏差は分散の平方根で、元のデータと単位がそろうので比較に使いやすくなります。条件付き確率とベイズの定理は、検査の的中率や障害原因の推定に直結します。検出率が99パーセントの検査でも、もともとの発生率が低ければ陽性の多くが誤検出になる、という直感に反する結論はここから出ます。
相関係数は −1 から 1 の範囲を取り、2つの量が直線的にどれだけ連動するかを表します。0 に近ければ直線的な関係がないというだけで、無関係とは限りません（放物線状の関係は相関0になり得ます）。そして相関があっても因果があるとは限りません。応用情報では「相関が強いから原因だ」と結論づける選択肢が誤りとして並ぶので、相関・因果・第三の要因を切り分けて読む姿勢が問われます。
ビット操作の定番パターン（マスクと演算の組合せ） やりたいこと 使う演算 マスクの作り方 結果 特定ビットを1にする OR 立てたい桁だけ1 他の桁は元のまま 特定ビットを0にする AND 残したい桁だけ1 指定桁だけクリア 特定ビットを反転する XOR 反転したい桁だけ1 2回かけると元に戻る 特定ビットを取り出す AND 取り出す桁だけ1 不要な桁が消える 全ビットを反転する XOR 全桁1 1の補数になる
マスクを使ったビット取出しと、AND・XOR の使い分け
○整数型: ビット取出し(整数型: x, 整数型: k) /* x の下から k 番目のビットを 0 か 1 で返す */ 整数型: マスク ← 1 整数型: i for (i を 1 から k − 1 まで 1 ずつ増やす) マスク ← マスク × 2 endfor if ((x AND マスク) ≠ 0) return 1 else return 0 endif /* 使い方の例 */ x が 01011010 のとき ビット取出し(x, 5) は 1 x AND 11110000 で下位4ビットをクリア → 01010000 x XOR 11111111 で全反転 → 10100101 用語 排他的論理和 2入力が異なるとき1、同じとき0になる演算。XOR と書く。同じ値で2回作用させると元に戻る、加算の桁上がりを無視した和にあたる、といった性質からパリティ計算やビット反転、値の入替えに使われる。 ド・モルガンの法則 論理和の否定は各項の否定の論理積に、論理積の否定は各項の否定の論理和に等しいという関係。複雑な否定条件を分配して書き換えるときに使い、集合では補集合の演算に対応する。 包除原理 和集合の要素数を求める原理。重なりを二重に数えたぶんを引き、引きすぎたぶんを足し戻す。3つの集合なら各要素数の和から2つずつの共通部分を引き、3つ全ての共通部分を加える。 期待値 確率変数が取り得る値に、その確率を掛けて足し合わせた値。長期的な平均を表す。期待値は和について線形なので、複数の確率変数の和の期待値は、独立でなくても各期待値の和になる。 分散 期待値からの偏差の2乗の期待値。ばらつきの大きさを表す。E[X²] − (E[X])² としても計算できる。単位が元の量の2乗になるため、比較には平方根を取った標準偏差を使うことが多い。 相関係数 共分散を両者の標準偏差の積で割った値で、−1 から 1 の範囲を取る。直線的な連動の強さを表す指標であり、非直線の関係は捉えられない。値が大きくても因果関係を意味しない。 ベイズの定理 結果が観測されたときに原因の確率を更新する式。事前確率に尤度を掛け、全体で正規化して事後確率を得る。発生率の低い事象では、検出率が高い検査でも陽性的中率が低くなることを説明できる。 例題
例題：全社員100名のうち、資格Aの保有者が60名、資格Bの保有者が45名、両方の保有者が25名である。どちらも持たない社員は何名か。
答えと考え方 包除原理より、少なくとも一方を持つのは 60 + 45 − 25 = 80名。全体から引いて 100 − 80 = 20名。両方を単純に足した105名は、25名を二重に数えている点に注意する。
例題：データ 2, 4, 4, 4, 5, 5, 7, 9 の分散はいくつか。
答えと考え方 平均は 40 ÷ 8 = 5。偏差は −3, −1, −1, −1, 0, 0, 2, 4 で、2乗和は 9 + 1 + 1 + 1 + 0 + 0 + 4 + 16 = 32。分散は 32 ÷ 8 = 4、標準偏差は 2。E[X²] − (E[X])² でも同じ値になることを確かめておくとよい。
出典・根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
3. 待ち行列と情報量・誤り制御
M/M/1 で「利用率が上がると待ち時間が跳ね上がる」ことを数で押さえ、情報量・ハフマン符号・誤り検出訂正までをまとめます。
待ち行列理論は、性能設計でいちばん実務に効く道具です。M/M/1 モデルは、到着がポアソン分布・サービス時間が指数分布・窓口が1つという前提で、利用率 ρ は「到着率 × 平均サービス時間」で求まります。このとき平均待ち時間は ρ ÷ (1 − ρ) × 平均サービス時間、系内の平均応答時間は 平均サービス時間 ÷ (1 − ρ) になります。大事なのは 1 − ρ が分母にあることで、利用率が 0.5 から 0.75 に上がるだけで待ち時間は3倍になります。「CPU使用率がまだ80パーセントだから余裕がある」という判断が危険なのはこのためです。
リトルの法則は、待ち行列の前提を問わず成り立つ関係で、系内の平均個数 L は 到着率 λ と 平均滞在時間 W の積に等しいというものです。3つのうち2つが測れれば残りが求まるので、実測値から未知の指標を出すときに重宝します。窓口を増やす（M/M/s にする）、サービス時間そのものを短くする、到着を平準化する、という3つの打ち手のうちどれが効くかを、式のどこに効くかで判断できるようになるのが目標です。
情報量は「起こりにくい事象ほど、知らされたときの情報が大きい」という考えを対数で定量化したものです。確率 p の事象が起きたと知ったときの情報量は log₂(1/p) ビット。確率 1/8 なら 3ビットです。各事象の情報量を確率で重み付けした平均がエントロピーで、符号化で到達できる平均符号長の下限を与えます。ハフマン符号は、出現確率の低い2つを繰り返しまとめて木を作ることで、この下限に近い可変長符号を作る手法です。頻出の記号に短い符号を割り当てるので、偏りが大きいほど圧縮率が上がります。
誤り制御は、検出だけでよいのか訂正まで必要なのかで手段が変わります。パリティは1ビットの誤りを検出できますが訂正はできず、2ビット誤りは見逃します。CRC は生成多項式による剰余を付加する方式で、連続したビット誤り（バースト誤り）に強く、通信路やストレージで広く使われます。ハミング符号は複数の検査ビットで誤り位置を特定でき、1ビット誤りの訂正と2ビット誤りの検出（拡張ハミング）ができます。データ m ビットに対して必要な検査ビット数 k は 2ᵏ ≧ m + k + 1 を満たす最小値で、データ8ビットなら4ビットが必要です。
M/M/1 で利用率が上がるとどうなるか（平均サービス時間を1とした倍率） 利用率 ρ 平均待ち時間 平均応答時間 系内平均件数 0.2 0.25 1.25 0.25 0.5 1.0 2.0 1.0 0.6 1.5 2.5 1.5 0.8 4.0 5.0 4.0 0.9 9.0 10.0 9.0 0.95 19.0 20.0 19.0
生成多項式1011によるCRCの求め方（剰余が検査符号になる）
CRC の生成（生成多項式 x³ + x + 1 → 1011） 送信データ 11010011 の後ろに 3 ビットの 0 を付け、 1011 で排他的論理和による除算を行う。 11010011000 1011 ---- 1100011000 /* 以下、先頭が1のたびに 1011 をXOR */ 1011 ---- ... 剰余は 011 → 送信するのは 11010011011 受信側で同じ多項式で割り、剰余0なら誤りなしとみなす 用語 M/M/1モデル 到着がポアソン分布、サービス時間が指数分布、窓口が1つの待ち行列モデル。利用率 ρ は到着率と平均サービス時間の積。平均待ち時間は ρ ÷ (1 − ρ) にサービス時間を掛けた値になり、ρ が1に近づくと発散する。 利用率 窓口が仕事をしている時間の割合。到着率をサービス率で割った値に等しい。1未満でなければ行列が無限に伸びるため、設計上は余裕を持たせる。待ち時間は利用率に対して直線的ではなく急激に増える。 リトルの法則 系内の平均滞在数は、到着率と平均滞在時間の積に等しいという関係。到着分布やサービス分布の仮定を必要とせず、安定した系であれば広く成り立つ。3量のうち2つの実測から残りを推定できる。 エントロピー 情報源が1記号あたりに持つ平均情報量。各記号の確率で重み付けした log₂(1/p) の平均で、単位はビット。すべての記号が等確率のときに最大となり、偏りが大きいほど小さくなる。可逆圧縮の限界を与える。 ハフマン符号 出現確率の低い2記号を繰り返し併合して2分木を作り、根からの経路で符号語を決める可変長符号。どの符号語も他の符号語の接頭辞にならない語頭符号になるので、区切り記号なしで一意に復号できる。 CRC 巡回冗長検査。データを多項式とみなし、生成多項式で割った剰余を検査符号として付加する。受信側で同じ除算を行い剰余が0かを見る。バースト誤りの検出能力が高く、誤り訂正はできない。 ハミング符号 複数の検査ビットを配置し、それらの組合せで誤りビットの位置を特定して訂正できる符号。データ m ビットに必要な検査ビット数 k は 2ᵏ ≧ m + k + 1 を満たす最小値。1ビット誤りの訂正が可能。 ハミング距離 同じ長さの2つの符号語で、値が異なるビットの個数。符号全体の最小ハミング距離が d のとき、d − 1 ビットの誤り検出、または (d − 1) ÷ 2 の整数部までの誤り訂正ができる。 例題
例題：平均サービス時間が 20ms の窓口に、1秒あたり 30 件の要求が到着する。M/M/1 として平均待ち時間はいくらか。
答えと考え方 利用率 ρ は 30 × 0.02 = 0.6。平均待ち時間は ρ ÷ (1 − ρ) × サービス時間 なので 0.6 ÷ 0.4 × 20ms = 30ms。待ちとサービスを合わせた応答時間は 20 ÷ 0.4 = 50ms になる。
例題：データが8ビットのとき、1ビット誤りを訂正するハミング符号に必要な検査ビット数はいくつか。
答えと考え方 2ᵏ ≧ m + k + 1 に m = 8 を入れて試す。k = 3 なら 8 ≧ 12 で不成立、k = 4 なら 16 ≧ 13 で成立。よって4ビットで、符号語全体は12ビットになる。
出典・根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
4. 計算量と探索・整列の選び方
O記法でアルゴリズムの伸び方を見積り、探索と整列を「データの性質からどれを選ぶか」で判断できるようにします。
計算量は、データ件数 n が増えたときに処理時間がどう伸びるかを表します。O記法は最も影響の大きい項だけを残す表し方で、定数倍や下位の項は無視します。O(1) は件数に関係なく一定、O(log n) は件数が倍になっても1回ぶんしか増えない、O(n) は比例、O(n log n) は比例よりやや急、O(n²) は件数が4倍になると16倍という具合です。応用情報では「n が 1000 から 4000 になったら処理時間は何倍か」という形でよく問われます。O(n²) なら16倍、O(n log n) なら約4.8倍です。定数倍を無視する記法なので、n が小さいうちは O(n²) のほうが速いこともある、という但し書きも押さえておいてください。
探索は、データの持ち方とセットで選びます。線形探索は前から順に見るだけで O(n)、並んでいなくても使えるかわりに遅い。2分探索は昇順または降順に整列済みであることが前提で O(log n)、n 件なら最大で log₂(n + 1) の切上げ回の比較で済みます。100万件でも20回です。ハッシュ表は鍵から格納位置を計算するので平均 O(1) ですが、異なる鍵が同じ位置になる衝突が起きるため、チェイン法（同じ位置を連結リストにする）やオープンアドレス法（空きを探して置く）で対処します。オープンアドレス法では、表の埋まり具合を示す負荷率が高くなるほど探索回数が急に増えるので、7割程度で拡張するのが一般的です。
整列は計算量だけでは決まりません。バブルソート・選択ソート・挿入ソートはいずれも最悪 O(n²) ですが、挿入ソートはほぼ整列済みのデータなら O(n) に近づき、追加コストがほとんどないという長所があります。クイックソートは平均 O(n log n) で定数倍が小さく実用上いちばん速いことが多い一方、枢軸の選び方が悪いと最悪 O(n²) に落ちます。マージソートは最悪でも O(n log n) を保証しますが、作業用に n 個ぶんの領域が要ります。ヒープソートは最悪 O(n log n) かつ追加領域がほぼ不要ですが、参照の局所性が悪く実測では負けがちです。
もうひとつの軸が安定性です。同じ値の要素どうしの元の順序が保たれるものを安定な整列といい、挿入ソート・マージソート・バブルソートが該当します。クイックソート・ヒープソート・選択ソートは不安定です。「部署順に並べたあと、氏名順に並べ替えても部署内の並びを保ちたい」といった多段の並べ替えでは安定性が必須になります。判断の順序としては、まず安定性が要るか、次に最悪時間の保証が要るか、最後に追加領域を使えるか、と絞り込むと迷いません。
主な整列アルゴリズムの比較（選ぶときの4つの軸） 方式 平均 最悪 追加領域 安定 バブルソート O(n²) O(n²) O(1) 安定 選択ソート O(n²) O(n²) O(1) 不安定 挿入ソート O(n²) O(n²) O(1) 安定 シェルソート n の1.3乗程度 O(n²) O(1) 不安定 クイックソート O(n log n) O(n²) O(log n) 不安定 マージソート O(n log n) O(n log n) O(n) 安定 ヒープソート O(n log n) O(n log n) O(1) 不安定
2分探索。範囲が毎回半分になるので比較回数は log₂ に比例する
○整数型: 2分探索(整数型の配列: a, 整数型: key) /* a は昇順に整列済み。添字は 1 から a の要素数 まで */ 整数型: lo ← 1 整数型: hi ← aの要素数 整数型: mid while (lo ≦ hi) mid ← (lo + hi) ÷ 2 の商 if (a[mid] = key) return mid elseif (a[mid] < key) lo ← mid + 1 else hi ← mid − 1 endif endwhile return −1 /* 見つからない */ 用語 O記法 入力の大きさが増えたときの計算量の増え方を、最も支配的な項だけで表す記法。定数倍と下位の項を無視するため、漸近的な傾向の比較に使う。n が小さい範囲での実測の速さは保証しない。 2分探索 整列済みの列の中央と比較し、探索範囲を半分ずつ狭める探索法。計算量は O(log n) で、n 件なら最大 log₂(n + 1) の切上げ回の比較で終わる。あらかじめ整列しておく必要があるため、更新が頻繁なデータには向かない。 ハッシュ法 鍵にハッシュ関数を適用して格納位置を直接計算する方式。平均計算量は O(1)。異なる鍵が同じ位置に割り当たる衝突が避けられないため、チェイン法やオープンアドレス法で対処する。範囲検索や順次取出しには向かない。 負荷率 ハッシュ表の大きさに対する格納済み要素数の割合。オープンアドレス法では平均探索回数がおおよそ 1 ÷ (1 − 負荷率) で増えるため、0.7 程度を上限として表を拡張するのが目安になる。 クイックソート 枢軸を選んで大小2組に分け、それぞれを再帰的に整列する分割統治法。平均 O(n log n) で定数倍が小さいが、枢軸が偏り続けると最悪 O(n²) になる。不安定な整列である。 マージソート 列を半分ずつに分割して整列し、整列済みの2列を併合する分割統治法。最悪でも O(n log n) を保証し安定だが、併合用に入力と同程度の作業領域を必要とする。外部整列にも応用される。 安定な整列 同じ値を持つ要素どうしの入力時の順序が、整列後も保たれる性質。挿入ソート・マージソート・バブルソートは安定、クイックソート・ヒープソート・選択ソートは不安定である。多段の並べ替えで重要になる。 例題
例題：ある処理の計算量が O(n²) で、n が 1000 のとき 3 秒かかった。n が 5000 になると何秒程度か。
答えと考え方 n が5倍なので時間は 5² = 25 倍、およそ 75 秒。O(n log n) なら 5 × (log₂5000 ÷ log₂1000) ≒ 5 × 1.23 ≒ 6.2 倍で約19秒にとどまる。倍率の計算では、まず n の倍率を出してから記法の次数を当てはめる。
例題：社員データを部署コード順に整列したあと、同じ手続きで氏名順に整列し直すと、同姓同名がいない限り部署内の並びは失われる。これを防ぐにはどうすればよいか。
答えと考え方 氏名順の整列に安定な方式（挿入ソートやマージソート）を使い、部署コード順の整列を先に行えばよい。安定な整列は同値要素の相対順序を変えないため、後から整列した鍵が主キー、先に整列した鍵が副キーとして機能する。クイックソートやヒープソートでは順序が保証されない。
出典・根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
5. 木構造・グラフと再帰・動的計画法
2分探索木・ヒープ・B木を用途で選び分け、グラフの最短経路と、再帰を動的計画法に置き換える考え方を身につけます。
木構造はどれも「階層で絞り込む」道具ですが、得意なことが違います。2分探索木は、ある節点の左部分木にはより小さい値、右部分木にはより大きい値を置く木で、探索・挿入・削除がいずれも木の高さに比例します。ただし昇順に挿入すると一直線の木になり O(n) に退化するため、実務では AVL木や赤黒木のような平衡2分探索木を使って高さを log₂n 程度に保ちます。ヒープは「親は子より小さい（または大きい）」という条件だけを課した完全2分木で、根が常に最小値または最大値になります。全体を整列するわけではないので、最小値の取出しと挿入を繰り返す優先度付きキューに向いています。配列で表せて、1起点なら節点 i の子は 2i と 2i + 1、親は i ÷ 2 の商です。
B木は、1つの節点に複数の鍵と複数の子を持たせた多分木で、ディスクを前提としたデータベースの索引に使われます。狙いは木の高さを極端に低くして、ディスクアクセス回数を減らすことです。1節点が100個の子を持てるなら3段で100万件近くを収められ、どの鍵も3回のアクセスで到達できます。B+木は葉だけにデータを置き、葉どうしを連結リストでつなぐため、範囲検索が高速になります。主記憶の中だけで完結するなら2分探索木、ディスク上の索引ならB木系、という分け方が判断の出発点です。
グラフの最短経路では、辺の重みが非負ならダイクストラ法が使えます。始点からの暫定距離が最小の未確定節点を選んで確定させ、その節点を経由した場合の距離で隣接節点を更新する、を繰り返す貪欲法です。負の重みがある場合はベルマン-フォード法、すべての節点対の最短距離をまとめて求めるならワーシャル-フロイド法（3重ループで O(n³)）を使います。重みをすべて1とみなせるなら幅優先探索で十分です。「負の辺があるか」「全対か単一始点か」の2点で手法が決まります。
再帰は、問題を同じ形の小さな問題に分解して解く書き方です。素直に書くと同じ部分問題を何度も計算してしまうことがあり、フィボナッチ数を単純な再帰で求めると呼出し回数が指数的に増えます。これを、一度計算した結果を表に記録して再利用する形に変えるのが動的計画法です。上から再帰しつつ記録するのがメモ化、下から表を埋めるのが漸化式による表計算で、どちらも計算量を多項式に落とします。動的計画法が使えるのは、最適解が部分問題の最適解から組み立てられ（最適部分構造）、かつ同じ部分問題が繰り返し現れる（部分問題の重複）ときです。ナップサック問題、最長共通部分列、編集距離が代表例です。
データ構造の使い分け（何が速く、何が苦手か） 構造 探索 最小値取出し 範囲検索 主な用途 整列済み配列 O(log n) O(1) 得意 更新の少ない参照専用データ 連結リスト O(n) O(n) 不得意 挿入削除が多い列 平衡2分探索木 O(log n) O(log n) 得意 主記憶上の順序付き集合 ヒープ O(n) O(log n) 不得意 優先度付きキュー ハッシュ表 O(1)平均 O(n) 不得意 完全一致の高速参照 B+木 O(log n) O(log n) 得意 ディスク上の索引
0-1ナップサック問題を1次元の表で解く動的計画法
○整数型: 最大価値(整数型の配列: w, 整数型の配列: v, 整数型: W) /* 0-1 ナップサック。品物 i の重さ w[i]、価値 v[i]、容量 W */ 整数型の配列: dp ← 要素数 W + 1 の配列、すべて 0 整数型: i, c for (i を 1 から wの要素数 まで 1 ずつ増やす) for (c を W から w[i] まで 1 ずつ減らす) if (dp[c − w[i] + 1] + v[i] > dp[c + 1]) dp[c + 1] ← dp[c − w[i] + 1] + v[i] endif endfor endfor return dp[W + 1] /* 容量 c を大きいほうから回すのは、同じ品物を 2回入れてしまわないようにするため */ 用語 2分探索木 各節点について、左部分木の値はすべて小さく、右部分木の値はすべて大きいという条件を満たす2分木。探索・挿入・削除の計算量は木の高さに比例する。挿入順が偏ると一直線になり O(n) に退化する。 平衡2分探索木 挿入や削除のたびに回転などで形を整え、高さを log₂n 程度に保つ2分探索木。AVL木や赤黒木が代表例。最悪計算量が O(log n) で保証されるかわりに、更新時の処理が2分探索木より重い。 ヒープ 親と子の間だけに大小関係を課した完全2分木。根が常に最小値または最大値になる。配列で隙間なく表現でき、挿入と最小値の取出しがいずれも O(log n) なので優先度付きキューの実装に使われる。 B木 1つの節点に複数の鍵と子を持つ多分木で、すべての葉が同じ深さになるよう均衡が保たれる。1節点をディスクの1ブロックに対応させることで、木の高さすなわちアクセス回数を小さく抑えられる。 ダイクストラ法 辺の重みがすべて非負のグラフで、単一始点からの最短経路を求める貪欲法。暫定距離が最小の未確定節点を確定させ、隣接節点の距離を更新することを繰り返す。負の重みがあると正しい結果を得られない。 ワーシャル-フロイド法 すべての節点対の最短距離を求める手法。経由してよい節点を1つずつ増やしながら距離表を更新する3重ループで、計算量は O(n³)。負の重みの辺があっても負閉路がなければ正しく求まる。 動的計画法 部分問題の答えを表に記録して再利用することで、重複した計算を避ける手法。最適部分構造と部分問題の重複という2条件が揃うときに有効。指数時間の素朴な再帰を多項式時間に落とせる。 メモ化 再帰の形を保ったまま、一度計算した引数と結果の組を表に残して同じ計算を繰り返さないようにする技法。上から下へ探索する自然な書き方を維持できるが、必要な部分問題だけを解くので表が疎になることもある。 例題
例題：要素数が 100 万件の平衡2分探索木で、目的の値に到達するまでの比較回数はおよそ何回か。
答えと考え方 高さは log₂(1000001) の切上げでおよそ20なので、20回程度。同じ件数を線形探索すれば平均50万回で、桁が4つ違う。ただし2分探索木は挿入順が昇順だと一直線になり100万回に退化するため、平衡を保つ仕組みが前提になる。
例題：1節点あたり最大10個の子を持てるB木を4段で構成すると、最大で何個の鍵を格納できるか。
答えと考え方 節点数は 1 + 10 + 100 + 1000 = 1111 個。1節点には子の数より1つ少ない最大9個の鍵が入るので、1111 × 9 = 9999 個。段数がわずか4でこの規模になるのがB木の狙いで、どの鍵にも4回のアクセスで到達できる。
出典・根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
確認問題（50問） 四肢択一。「正解と解説」を開くと、正解の理由と他の選択肢が違う理由を確認できます。
問1｜基数変換
次の関数を 2進変換(44) として呼び出したとき、返される配列 b の中身はどれか。
剰余を求めてから商を更新する順に注意する
○整数型の配列: 2進変換(整数型: n) /* n は正の整数。求めた値を b の末尾に順に追加していく */ 整数型の配列: b ← 要素数 0 の配列 整数型: m ← n while (m > 0) b の末尾に (m mod 2) を追加する m ← m ÷ 2 の商 endwhile return b {1, 0, 1, 1, 0, 0} {0, 0, 1, 1, 0, 1} {0, 1, 1, 0, 1, 0} {0, 1, 0, 1, 1, 0} 正解と解説 正解：B. {0, 0, 1, 1, 0, 1} 44 を2で割った剰余は 0, 0, 1, 1, 0, 1 の順に求まり、この順のまま b に追加されるので b は {0, 0, 1, 1, 0, 1} になる。2進数として読むときは末尾から逆に読んで 101100 である。{1, 0, 1, 1, 0, 0} はこの逆順で、上位けたから並ぶと思い込んだ誤り。{0, 1, 1, 0, 1, 0} は6行目と7行目を入れ替えて商を先に更新した場合の結果、{0, 1, 0, 1, 1, 0} はさらにそれを逆順にした値である。基数変換のプログラムは、剰余を並べる向きが答えを分ける。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問2｜循環の理由
10進数の 0.1 を2進数で表すと 0.0001100110011… と無限に循環する。この理由として最も適切なものはどれか。
浮動小数点の仮数部が23ビットしかなく、桁が足りないから 10進数から2進数への変換手順に、必ず誤差が入る近似計算が含まれるから 0.1 が無理数であり、有限小数でも循環小数でも表せない値だから 2進小数は分母が2のべき乗の分数の和でしか表せず、1/10 はその形に書けないから 正解と解説 正解：D. 2進小数は分母が2のべき乗の分数の和でしか表せず、1/10 はその形に書けないから 2進小数の各桁の重みは 1/2、1/4、1/8 と2のべき乗の逆数なので、有限桁で表せるのは分母が2のべき乗に約分できる有理数だけである。1/10 の分母には5が含まれるため有限桁にならない。仮数部のビット数は打ち切る位置を決めるだけで循環そのものの原因ではない。変換手順は誤差のない演算であり、0.1 は有理数なので無理数という説明も誤りである。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問3｜有効桁数
IEEE 754 の単精度浮動小数点数は仮数部が23ビットで、正規化により実質24ビットの精度を持つ。10進数に直したときの有効桁数はおよそ何桁か。
約4桁 約10桁 約15桁 約7桁 正解と解説 正解：D. 約7桁 24ビットで区別できる値の個数は 2²⁴ 通りなので、10進の桁数は 24 × log10(2) ≒ 7.2 となり約7桁である。約15桁は仮数53ビットぶんを持つ倍精度の値、約10桁と約4桁はいずれもこの計算に合わない。有効桁数は仮数のビット数だけで決まり、指数部のビット数は表せる範囲を決める点に注意する。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問4｜桁落ち
浮動小数点演算で桁落ちが生じる場面として最も適切なものはどれか。
絶対値が大きく異なる2つの数を加算し、小さいほうが無視されたとき 無限級数の計算を有限の項数で打ち切ったとき ほぼ等しい大きさの2つの数を減算し、上位の有効桁が打ち消し合ったとき 演算結果が表現できる最大値を超え、無限大になったとき 正解と解説 正解：C. ほぼ等しい大きさの2つの数を減算し、上位の有効桁が打ち消し合ったとき 桁落ちは、近い値どうしの減算で先頭の有効桁が消え、残った下位の桁だけで結果を表すために有効桁数が激減する現象である。絶対値が大きく異なる数の加算で小さいほうが消えるのは情報落ち、級数を途中で止めるのは打切り誤差、表現範囲を超えるのはけたあふれであり、いずれも原因も対策も異なる。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問5｜情報落ち
絶対値の大きさが大きく異なる多数の浮動小数点数を合計するとき、誤差を小さく抑える方法として最も適切なものはどれか。
絶対値の大きいものから順に加算していく 加算のたびに結果を切上げてから次を加える 絶対値の小さいものから順に加算していく 正の数と負の数を交互に並べてから加算する 正解と解説 正解：C. 絶対値の小さいものから順に加算していく 先に大きな値を作ってしまうと、あとから足す小さな値が仮数の桁からあふれて結果に反映されない情報落ちが起きる。小さいものから足せば同程度の大きさどうしの加算が続き、部分和が徐々に育つので影響が小さくなる。切上げを繰り返すと誤差が一方向に偏って累積し、正負を交互に並べても大きさの差の問題は解消しない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問6｜打切り誤差
打切り誤差の説明として適切なものはどれか。
本来は無限に続く計算を有限回で終わらせたために生じる誤差 表現できる桁数を超えた部分を捨てたために生じる誤差 近い値どうしの減算で有効桁数が失われたために生じる誤差 測定器の分解能の限界によって観測値に含まれる誤差 正解と解説 正解：A. 本来は無限に続く計算を有限回で終わらせたために生じる誤差 打切り誤差は、級数展開や反復計算のように本来は無限に続く手順を途中で止めることに由来する。項数を増やすか、収束の速い式に変えることで小さくできる。表現桁数を超えた部分を捨てるのは丸め誤差（切捨て）、近い値の減算は桁落ちで、いずれも別の原因による誤差である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問7｜けたあふれ
次の関数を 8ビット加算(100, 50) として呼び出した。戻り値はどれか。
8ビットに収まらない和を、2の補数として読み直す
○整数型: 8ビット加算(整数型: x, 整数型: y) /* x, y は −128 以上 127 以下。和を8ビットの2の補数として 解釈し直した値を返す */ 整数型: s s ← (x + y) mod 256 /* 0 以上 255 以下になる */ if (s ≧ 128) s ← s − 256 endif return s −150 106 −106 150 正解と解説 正解：C. −106 5行目で s は 150 mod 256 で 150 になる。6行目の条件 s ≧ 128 が成り立つので 7行目で 150 − 256 = −106 となり、これが戻り値である。8ビットの2の補数で表せるのは −128 から 127 までなので、150 は最上位ビットが1のビット列 10010110 として負の値に読み替えられる。150 は 6行目の判定を通らないと考えた誤り、106 は 8ビット加算(−100, −50) の戻り値、−150 は桁あふれが起きないとみなした誤りである。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問8｜相対誤差
真の値 2/3 を 0.667 と近似したときの相対誤差はおよそ何パーセントか。
0.03 パーセント 0.5 パーセント 0.05 パーセント 1.5 パーセント 正解と解説 正解：C. 0.05 パーセント 絶対誤差は 0.667 − 2/3 = 1/3000 ≒ 0.000333。相対誤差は絶対誤差を真の値で割るので (1/3000) ÷ (2/3) = 1/2000 = 0.0005、すなわち 0.05 パーセントである。0.03 パーセントは絶対誤差そのものを百分率にした誤り、0.5 パーセントは 1/2000 = 0.0005 を百分率に直すときに100倍ではなく1000倍してしまった誤り、1.5 パーセントは桁も向きも合わず、どの計算からも得られない値である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問9｜固定小数点
符号1ビット、整数部5ビット、小数部10ビットの固定小数点数がある。この形式で表せる正の値のうち、最も小さいものはどれか。
1/32 1/1024 1/512 1/2048 正解と解説 正解：B. 1/1024 小数部の最下位ビットの重みが分解能になる。小数部が10ビットなら最下位の重みは 2⁻¹⁰ すなわち 1/1024 で、これが表せる最小の正の値である。1/512 は小数部を9ビットと数えた誤り、1/2048 は11ビットと数えた誤り、1/32 は整数部の5ビットから求めた値であり小数の分解能とは無関係である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問10｜指数部の役割
浮動小数点形式で、仮数部のビット数を変えずに指数部のビット数だけを増やしたときに起こることはどれか。
有効桁数は増えるが、表せる値の範囲は変わらない 表せる値の範囲も有効桁数もともに増える 表せる値の範囲は広がるが、有効桁数はほとんど変わらない けた落ちも情報落ちも起こらなくなる 正解と解説 正解：C. 表せる値の範囲は広がるが、有効桁数はほとんど変わらない 指数部は小数点の位置、すなわち表せる値の範囲を決め、仮数部は表せる細かさ、すなわち有効桁数を決める。役割が分かれているので、指数部だけを増やしても精度は上がらない。桁落ちは近い値の減算、情報落ちは大きさの違う値の加算で起きる現象で、どちらも仮数の桁数が有限であることに由来するため、指数部を増やしても解消しない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問11｜XORの性質
排他的論理和（XOR）の性質として正しいものはどれか。
どの値と XOR しても結果は必ず0になる 0 と XOR すると結果は必ず全ビット1になる 全ビット1と XOR すると元の値がそのまま残る 同じ値をもう一度 XOR すると元の値に戻る 正解と解説 正解：D. 同じ値をもう一度 XOR すると元の値に戻る XOR は 2回作用させると打ち消し合うので、鍵で XOR して送り、受信側で同じ鍵をもう一度 XOR すれば復元できる。自分自身と XOR したときだけ0になるのであって、任意の値との XOR が0になるわけではない。0 との XOR は元の値のまま、全ビット1との XOR は全ビット反転（1の補数）であり、選択肢の説明が入れ替わっている。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問12｜ビット整形
次の関数は、引数 x の上位4ビットを 0 にしたうえで、最下位ビットだけを 1 にして返す。x が 10110010 のときも 10110011 のときも 00000011 を返すようにしたい。空欄に入れる字句はどれか。
マスクと演算の組合せで、けたごとの狙いを分ける
○整数型: ビット整形(整数型: x) /* x は8ビット。2進数は8けたのまま書く */ 整数型: r r ← x AND 00001111 r ← 【 】 return r r AND 00000001 r XOR 00000001 r OR 00000001 r OR 11111110 正解と解説 正解：C. r OR 00000001 4行目で上位4ビットは消え、x が 10110010 なら r は 00000010、10110011 なら 00000011 になる。残った下位4ビットを壊さずに最下位ビットだけを 1 にするので、立てたいけただけを 1 にしたマスクとの論理和を使い r OR 00000001 とする。r AND 00000001 は 00000000 と 00000001 になり他のけたが消え、r XOR 00000001 は 00000011 と 00000010 になり元が1のときに0へ反転してしまう。r OR 11111110 は 11111110 と 11111111 になり、0 にしたはずの上位4ビットまで 1 に戻ってしまう。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問13｜1の個数
次の関数を 立っているビット数(10110110) として呼び出した。引数は2進数で与えるものとする。戻り値と、while の繰返し回数の組合せはどれか。
最下位ビットを見ては2で割る、を繰り返す
○整数型: 立っているビット数(整数型: x) /* x は 0 以上 255 以下 */ 整数型: n ← 0 整数型: m ← x while (m > 0) if ((m mod 2) = 1) n ← n + 1 endif m ← m ÷ 2 の商 endwhile return n 戻り値は3、繰返しは8回 戻り値は5、繰返しは5回 戻り値は8、繰返しは8回 戻り値は5、繰返しは8回 正解と解説 正解：D. 戻り値は5、繰返しは8回 10110110 は10進で 182 である。m は 182, 91, 45, 22, 11, 5, 2, 1 と変わって 0 になるので while は8回まわり、そのうち m が奇数だったのは 91, 45, 11, 5, 1 の5回なので n は5になる。1のビット数は最上位ビットまでのけた数と一致しない点に注意する。戻り値3は 0 のビットの個数を数えた誤り、繰返し5回は 1 のビットの個数と取り違えた誤り、戻り値8はビット幅そのものを答えた誤りである。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問14｜ド・モルガン
論理式 NOT (A OR B) と等価な式はどれか。
(NOT A) OR (NOT B) NOT (A AND B) A AND (NOT B) (NOT A) AND (NOT B) 正解と解説 正解：D. (NOT A) AND (NOT B) ド・モルガンの法則により、論理和の否定は各項の否定の論理積になる。集合でいえば「AにもBにも属さない」は「Aの補集合とBの補集合の共通部分」に等しい。(NOT A) OR (NOT B) は NOT (A AND B) と等価で別の式、A AND (NOT B) は A から B を除いた差集合にあたり、いずれも元の式とは異なる。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問15｜包除原理
ある製品群を調べたところ、機能Aを持つものが180、機能Bを持つものが150、機能Cを持つものが120であった。AとBの両方を持つものが60、BとCの両方が45、CとAの両方が50、3つすべてを持つものが20である。A、B、Cのいずれか1つ以上を持つ製品はいくつか。
160 315 295 450 正解と解説 正解：B. 315 包除原理より 180 + 150 + 120 − 60 − 45 − 50 + 20 = 315 である。450 は単純に足しただけで重なりを引いていない値、295 は3つすべての共通部分20を足し戻し忘れた値、160 は2つずつの共通部分を二重に引いた値であり、いずれも重なりの数え方を誤っている。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問16｜期待値
ある施策の1回あたりの効果額が、0円となる確率 0.50、1000円となる確率 0.30、5000円となる確率 0.15、20000円となる確率 0.05 であるとき、効果額の期待値はいくらか。
2050円 1050円 3550円 6500円 正解と解説 正解：A. 2050円 期待値は 0 × 0.50 + 1000 × 0.30 + 5000 × 0.15 + 20000 × 0.05 = 0 + 300 + 750 + 1000 = 2050円。1050円は確率の低い20000円の項を落とした値、3550円は5000円と20000円の確率を取り違えて 0.05 と 0.15 を入れ替えた値、6500円は確率を無視して4つの金額を単純平均した値である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問17｜分散
確率変数Xが値1、2、3をそれぞれ確率 1/2、1/3、1/6 でとるとき、Xの分散はどれか。
5/3 2/3 5/9 10/3 正解と解説 正解：C. 5/9 期待値は 1 × 1/2 + 2 × 1/3 + 3 × 1/6 = 5/3。Xの2乗の期待値は 1 × 1/2 + 4 × 1/3 + 9 × 1/6 = 10/3。分散は 10/3 − (5/3)² = 30/9 − 25/9 = 5/9 である。10/3 はXの2乗の期待値そのもの、5/3 は期待値そのもの、または2乗の期待値から期待値を引いた誤りの値であり、2/3 はいずれの計算にも一致しない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問18｜相関係数
5人の受験者について、模試の順位に対応する値Xが 1、2、3、4、5、本試験の順位に対応する値Yが 1、3、2、5、4 であった。XとYの相関係数はどれか。
0.4 1.0 0.8 1.6 正解と解説 正解：C. 0.8 Xの平均もYの平均も3。共分散は偏差の積の平均で (−2)(−2) + (−1)(0) + (0)(−1) + (1)(2) + (2)(1) を5で割り 8/5 = 1.6。XとYの分散はどちらも 10/5 = 2、標準偏差はその平方根なので、相関係数は 1.6 ÷ 2 = 0.8 である。1.6 は共分散をそのまま答えた誤りで、相関係数は −1 から 1 の範囲を超えない。0.4 は標準偏差の積ではなく分散の積 4 で割った誤り、1.0 は両者の順位が完全に一致した場合の値である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問19｜相関と因果
2つの指標の相関係数が 0.92 であった。この結果の解釈として最も適切なものはどれか。
直線的に連動する傾向は強いが、一方が他方の原因であるとは言えない 一方が他方を引き起こしていると結論してよい 相関係数が1に近いので、2つの指標は同じものを測っている 相関係数が正なので、片方を増やせばもう片方も必ず増える 正解と解説 正解：A. 直線的に連動する傾向は強いが、一方が他方の原因であるとは言えない 相関係数は直線的な連動の強さを表すだけで、因果の向きも有無も示さない。第三の要因が両方を動かしている場合も高い相関になる。値が1に近くても同一の指標とは限らず、また相関は平均的な傾向であって個々の観測で必ず連動することを保証しない。因果を主張するには対照実験など別の根拠が要る。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問20｜ベイズ
ある部品の不良率は1パーセントである。検査装置は不良品を99パーセントの確率で不良と判定するが、良品も2パーセントの確率で誤って不良と判定する。この装置が不良と判定した部品が実際に不良である確率はおよそいくらか。
約1パーセント 約33パーセント 約50パーセント 約99パーセント 正解と解説 正解：B. 約33パーセント 不良かつ不良判定は 0.01 × 0.99 = 0.0099。良品かつ不良判定は 0.99 × 0.02 = 0.0198。不良判定全体は 0.0297 なので、求める確率は 0.0099 ÷ 0.0297 = 1/3 で約33パーセントである。約99パーセントは検出率そのものと取り違えた誤り、約1パーセントは事前の不良率、約50パーセントは2つの経路の件数が等しいと思い込んだ誤りである。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問21｜平均待ち時間
M/M/1 の待ち行列モデルで、平均サービス時間が 100ms のサーバに1秒あたり8件の要求が到着する。平均待ち時間はいくらか。
100ms 400ms 500ms 800ms 正解と解説 正解：B. 400ms 利用率は 8 × 0.1 = 0.8。平均待ち時間は 利用率 ÷ (1 − 利用率) × 平均サービス時間 なので 0.8 ÷ 0.2 × 100ms = 400ms である。500ms は待ち時間にサービス時間を加えた平均応答時間、800ms は 到着率 8 に平均サービス時間 100ms を掛けた値（利用率の計算式）をそのまま待ち時間としてしまった誤り、100ms はサービス時間そのものである。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問22｜平均応答時間
1件あたりの処理に平均 50ms を要するサーバに、1秒あたり12件の要求が到着する。M/M/1 モデルとみなしたとき、要求が到着してから処理が終わるまでの平均応答時間はいくらか。
125ms 50ms 75ms 200ms 正解と解説 正解：A. 125ms 利用率は 12 × 0.05 = 0.6。平均応答時間は 平均サービス時間 ÷ (1 − 利用率) なので 50 ÷ 0.4 = 125ms である。75ms は待ち時間だけを求めた値（0.6 ÷ 0.4 × 50）、50ms はサービス時間そのもの、200ms は 50 ÷ 0.25 のように利用率を 0.75 と取り違えた場合の値であり、いずれも応答時間ではない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問23｜利用率の効き
単一窓口の待ち行列を M/M/1 とみなす。平均サービス時間を変えずに利用率だけを 0.5 から 0.75 に上げたとき、平均待ち時間は何倍になるか。
1.5倍 2倍 6倍 3倍 正解と解説 正解：D. 3倍 平均待ち時間は 利用率 ÷ (1 − 利用率) にサービス時間を掛けた値なので、係数は 0.5 ÷ 0.5 = 1 から 0.75 ÷ 0.25 = 3 に変わり3倍になる。1.5倍は利用率の比をそのまま答えた誤り、2倍と6倍はいずれもこの式から出てこない。分母に 1 − 利用率 があるため、利用率の上昇に対して待ち時間は加速度的に伸びる。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問24｜リトルの法則
ある処理系に1分あたり20件の要求が到着し、系内に滞留している要求は平均5件であった。リトルの法則によれば、1件あたりの平均滞在時間はいくらか。
4秒 25秒 15秒 100秒 正解と解説 正解：C. 15秒 リトルの法則は 系内平均件数 = 到着率 × 平均滞在時間 なので、滞在時間は 5 ÷ 20 = 0.25分、すなわち15秒である。4秒は到着率を件数で割った 20 ÷ 5 を秒とみなした誤り、100秒は 5 × 20 を秒とみなした誤り、25秒はいずれの計算にも一致しない。この法則は到着やサービスの分布を仮定せずに成り立つ点が利点である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問25｜情報量
起こる確率が 1/32 である事象が実際に起きたことを知ったときに得られる情報量は何ビットか。
3ビット 16ビット 32ビット 5ビット 正解と解説 正解：D. 5ビット 確率 p の事象が起きたと知ったときの情報量は log₂(1/p) ビットである。1/32 なので log₂32 = 5ビット。3ビットは確率 1/8 の場合の値、16ビットと32ビットは確率の分母や2のべき乗の指数を取り違えた誤りである。起こりにくい事象ほど情報量が大きくなる、という向きを押さえておく。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問26｜エントロピー
5種類の記号A、B、C、D、Eが、それぞれ確率 1/2、1/4、1/8、1/16、1/16 で現れる情報源がある。この情報源の1記号あたりの平均情報量（エントロピー）は何ビットか。
1.875ビット 1.75ビット 2.32ビット 3ビット 正解と解説 正解：A. 1.875ビット 各記号の情報量は順に 1、2、3、4、4 ビット。確率で重み付けすると 1 × 1/2 + 2 × 1/4 + 3 × 1/8 + 4 × 1/16 + 4 × 1/16 = 0.5 + 0.5 + 0.375 + 0.25 + 0.25 = 1.875ビットになる。1.75ビットは確率が 1/2、1/4、1/8、1/8 の4記号のときの値、2.32ビットは5記号が等確率のときの log₂5、3ビットは5種類を固定長で表すのに必要なビット数である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問27｜ハフマン
5種類の記号が、それぞれ確率 0.45、0.20、0.15、0.12、0.08 で現れる。ハフマン符号を作ったときの1記号あたりの平均符号長は何ビットか。
2.05ビット 2.6ビット 2.1ビット 3ビット 正解と解説 正解：C. 2.1ビット 確率の低い2つを順に併合すると、0.45 の記号に1ビット、残る4つに3ビットが割り当たる。平均符号長は 0.45 × 1 + (0.20 + 0.15 + 0.12 + 0.08) × 3 = 0.45 + 1.65 = 2.1ビットである。2.05ビットはこの情報源のエントロピーで理論的な下限、2.6ビットは符号長 1、3、3、3、3 を確率で重み付けせず単純平均した値、3ビットは固定長で符号化した場合の値である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問28｜CRC
生成多項式を 10011 とするCRCで、送信データ 1101011011 に付加する検査ビット（剰余）はどれか。
0001 0111 1110 1011 正解と解説 正解：C. 1110 生成多項式 10011 の次数は4なので、データの後ろに0を4個付けて 11010110110000 とし、10011 で排他的論理和による除算を行う。剰余は 1110 である。1011 は0を付け足さずに元のデータをそのまま割った誤り、0111 は付ける0を3個と数え違えた場合の剰余、0001 はデータのビット順を逆に並べて割った場合の剰余であり、いずれも正しい手順から得られない。受信側は付加後の全体を同じ多項式で割り、剰余が0であれば誤りなしとみなす。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問29｜ハミング検査
データ16ビットに対して1ビットの誤りを訂正できるハミング符号を構成するとき、必要な検査ビット数は最小でいくつか。
4ビット 6ビット 8ビット 5ビット 正解と解説 正解：D. 5ビット 検査ビット数 k は 2ᵏ ≧ m + k + 1 を満たす最小値である。m が16のとき、k が4では 16 ≧ 21 で不成立、k が5なら 32 ≧ 22 で成立するので5ビット。符号語全体は21ビットになる。4ビットはデータ8ビットまたは11ビットのときの値、6ビットと8ビットは必要以上に多く、最小ではない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問30｜ハミング距離
ある符号の符号語どうしの最小ハミング距離が5であるとき、訂正できる誤りビット数の最大値はいくつか。
1ビット 2ビット 3ビット 4ビット 正解と解説 正解：B. 2ビット 最小ハミング距離 d の符号では、d − 1 ビットまでの誤り検出、または (d − 1) ÷ 2 の整数部までの誤り訂正ができる。d が5なら訂正は 4 ÷ 2 = 2ビットまでである。4ビットは検出できる上限であって訂正の上限ではなく、1ビットは d が3のときの訂正能力、3ビットはこの式から得られない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問31｜ループ回数
次のプログラムを実行し終えたときの変数 cnt の値は、n だけで決まる。n を4倍にすると cnt はおよそ何倍になるか。
内側の for が i から始まる点に注意する
整数型: n 整数型: cnt ← 0 整数型: i, j for (i を 1 から n まで 1 ずつ増やす) for (j を i から n まで 1 ずつ増やす) cnt ← cnt + 1 endfor endfor 4倍 8倍 64倍 16倍 正解と解説 正解：D. 16倍 内側の for は i 回目に n − i + 1 回まわるので、cnt は n + (n − 1) + … + 1 で n × (n + 1) ÷ 2 になる。n が 100 なら 5050、400 なら 80200 で比は約15.9、つまり n² に比例するので4倍にすればおよそ16倍である。4倍は内側が n 回固定だと見て O(n) と考えた誤り、64倍は三重ループの O(n³) とした誤り、8倍は 2³ でありこの形には対応しない。定数の 1/2 は倍率には影響しない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問32｜反復回数
次の関数を 段数(1000) として呼び出した。戻り値と、n に対する繰返し回数の増え方の組合せはどれか。
毎回3分の1になる型のループ
○整数型: 段数(整数型: n) /* n は正の整数 */ 整数型: k ← 0 整数型: m ← n while (m > 1) m ← m ÷ 3 の商 k ← k + 1 endwhile return k 6 と O(log n) 9 と O(log n) 7 と O(log n) 6 と O(n) 正解と解説 正解：A. 6 と O(log n) m は 1000, 333, 111, 37, 12, 4, 1 と変わり、1 になった時点で条件 m > 1 が偽になるので k は6である。1回あたり3分の1になるので繰返し回数は log₃n におさまり、底の違いは定数倍なので O(log n) と書く。9 は 3 ではなく 2 で割ると読み違えた場合の回数、7 は条件を m ≧ 1 と読み違えて 0 になるまでまわした場合の回数、O(n) は n に比例すると見た誤りである。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問33｜2分探索
次の関数について、a が {3, 8, 12, 19, 25, 31, 40}、key が 20 のときの戻り値はどれか。
境界を求める形の2分探索
○整数型: 位置探索(整数型の配列: a, 整数型: key) /* a は昇順に整列済み。添字は 1 から aの要素数 まで。 key 以上である最初の要素の添字を返す。 すべての要素が key 未満なら aの要素数 + 1 を返す */ 整数型: lo ← 1 整数型: hi ← aの要素数 + 1 整数型: mid while (lo < hi) mid ← (lo + hi) ÷ 2 の商 if (a[mid] < key) lo ← mid + 1 else hi ← mid endif endwhile return lo 5 4 6 8 正解と解説 正解：A. 5 lo は1、hi は8で始まる。mid は4となり a[4] は 19 で key の 20 未満なので lo は5になる。次に mid は6で a[6] は 31 なので hi は6、続いて mid は5で a[5] は 25 なので hi は5となり、lo と hi が5で一致して終わる。戻り値は5で、実際 a[5] の 25 が 20 以上である最初の要素である。4 は 20 未満である最後の要素の添字、6 は 25 を飛ばして 31 の位置を答えた誤り、8 はすべてが key 未満だった場合に返る値である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問34｜挿入ソート
次のプログラムについて、外側の for が i の値 4 の回を終えた時点の配列 a はどれか。
整列済みの部分に1件ずつ差し込んでいく
/* 挿入ソート。a の添字は 1 から aの要素数 まで */ 整数型の配列: a ← {8, 3, 5, 1, 9, 4} 整数型: i, j, t for (i を 2 から aの要素数 まで 1 ずつ増やす) t ← a[i] j ← i − 1 while (j ≧ 1 and a[j] > t) a[j + 1] ← a[j] j ← j − 1 endwhile a[j + 1] ← t endfor {3, 5, 8, 1, 9, 4} {1, 3, 5, 8, 9, 4} {1, 3, 4, 5, 8, 9} {1, 5, 8, 3, 9, 4} 正解と解説 正解：B. {1, 3, 5, 8, 9, 4} i が2の回で {3, 8, 5, 1, 9, 4}、3の回で {3, 5, 8, 1, 9, 4}、4の回で t が 1 となり 8, 5, 3 が順に1つ後ろへずれて {1, 3, 5, 8, 9, 4} になる。挿入ソートは前半だけが整列済みで、後半は入力のままである点が特徴になる。{3, 5, 8, 1, 9, 4} は i が3の回を終えた時点、{1, 3, 4, 5, 8, 9} は最後まで実行した結果、{1, 5, 8, 3, 9, 4} はずらさずに a[i] と挿入位置を1回入れ替えるだけにした場合の結果である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問35｜クイックソート
次の手続について、a が {6, 2, 9, 4, 7, 1, 8}、lo が 1、hi が 7 のときの、実行後の a と戻り値の組合せはどれか。
枢軸より小さい要素を前へ集め、最後に枢軸を境目へ置く
○整数型: 分割(整数型の配列: a, 整数型: lo, 整数型: hi) /* クイックソートの分割。枢軸は先頭の要素とする */ 整数型: p ← a[lo] 整数型: i ← lo 整数型: j for (j を lo + 1 から hi まで 1 ずつ増やす) if (a[j] < p) i ← i + 1 a[i] と a[j] を入れ替える endif endfor a[lo] と a[i] を入れ替える return i a は {1, 2, 4, 6, 7, 9, 8}、戻り値は 4 a は {1, 2, 4, 6, 7, 9, 8}、戻り値は 3 a は {6, 2, 4, 1, 7, 9, 8}、戻り値は 4 a は {1, 2, 4, 6, 7, 8, 9}、戻り値は 4 正解と解説 正解：A. a は {1, 2, 4, 6, 7, 9, 8}、戻り値は 4 枢軸は 6 である。j が2で 2 < 6 なので i は2、j が4で 4 < 6 なので i は3となり 9 と 4 が入れ替わって {6, 2, 4, 9, 7, 1, 8}、j が6で 1 < 6 なので i は4となり 9 と 1 が入れ替わって {6, 2, 4, 1, 7, 9, 8} になる。最後に a[1] と a[4] を入れ替えて {1, 2, 4, 6, 7, 9, 8} となり、戻り値は 4 である。戻り値3は i の更新を1回数え落とした誤り、{6, 2, 4, 1, 7, 9, 8} は最後の入替えを忘れた状態、{1, 2, 4, 6, 7, 8, 9} は分割だけで整列まで終わると思い込んだ誤りである。分割は境目を1つ確定させるだけである。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問36｜併合の空欄
次の関数について、x が {2, 5, 9}、y が {1, 5, 7, 8} のときに {1, 2, 5, 5, 7, 8, 9} を返すようにしたい。空欄に入れる字句はどれか。
マージソートの併合。片方が尽きた場合を先に片付ける
○整数型の配列: 併合(整数型の配列: x, 整数型の配列: y) /* x と y はともに昇順。添字は 1 から。併合して昇順の配列を返す */ 整数型の配列: z ← 要素数 xの要素数 + yの要素数 の配列 整数型: i ← 1 整数型: j ← 1 整数型: k for (k を 1 から zの要素数 まで 1 ずつ増やす) if (j > yの要素数) z[k] ← x[i] i ← i + 1 elseif (i > xの要素数) z[k] ← y[j] j ← j + 1 elseif (【 】) z[k] ← x[i] i ← i + 1 else z[k] ← y[j] j ← j + 1 endif endfor return z x[i] > y[j] x[i] ≦ y[j] x[k] ≦ y[k] x[i] ≦ y[i] 正解と解説 正解：B. x[i] ≦ y[j] 両方に要素が残っている間は、先頭どうしを比べて小さいほうを取り出す。x[i] ≦ y[j] のときに x 側を取れば {1, 2, 5, 5, 7, 8, 9} が得られる。等号を x 側に付けておくと、値が等しいときに x の要素が先に出るので併合が安定になる。x[i] > y[j] は大小の向きが逆で {2, 5, 9, 1, 5, 7, 8} となる。x[k] ≦ y[k] は k が y の要素数を超えた時点で添字が範囲外になる。x[i] ≦ y[i] は y 側の添字を取り違えており {1, 5, 7, 8, 2, 5, 9} となる。併合では、2本の列それぞれに別の添字を持たせて、進めたほうだけを1つ進めるのが要点である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問37｜交換回数
次のプログラムを実行し終えたとき、変数 swp の値はいくつか。
隣どうしを比べ、逆順なら入れ替える
/* 交換法。a の添字は 1 から aの要素数 まで */ 整数型の配列: a ← {3, 1, 4, 2, 5} 整数型: i, j, t 整数型: swp ← 0 for (i を 1 から aの要素数 − 1 まで 1 ずつ増やす) for (j を 1 から aの要素数 − i まで 1 ずつ増やす) if (a[j] > a[j + 1]) t ← a[j] a[j] ← a[j + 1] a[j + 1] ← t swp ← swp + 1 endif endfor endfor 3回 10回 4回 5回 正解と解説 正解：A. 3回 隣接交換の回数は、入力に含まれる逆順の組の個数と一致する。{3, 1, 4, 2, 5} では (3, 1)、(3, 2)、(4, 2) の3組なので swp は3である。比較そのものは 4 + 3 + 2 + 1 で10回行われるが、そのうち交換に至るのは3回だけである。10回は比較回数を答えた誤り、4回は外側の for の回数、5回は要素数を答えた誤りである。ほぼ整列済みのデータでは交換回数が小さくなり、交換法や挿入ソートが有利になる理由がここにある。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問38｜チェイン法
ハッシュ表の衝突をチェイン法で解決する。同じ k になる鍵を 11, 23, 35 の順に登録したあと、t[k] から next をたどると 35, 23, 11 の順に取り出せるようにしたい。空欄に入れる字句はどれか。
新しいノードを連鎖の先頭につなぐ
/* t[k] は k 番目の連鎖の先頭ノードを指す。連鎖が空なら t[k] は なし。 ノードは値 val と、次のノードを指す next をもつ */ ○登録(整数型: key) 整数型: k ノード: p k ← ハッシュ値(key) p ← 新しいノード p.val ← key 【 】 t[k] ← p p.next ← t[k] t[k].next ← p p.next ← なし t[k] ← p.next 正解と解説 正解：A. p.next ← t[k] 先頭に追加する手順は、まず新しいノードの next に現在の先頭を指させ、そのうえで先頭を新しいノードに付け替える、の2段階になる。p.next ← t[k] としてから t[k] ← p とすれば、たどる順は 35, 23, 11 になる。t[k].next ← p は連鎖が空のとき t[k] が なし なので参照できず、最初の登録で失敗する。p.next ← なし とすると連鎖が毎回1件に切り詰められ 35 しか残らない。t[k] ← p.next は直後の t[k] ← p で上書きされるだけで意味を持たない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問39｜番兵法
次の関数は、a[1] から a[n] までに key があればその添字を、無ければ −1 を返す。while の中で添字が範囲を超えたかどうかを判定せずに済ませたい。空欄に入れる字句はどれか。
末尾に必ず一致する値を置いて、ループを必ず止める
○整数型: 番兵探索(整数型の配列: a, 整数型: key) /* a の添字は 1 から n + 1 まで。a[n + 1] は番兵を置くための空き */ 整数型: n ← aの要素数 − 1 整数型: i ← 1 【 】 while (a[i] ≠ key) i ← i + 1 endwhile if (i ≦ n) return i else return −1 endif a[1] ← key a[n + 1] ← key a[n − 1] ← key a[n + 1] ← −1 正解と解説 正解：B. a[n + 1] ← key 末尾の空き a[n + 1] に探す値そのものを置いておけば、実データに無くても必ずそこで while が止まる。止まった位置が n 以下なら本物の一致、n + 1 なら見つからなかったと判断できるので、ループ内の範囲判定を1つ減らせる。a[1] ← key は先頭を壊すため常に 1 が返る。a[n − 1] ← key は番兵を1つ手前に置くもので、実データを壊すうえに見つからない場合に −1 ではなく n − 1 を返してしまう。a[n + 1] ← −1 では key が −1 でない限り止まらず、添字が範囲を超える。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問40｜文字列照合
次の関数を 出現回数("ABABABA", "ABA") として呼び出したときの戻り値はどれか。
開始位置を1つずつずらして照合する素朴な方法
○整数型: 出現回数(文字列型: s, 文字列型: p) /* s と p の文字位置は 1 から。位置が重なる出現も別々に数える */ 整数型: cnt ← 0 整数型: i, j 論理型: 一致 for (i を 1 から sの文字数 − pの文字数 + 1 まで 1 ずつ増やす) 一致 ← true for (j を 1 から pの文字数 まで 1 ずつ増やす) if (s の i + j − 1 文字目 ≠ p の j 文字目) 一致 ← false endif endfor if (一致 = true) cnt ← cnt + 1 endif endfor return cnt 3回 2回 5回 15回 正解と解説 正解：A. 3回 開始位置 i は 1 から 5 までの5通りで、そのうち一致するのは i が 1、3、5 のときなので戻り値は3である。i が3の出現は i が1の出現と末尾の A を共有しているが、この関数は開始位置を1つずつしか進めないので別々に数える。2回は一致するたびに開始位置を p の長さぶん飛ばし、重なりを数えなかった場合の値。5回は外側の for の回数、15回は内側の for が実行される延べ回数である。素朴な照合の計算量は s と p の文字数の積に比例する。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問41｜木の走査
次のプログラムを実行したとき、出力される値の並びはどれか。
右の子を先に積むと、左の子が先に取り出される
/* 2分木を配列で表す。v[i] は値、L[i] と R[i] は子の添字で、子が無いときは 0 */ i | 1 2 3 4 5 6 v | 8 3 10 1 6 14 L | 2 4 0 0 0 0 R | 3 5 6 0 0 0 /* スタックを使って全節点をたどる */ 整数型: 根 ← 1 整数型: c スタック: st ← 空 st に 根 を積む while (st が空でない) c ← st から取り出す v[c] を出力する if (R[c] ≠ 0) st に R[c] を積む endif if (L[c] ≠ 0) st に L[c] を積む endif endwhile 1, 3, 6, 8, 10, 14 1, 6, 3, 14, 10, 8 8, 3, 1, 6, 10, 14 8, 3, 10, 1, 6, 14 正解と解説 正解：C. 8, 3, 1, 6, 10, 14 スタックは後入れ先出しなので、右の子を先に積めば左の子が先に取り出され、節点を先に出力してから子へ進む行きがけ順（先行順）になる。出力は 8, 3, 1, 6, 10, 14 である。1, 3, 6, 8, 10, 14 は通りがけ順（中間順）で、この木は2分探索木なので昇順に並ぶ。1, 6, 3, 14, 10, 8 は帰りがけ順（後行順）、8, 3, 10, 1, 6, 14 はスタックをキューに替えた幅優先の並びである。スタックをキューに替えるだけで走査の順序が変わる点が要点になる。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問42｜ヒープ挿入
次の手続について、h が {2, 5, 4, 9, 7, 6} のときに 挿入(h, 3) を実行した後の h はどれか。
末尾に置いてから、親より小さい間だけ上へ運ぶ
○挿入(整数型の配列: h, 整数型: x) /* 最小ヒープ。根は添字1、添字 i の親は i ÷ 2 の商 */ 整数型: i h の末尾に x を追加する i ← hの要素数 while (i > 1 and h[i ÷ 2 の商] > h[i]) h[i] と h[i ÷ 2 の商] を入れ替える i ← i ÷ 2 の商 endwhile {2, 5, 3, 9, 7, 6, 4} {2, 5, 4, 9, 7, 6, 3} {3, 5, 2, 9, 7, 6, 4} {2, 3, 5, 4, 9, 7, 6} 正解と解説 正解：A. {2, 5, 3, 9, 7, 6, 4} 3 を末尾に置くと添字は7で、親の添字は 7 ÷ 2 の商で3である。h[3] は 4 で 3 より大きいので入れ替わり、h は {2, 5, 3, 9, 7, 6, 4} になる。次に i は3、親は1で h[1] は 2 なので 2 > 3 は成り立たず、ここで止まる。{2, 5, 4, 9, 7, 6, 3} は上方移動を1度も行わなかった状態、{3, 5, 2, 9, 7, 6, 4} は条件を確かめずに根まで持ち上げた誤り、{2, 3, 5, 4, 9, 7, 6} は親の添字を i − 1 と読み違えた場合の結果である。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問43｜互除法
次の関数を gcd(1071, 462) として呼び出した。戻り値と、gcd が呼び出される回数（最初の呼出しを含む）の組合せはどれか。
ユークリッドの互除法を再帰で書いた形
○整数型: gcd(整数型: a, 整数型: b) /* a, b は 0 以上の整数 */ if (b = 0) return a else return gcd(b, a mod b) endif 戻り値は 21、呼出しは3回 戻り値は 21、呼出しは4回 戻り値は 3、呼出しは4回 戻り値は 7、呼出しは5回 正解と解説 正解：B. 戻り値は 21、呼出しは4回 引数は (1071, 462)、(462, 147)、(147, 21)、(21, 0) と移り、最後で b が 0 になって 21 を返す。呼出しは最初を含めて4回である。1071 は 3 × 357、462 は 2 × 3 × 7 × 11 なので、共通の因数は 3 と 7 で積は 21 になる。3回は b が 0 になる最後の呼出しを数え落とした誤り、3 と 7 はいずれも共通因数の一部だけを答えた誤りである。互除法の呼出し回数は小さいほうの値の対数におさまるので、桁数が増えても急には伸びない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問44｜B+木
データベースの索引にB+木が使われる理由として、B木と比べたときの利点はどれか。
節点あたりの鍵数が少なくなるので、木の高さが低くなる データがすべて葉に置かれ、葉どうしが連結されているので範囲検索を順にたどるだけで行える 鍵が根の近くに置かれるので、1件の完全一致検索が常に1回のアクセスで終わる 重複した鍵を格納できないので、一意性制約の検査が不要になる 正解と解説 正解：B. データがすべて葉に置かれ、葉どうしが連結されているので範囲検索を順にたどるだけで行える B+木は葉だけに実データ（またはその位置）を置き、葉を連結リストでつなぐ。そのため、範囲の下端を木で探したあとは葉を横にたどるだけでよく、範囲検索が高速になる。節点あたりの鍵数はむしろ多くでき、完全一致検索は必ず葉まで下るので1回では終わらない。重複鍵も格納できる。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問45｜B木の容量
1つの節点が最大5個の子を持てるB木を3段（根から葉まで3階層）で構成する。格納できる鍵の最大個数はいくつか。
31 93 124 155 正解と解説 正解：C. 124 節点数は 1 + 5 + 25 = 31 個。1つの節点には子の数より1つ少ない最大4個の鍵が入るので、31 × 4 = 124 個である。31は節点数そのもの、155は1節点に5個の鍵が入ると誤った値、93は 31 × 3 で鍵数を1つ少なく見積もった誤りである。段数がわずかでも大量の鍵を収められるので、ディスクアクセス回数を抑えられる。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問46｜幅優先
キューを使う次のプログラムを実行したとき、出力される節点の並びはどれか。
キューに入れた時点で済に加えるので、二重に入らない
/* 有向グラフの隣接表。各行の右側は、その節点から出る辺の行き先を並べた順 */ A | C, B B | E, D C | E, F D | F E | なし F | B /* キューを使って A からたどる */ 節点: c, n 整数型: k キュー: q ← 空 集合: 済 ← 空 q に A を入れる 済 に A を加える while (q が空でない) c ← q から取り出す c を出力する for (k を 1 から cの行き先の個数 まで 1 ずつ増やす) n ← c の k 番目の行き先 if (n が 済 に含まれない) 済 に n を加える q に n を入れる endif endfor endwhile A, B, C, D, E, F A, C, E, F, B, D A, C, B, F, E, D A, C, B, E, F, D 正解と解説 正解：D. A, C, B, E, F, D A を出力して C, B をこの順で入れる。C を出力して E, F を入れ、B を出力するが E は済なので D だけを入れる。残りは入れた順に E, F, D と取り出され、出力は A, C, B, E, F, D になる。A, B, C, D, E, F は隣接表を辞書順に読み替えた場合の並び、A, C, E, F, B, D は同じ隣接表を再帰でたどる深さ優先探索（行きがけ順）の並び、A, C, B, F, E, D は C の行き先を F, E の順に読んだ場合の並びである。幅優先探索は、辺の重みがすべて等しいときの最短経路を求める土台になる。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問47｜負の重み
辺の重みに負の値を含むグラフで、単一始点からの最短経路を正しく求められる手法はどれか。
ダイクストラ法 ベルマン-フォード法 幅優先探索 クラスカル法 正解と解説 正解：B. ベルマン-フォード法 ダイクストラ法は、いったん確定した節点の距離があとから縮まらないという前提に立つため、負の重みがあると誤った結果を返す。ベルマン-フォード法は全辺の緩和を節点数 − 1 回繰り返す方式で、負の重みを扱え、負閉路の検出もできる。幅優先探索は重みがすべて等しい場合の手法、クラスカル法は最小全域木を求める手法であり、いずれも最短経路の目的に合わない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問48｜DPの条件
動的計画法が有効に働くための条件の組合せとして適切なものはどれか。
入力が整列済みであること、および部分問題が互いに独立であること 問題を必ず半分ずつに分割できること、および再帰の深さが対数に収まること 評価関数が単調であること、および解の候補が有限個であること 最適解が部分問題の最適解から構成できること、および同じ部分問題が繰り返し現れること 正解と解説 正解：D. 最適解が部分問題の最適解から構成できること、および同じ部分問題が繰り返し現れること 動的計画法は、最適部分構造があるから部分問題の答えを組み合わせて全体の最適解を作れ、部分問題の重複があるから記録の再利用で計算量が減る。部分問題が独立で重複がないなら、記録しても得はなく単なる分割統治で足りる。半分ずつの分割は分割統治法の特徴であり、動的計画法の必須条件ではない。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問49｜DPの空欄
次の関数について、c が {1, 4, 5}、n が 11 のときに 3 を返すようにしたい。空欄に入れる字句はどれか。
添字は1から始まるので、金額 k は dp[k + 1] に対応する
○整数型: 最小枚数(整数型の配列: c, 整数型: n) /* c は硬貨の額面。金額 n をちょうど払う最小の枚数を返す。 払えないときは −1 を返す。dp[k + 1] が金額 k のときの最小枚数 */ 整数型: 大きな値 ← n + 1 整数型の配列: dp ← 要素数 n + 1 の配列 整数型: i, j, t dp[1] ← 0 for (i を 1 から n まで 1 ずつ増やす) dp[i + 1] ← 大きな値 for (j を 1 から cの要素数 まで 1 ずつ増やす) if (c[j] ≦ i) t ← 【 】 if (t < dp[i + 1]) dp[i + 1] ← t endif endif endfor endfor if (dp[n + 1] = 大きな値) return −1 else return dp[n + 1] endif dp[i − c[j] + 1] − 1 dp[i − c[j] + 1] + 1 dp[i − c[j]] + 1 dp[c[j] + 1] + 1 正解と解説 正解：B. dp[i − c[j] + 1] + 1 金額 i を払う最小枚数は、額面 c[j] を1枚使った残りの金額 i − c[j] の最小枚数に1を足したものである。金額 i − c[j] は dp[i − c[j] + 1] に入っているので、t は dp[i − c[j] + 1] + 1 になる。この式で c が {1, 4, 5}、n が 11 のとき 5 + 5 + 1 の3枚が求まる。dp[i − c[j] + 1] − 1 は枚数が減り続けて −11 を返し、dp[i − c[j]] は金額を1つ取り違えるうえ i と c[j] が等しいときに添字が0になる。dp[c[j] + 1] + 1 は残りの金額を見ておらず、どの額面でも払えないと判断して −1 を返す。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
問50｜再帰の回数
フィボナッチ数を漸化式のまま求める次の関数を fib(8) として呼び出した。戻り値と、fib が呼び出される回数（最初の呼出しを含む）の組合せはどれか。
同じ引数が何度も計算される点に注目する
○整数型: fib(整数型: n) /* n は 1 以上の整数 */ if (n ≦ 2) return 1 else return fib(n − 1) + fib(n − 2) endif 戻り値は 13、呼出しは25回 戻り値は 21、呼出しは15回 戻り値は 34、呼出しは41回 戻り値は 21、呼出しは41回 正解と解説 正解：D. 戻り値は 21、呼出しは41回 フィボナッチ数は 1, 1, 2, 3, 5, 8, 13, 21 と並ぶので fib(8) は 21 である。呼出し回数は C(n) が 1 + C(n − 1) + C(n − 2) で増え、1, 1, 3, 5, 9, 15, 25, 41 となるので41回になる。25回は fib(7)、15回は fib(6) の呼出し回数、34 は fib(9) の値である。この増え方はおおむね黄金比のべき乗で、n が少し増えるだけで急に重くなる。計算済みの値を表に残して再利用すれば、各引数について1回しか計算しないので呼出しは n に比例する回数まで減る。
根拠：IPA「応用情報技術者試験（レベル3）」シラバス Ver.7.2 大分類1：基礎理論
演習：この章の問題を解く ランダム出題の演習ツールです（JavaScript が有効な場合に動きます）。上の「確認問題」はそのままでもすべて読めます。
← 応用情報技術者 合格ラボ トップ 次の章：コンピュータ構成とシステム構成 → ※ 解説は学習用の情報提供です。最新の出題範囲・制度は必ずIPAの公式発表をご確認ください。