基本情報技術者試験 (FE)｜ 第４章 まとめ | アルゴリズムとプログラミング

基本情報技術者試験 第4章：データ構造とアルゴリズム 完全ガイド

Fundamental Information Technology Engineer Examination

2025年12月合格 執筆者：Tran Huy Khoa

こんにちは！私が2025年12月に基本情報技術者試験 (FE)に合格しました。こちらのシリーズは FEを勉強した時の個人メモです。ブログとしてシェアさせていただき、皆さんの参考になれば幸いです！

この記事では、基本情報技術者試験の第4章「データ構造とアルゴリズム」について、連結リスト、データ構造、探索と整列、プログラムの性質、プログラム言語とマークアップ言語など、試験に必要な重要トピックを詳しく解説します。

目次

• 4.01：連結リスト
• 4.02：データ構造
• 4.03：データ探索と整列
• 4.04：プログラムの性質
• 4.05：プログラム言語とマークアップ言語

4.01：連結リスト

連結リストの種類

• 単方向リスト：データが一方向に連結される
  
  「」--->「」--->「」
• 双方向リスト：データが双方向に連結される
  
  「」<-->「」<-->「」
• 環状リスト：最後のデータが最初のデータに連結される
  
  |-->「」--->「」--->「」-| |----------------------|

4.02：データ構造

木構造

木構造は、節（ノード）、枝（ブランチ）、根（ルート）、葉（リーフ）で構成される階層的なデータ構造です。

2分木の種類

• 完全2分木：根から葉までの深さが全て等しい2分木
• 2分探索木：各節において「左 < 親 < 右」の関係が成立
• ヒープ木：親 < 子（根が最小値）または 親 > 子（根が最大値）
• B木：枝の分岐が2つ以上
• B+木：葉にのみデータを持たせる

4.03：データ探索と整列

整列アルゴリズムの計算量

アルゴリズム	計算量	比較回数
基本交換法 (Bubble sort)	O(n²)	N(N-1)/2
基本選択法 (Selection sort)	O(n²)	N(N-1)/2
基本挿入法 (Insertion sort)	O(n²)	N(N-1)/2

改良された整列アルゴリズム

• シェルソート：一定間隔おきに取り出した要素内で基本挿入法を用いて整列させ、間隔を詰めながら、間隔が1になるまで繰り返す
• クイックソート：基準値を決めて、より小さいグループとより大きいグループに分ける操作を繰り返す
• ヒープソート：未整列データから順序木を作る。根（最大値または最小値）の取り出しを繰り返す

探索アルゴリズムの計算量

• 線形探索法：O(n)
  探索回数は最小で1回、最大でN回、平均 (N+1)/2
• 2分探索法：O(log₂N)
  最大比較回数は (log₂N + 1)回、平均比較回数は log₂N
• ハッシュ探索法：O(1)

ハッシュ探索法の用語

• シノニム：ハッシュ探索法で、格納先のアドレスが衝突すること
• 一様分布：全ての事象が起こる確率が一定である（サイコロを振ることと同じく、どのケースでも確率が一定 1/6）

4.04：プログラムの性質

プログラムの属性

• 再配置可能（リロケータブル）：主記憶のどこに配置しても実行可能
• 再入可能（リエントラント）：複数のタスクが同時に使用可能
• 再使用可能（リユーザブル）：再ロードしなくても使用可能
• 再帰的（リカーシブ）：自分自身を呼び出す

4.05：プログラム言語とマークアップ言語

言語プロセッサ

• アセンブラ：原始プログラム → 機械語
• インタプリタ：原始プログラムを1命令ずつ解釈しながら実行
• コンパイラ：原始プログラムを一括に目的プログラムに解釈

プログラムの実行手順

コンパイル リンク ロード 原始プログラム -------→ 目的プログラム -------→ ロードモジュール -------→ 実行 ↑ ↑ ↑ コンパイラ リンカ ローダ

• コンパイラ：原始プログラム → 目的プログラム
• リンカ：目的プログラム → ロードモジュール
• ローダ：ロードモジュールを主記憶にロード

コンパイル処理の流れ

字句解析 → 構文解析 → 意味解析 → 最適化 → コード生成

リンキング方式

• 動的リンキング：アプリ実行中に、必要となったモジュールをOSによって連携する方式
• 静的リンキング：アプリ実行の前に、予め複数の目的プログラムをリンクしておく

その他の言語プロセッサ

• プリコンパイラ：コンパイラが解釈できないプログラムを、コンパイラの前処理で解釈できるように変換する。拡張構文を標準構文に変換
• クロスコンパイラ：ホスト環境でコンパイルし、異なるターゲット環境（命令形式が異なるPC）で実行可能なプログラムを生成
• ジェネレータ：入出力・処理などのパラメータを指定することで、自動的にプログラムを生成する
• トランスレータ：原始プログラムを、ある言語から別の言語に変換
• エミュレータ：他の環境で開発されたプログラムを類似的に実行
  例：PC上でAndroid端末の環境を再現してアプリを動かす

デバッグツール

• トレーサ：プログラムの命令の実行順序・結果などを時系列に出力
• スナップショットダンプ：命令実行するごとに、指定されたメモリ内容を出力
• メモリダンプ：プログラム異常終了時に、メモリ内容を出力
• 静的解析ツール：プログラムを実行せずに、文法の誤り、規則違反、モジュール構造などを解析するツール

形式言語

BNF記法：構文規則を定義するための表記法

例：<S>::= 01 | 0<S>1 とは、「Sは01と定義する」または「Sは 0<S>1 と定義する」

第4章は以上になります！ご覧いただきありがとうございます。

他の記事はこちらから：www.khoath.com