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

選択肢

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

正解と解説

正解：エ 末尾のデータを削除する処理

単方向リストでは各ノードが次のノードだけを指す。末尾のデータを削除するには、新しい末尾となる「最後から2番目」のノードのポインタを書き換える必要があり、そのノードへは先頭からたどるしかない。末尾ポインタがあっても手前には戻れないため、リスト全体をほぼ一巡することになり、たどる回数が最も多くなる。

選択肢ごとの解説

• ア先頭への追加は、新しいノードの次を旧先頭にして先頭ポインタを更新するだけで、たどる回数はごくわずかである。
• イ先頭の削除も、先頭ポインタを2番目のノードに付け替えるだけで済む。
• ウ末尾への追加は、末尾ポインタが指すノードの次に新ノードをつなぎ、末尾ポインタを更新するだけでよい。
• エ正しい。最後から2番目のノードを先頭からたどって探す必要があるため、たどる回数が最も多い。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
• 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3