情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和元年度秋期 午前Ⅰ 問4: 先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数

問題本文

先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで，単方向のリストは先頭ポインタからつながっているものとし，追加するデータはポインタをたどらなくても参照できるものとする。

選択肢

• ア.先頭にデータを追加する処理
• イ.先頭のデータを削除する処理
• ウ.末尾にデータを追加する処理
• エ.末尾のデータを削除する処理

正解

エ. 末尾のデータを削除する処理

解説

単方向リストでは各ノードが次への一方向ポインタしか持たない。末尾の一つ前のノードのポインタを書き換える必要がある末尾削除では、先頭から末尾の手前まで全ノードをたどる必要があり最も多い。よってエが正解。先頭追加・先頭削除はポインタ操作のみ、末尾追加は末尾ポインタを使えるためたどり不要。データ構造ごとの操作コストの理解は基本である。

選択肢ごとの解説

• ア.先頭追加は新ノードを先頭ポインタにつなぐだけで、たどる回数は少なく誤り。
• イ.先頭削除は先頭ポインタを次ノードへ移すだけで完了し、たどる必要がなく誤り。
• ウ.末尾追加は末尾ポインタから直接末尾を参照でき、たどる回数は少ないため誤り。
• エ.末尾削除は末尾の前ノードを探すため先頭からほぼ全件たどる必要があり、最も多く正しい。