見出し画像

基本情報技術者試験〔科目B〕演習_2022年サンプル問題　問10（ありえない選択肢、オブジェクト指向、リスト）

Tohoku I-STH

　問10（ありえない選択肢、オブジェクト指向、リスト）
　手続delNode は、単方向リストから、引数pos で指定された位置の要素を削除する手続きである。引数posは、リストの要素数以下の正の整数とする。リストの先頭の位置を1とする。
　クラスListElementは、単方向リストの要素を表す。クラスListElementのメンバ変数の説明を表に示す。ListElement型の変数は、クラスListElementのインスタンスの参照を格納するものとする。大域変数listHeadには、リストの先頭要素の参照があらかじめ格納されている。

クラスListElement のメンバ変数の説明
（メンバ変数、型、説明）
1. (val、文字型、要素の値)
2. (next、ListElement、次の要素の参照、次の要素が無いときの状態は未定義)

〔プログラム〕
1: 大域：ListElement: ListHead // リストの先頭要素が格納されている
2: 〇delNode (整数型：pos) /* posは、リストの要素数以下の正の整数 */
3: 　ListElement: prev
4: 　整数型：i
5: 　if (pos が 1 と等しい)
6: 　　listHead ← listHead.next
7: 　else
8: 　　prev ← listHead
9: 　/* pos が2と等しいときは繰り返し処理を実行しない */
10: 　for (i を 2 から pos – 1 まで 1 ずつ増やす)
11: 　　prev ← prev.next
12: 　endfor
13: 　prev.next ←　□
14: 　endif

解答：prev.next.next

解説
本問題は、単方向リストから指定された位置の要素を削除する手続きdelNodeを扱っている。正しい動作を考慮しつつ、「ありえない選択肢」を問われているので、具体的に説明する。
コードの動作の整理

  1. pos = 1の場合（リストの先頭を削除する）

    • listHeadを次の要素listHead.nextに更新して終了。

  2. pos > 1の場合（指定された位置の要素を削除する）

    • prevをリストの先頭listHeadから開始し、削除対象の一つ手前の要素を取得する。

    • その後、prev.nextを更新して削除対象要素をリストから取り除く。

重要なポイント：削除のためのリンク更新

  • 削除するノードはprev.nextで参照される。

  • 削除時には、prev.nextをprev.next.nextに更新することで、削除対象のノードをリストから外す。

空欄□に入るべき正しいコード

  • 空欄部分に当てはまるのはprev.next.nextである。

    • prev.nextが削除対象ノードを指し、prev.next.nextが削除対象ノードの次のノードを指す。

    • これにより、prev.nextをprev.next.nextに更新して削除対象を切り離せる。

ありえない選択肢について
「ありえない選択肢」は、リストの操作として不正な動作やエラーにつながる操作を選ぶ必要がある。

  1. listHead → 不正。listHeadを直接変更するのはpos = 1の場合のみ適切で、他の位置で使用すると、リスト構造を破壊する。

  2. prev.next → 不正。prev.nextにそのまま代入すると削除対象の次のノードが参照されず、リスト構造が壊れる。

  3. null → 削除操作の対象であれば使うべきではない。

  4. 正解：prev.next.next → これが正しい解答である。

擬似言語プログラムにおける記号の意味と使い方
擬似言語における記述の意味や構文について、それぞれ解説する。

1. ドット（.）で変数名を記述する意味
擬似言語において、ドット記法はオブジェクトのメンバにアクセスすることを意味する。
具体的には次のようなケースである：

  • prev.next
    → prevが参照するオブジェクトの「next」というメンバ変数にアクセスする。

    • 例: prevが現在のリスト要素を指している場合、prev.nextはその次の要素を参照する。

  • prev.next.next
    → prev.next（次の要素）が参照するオブジェクトの「next」というメンバ変数にアクセスする。

    • 例: 3つ先の要素まで順番にたどる場合、prev.next.nextとすることで3番目の要素に到達する。

ドット記法の目的
ドット記法は「階層的に構造化されたデータ」を扱うときに用いられる。
たとえば、リスト要素やオブジェクトの内部にさらにデータ構造が含まれている場合に、それを参照・操作できる。

2. 矢印（←）の意味
矢印（←）は、擬似言語において**「代入」を表す記号**である。
プログラミング言語では、通常=や:=で代入を表すが、擬似言語では矢印が使われることがある。
代入の構文と意味

  • 〇 ← △
    → 「△の値を〇に代入する」

    • 例: listHead ← listHead.next
      → 現在のリストの先頭要素を、次の要素（listHead.next）に置き換える。

  • 擬似言語における代入の特徴

    • 矢印の左側（〇）は「代入先」、右側（△）は「代入元」を表す。

    • 実行の流れを矢印の方向で視覚的に理解しやすい。

3. 実際のプログラミング言語との対応関係
擬似言語の記述を実際のプログラミング言語（例: JavaやPython）に置き換えると以下のようになる：
擬似言語
listHead ← listHead.next
Javaのコード例
listHead = listHead.next;
Pythonのコード例
listHead = listHead.next

