応用情報技術者試験 応用情報技術者試験 令和元年度秋期 午前 問6: 先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数

問題本文

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

選択肢

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

正解

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

解説

単方向リストは各データが「次のデータの番地」だけを持つため、ある位置の直前のデータを知るには先頭から順にポインタをたどるしかない。末尾を削除すると、新たに末尾となる「末尾の1つ手前」のデータのポインタを書き換える必要があるが、その位置は末尾ポインタからは戻れず先頭からたどるしかないため、要素数が多いほどたどる回数が最大になる。よって正解は エ である。

選択肢ごとの解説

• ア.先頭への追加は、新データのポインタを旧先頭に向け、先頭ポインタを新データに付け替えるだけで、ポインタをたどる必要がなく(0回)、最多ではない。
• イ.先頭の削除は、先頭ポインタを2番目のデータへ付け替えるだけで、たどるのは先頭ポインタ程度であり最多ではない。
• ウ.末尾への追加は、末尾ポインタが末尾の位置を直接指しているので、そこへ新データをつなぐだけで済み、先頭からたどる必要がなく最多ではない。
• エ.末尾の削除では新しい末尾(末尾の1つ手前)のポインタを書き換える必要があるが、単方向では直前の番地が分からず先頭からたどるしかないため、たどる回数が最も多い。正しい。