まとめ

  1. ドット記法（.）

    • オブジェクトのメンバ変数やメソッドにアクセスするための構文。

    • 擬似言語では構造化データを操作する際に使われる。

  2. 矢印（←）

    • 代入演算子として機能する記号で、視覚的に代入の方向を表している。

これらは、擬似言語でプログラムの流れや構造を分かりやすく示すためのルールであり、実際のプログラムの基礎を表現する役割を果たしている。

ノードとは
ノード（Node）とは、データ構造においてデータの単位を構成する基本的な要素を指す。特に、リストやツリー、グラフなどのデータ構造で頻繁に使われる。ノードは、データ本体（値）とそのデータを他のノードと結びつける参照（リンク）を持つことが一般的である。

1. ノードの構成
ノードの構成要素は、データ構造に応じて以下のように分かれる：
(1) リストにおけるノード

  • データ：ノードが保持する値（例：文字、数値、オブジェクトなど）。

  • リンク（ポインタ/参照）：

    • 単方向リスト：次のノードへのリンク（next）。

    • 双方向リスト：次のノードへのリンク（next）と前のノードへのリンク（prev）。

(2) ツリーにおけるノード

  • データ：ノードが保持する値。

  • リンク（子ノードの参照）：

    • 二分木：左の子ノードへのリンク（left）と右の子ノードへのリンク（right）。

    • 多分木：複数の子ノードへのリンク。

(3) グラフにおけるノード

  • データ：ノードが保持する値。

  • エッジ（隣接ノードへのリンク）：ノード間をつなぐリンク（双方向や単方向）。

2. ノードの役割
ノードは、データの構造化や関係性の管理を行うために使われる。具体的な役割を以下に示す：
(1) データ保持

  • ノードは「データ本体」を格納する役割を担う。

  • 例：リストにおけるノードが、文字や数値などを保持する。

(2) 構造を構成

  • ノード同士がリンクすることで、データの並び順や階層構造、関係性を表現する。

  • 例：

    • 単方向リストでは、各ノードが次のノードを指すことで順序を表現。

    • ツリーでは親子関係をリンクで表現。

(3) 操作の基点

  • ノードは、データ構造を操作する基点として利用される。

  • 例：

    • リストでは「先頭ノード」から順に操作を開始。

    • ツリーでは「ルートノード」から検索や挿入を開始。

3. ノードの実装例
プログラミングでノードを実装する場合、オブジェクト指向言語ではクラスとして定義されることが一般的である。
(1) 単方向リストのノード（Java例）
class Node {
int data; // ノードが保持するデータ
Node next; // 次のノードへの参照

// コンストラクタ
Node(int data) {
this.data = data;
this.next = null;
}
}
(2) 二分木のノード（Python例）
class TreeNode:
def __init__(self, value):
self.value = value # ノードが保持するデータ
self.left = None # 左の子ノードへの参照
self.right = None # 右の子ノードへの参照

4. ノードの具体例
以下は、ノードがどのように使われるかの例。
(1) 単方向リスト

  • リスト：10 → 20 → 30 → null

    • ノード1（データ：10、次：ノード2）

    • ノード2（データ：20、次：ノード3）

    • ノード3（データ：30、次：null）

(2) 二分木

  • ツリー：

   10
   / \
20 30

  • ルートノード（データ：10、左：ノード20、右：ノード30）

  • 左の子ノード（データ：20、左：null、右：null）

  • 右の子ノード（データ：30、左：null、右：null）

5. ノードの重要性

  • ノードはデータ構造の基本単位として非常に重要である。

  • リストやツリー、グラフなど、多くのデータ構造はノードの集まりで形成されている。

  • ノードを正しく理解することで、データ構造やアルゴリズムの設計・実装がスムーズになる。

まとめ：
ノードは、データとその関係性を管理する基本的な要素であり、データ構造を構築するための基盤となる。リスト、ツリー、グラフなどの構造を学ぶ際に、ノードの概念を正しく理解することが重要である。

単方向リストと双方向リストの違い
単方向リストと双方向リストは、どちらもデータ構造として「リスト」を表現するが、ノード間のリンクの方法が異なる。それぞれの特徴、利点、欠点を以下に説明する。

1. 単方向リスト（Singly Linked List）
構造

  • 各ノードが以下を保持する：

    1. データ（値）

    2. 次のノードへの参照（ポインタ）

  • 最後のノード（末尾ノード）の次の参照は通常nullまたは未定義で、リストの終端を示す。

例
ノードが A → B → C → null のように一方向にリンクする。
利点

  1. 実装が簡単：

    • ノードが「データ」と「次のノードへの参照」だけを持つので構造がシンプル。

  2. メモリ効率が良い：

    • 各ノードが次のノードへの参照だけを持つため、メモリ使用量が少ない。

  3. 一方向の操作に適している：

    • 先頭から順にデータを処理する場合に効率的。

欠点

  1. 逆方向の操作が困難：

    • 逆方向のリンクがないため、ノードを遡る操作ができない。

  2. 削除・挿入操作の制限：

    • 指定ノードを削除するには、必ず「その一つ前のノード」を見つける必要がある。

    • 末尾にノードを追加する場合、全ノードを辿る必要がある。

2. 双方向リスト（Doubly Linked List）
構造

  • 各ノードが以下を保持する：

    1. データ（値）

    2. 次のノードへの参照（ポインタ）

    3. 前のノードへの参照（ポインタ）

  • 最初のノード（先頭ノード）は「前の参照」がnullを指し、最後のノードは「次の参照」がnullを指す。

例
ノードが null ← A ↔ B ↔ C → null のように両方向にリンクする。
利点

  1. 双方向の操作が可能：

    • 次のノードだけでなく、前のノードにも簡単に遡ることができる。

  2. 挿入・削除が柔軟：

    • 特定のノードの削除や挿入が効率的（前のノードを保持する必要がない）。

    • リストの末尾にも容易にアクセス可能。

  3. 循環リストに適している：

    • 循環的な処理に向いており、先頭から末尾、または逆方向の巡回が容易。

欠点

  1. 実装が複雑：

    • 各ノードが「前」と「次」への参照を持つため、操作や実装が煩雑になる。

  2. メモリ消費が大きい：

    • 各ノードが追加のポインタ（参照）を持つため、単方向リストに比べてメモリ使用量が増える。

  3. パフォーマンスへの影響：

    • リストのサイズが大きくなると、参照管理のためのオーバーヘッドが増える。

3. 本問題との関連性

  • 単方向リストでは、削除処理において「削除対象の前のノード」が必要である。本問題のdelNodeでは、削除対象のノードを「prev.next」として扱い、前のノードprevを用いて削除操作を実現している。

  • 双方向リストであれば、削除対象のノード自体が「前のノードへの参照」を持つため、前のノードprevを保持する必要はない。この違いから、双方向リストではより簡潔に削除処理が実装できる。

4. 適切な選択肢

  • 単方向リストはシンプルで効率的だが、柔軟性が低い場合に向いている。

  • 双方向リストは操作が多い場合や逆方向操作が必要な場合に適している。

・Java でコーディング

class ListElement {
    char val;          // 要素の値
    ListElement next;  // 次の要素への参照

    // コンストラクタ
    ListElement(char val) {
        this.val = val;
        this.next = null;
    }
}

public class SinglyLinkedList {
    static ListElement listHead; // リストの先頭要素

    // 要素を削除するメソッド
    public static void delNode(int pos) {
        if (pos <= 0) {
            System.out.println("無効な位置です。");
            return;
        }

        if (pos == 1) { // 先頭の削除
            if (listHead != null) {
                listHead = listHead.next;
            }
            return;
        }

        ListElement prev = listHead;
        for (int i = 2; i < pos; i++) { // pos - 1 まで進む
            if (prev == null || prev.next == null) {
                System.out.println("位置がリストの範囲外です。");
                return;
            }
            prev = prev.next;
        }

        if (prev != null && prev.next != null) {
            prev.next = prev.next.next; // ノードを削除
        }
    }

    // リストの表示
    public static void printList() {
        ListElement current = listHead;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    // メイン関数
    public static void main(String[] args) {
        // リスト作成 (A → B → C → D)
        listHead = new ListElement('A');
        listHead.next = new ListElement('B');
        listHead.next.next = new ListElement('C');
        listHead.next.next.next = new ListElement('D');

        System.out.println("削除前のリスト:");
        printList();

        // ノードを削除 (例: 2番目の要素を削除)
        delNode(2);

        System.out.println("削除後のリスト:");
        printList();
    }
}

・Python でコーディング

class ListElement:
    def __init__(self, val):
        self.val = val         # 要素の値
        self.next = None       # 次の要素への参照


class SinglyLinkedList:
    def __init__(self):
        self.list_head = None  # リストの先頭要素

    def del_node(self, pos):
        if pos <= 0:
            print("無効な位置です。")
            return

        if pos == 1:  # 先頭の削除
            if self.list_head is not None:
                self.list_head = self.list_head.next
            return

        prev = self.list_head
        for _ in range(2, pos):  # pos - 1 まで進む
            if prev is None or prev.next is None:
                print("位置がリストの範囲外です。")
                return
            prev = prev.next

        if prev is not None and prev.next is not None:
            prev.next = prev.next.next  # ノードを削除

    def print_list(self):
        current = self.list_head
        while current is not None:
            print(current.val, end=" ")
            current = current.next
        print()


# メイン関数
if __name__ == "__main__":
    # リスト作成 (A → B → C → D)
    linked_list = SinglyLinkedList()
    linked_list.list_head = ListElement('A')
    linked_list.list_head.next = ListElement('B')
    linked_list.list_head.next.next = ListElement('C')
    linked_list.list_head.next.next.next = ListElement('D')

    print("削除前のリスト:")
    linked_list.print_list()

    # ノードを削除 (例: 2番目の要素を削除)
    linked_list.del_node(2)

    print("削除後のリスト:")
    linked_list.print_list()

以上。

いいなと思ったら応援しよう！