第1種情報処理技術者試験 1995年度 = 平成7年度 午前 問7

 図のような構造をもった線形リストについて、正しい記述はどれか。


ア 要素の値で整列されたリストとなるように挿入と削除を行う場合には、最後尾へのポインタを使用すると更新の処理量が平準化される。
イ 要素の削除に要する処理量は、先頭と最後尾とでほぼ同じである。
ウ 要素の追加と取出し(読出し後削除)を最後尾で行うスタックとしての利用に適している。
エ 要素の追加に要する処理量は、先頭と最後尾とでほぼ同じである。
オ 要素の追加は先頭に、取出し(読出し後削除)は最後尾からするとFIFO (First-In First-Out) のキューとしての利用に適している。

解答



解説

 先頭への追加と取出し、最後尾への追加と取出しは、以下に示す処理で実現します。

■先頭への追加
・ポインタHeadが、追加する要素を指すように変更する。
・追加する要素のポインタが、E1を指すように変更する。

■先頭からの取出し
・ポインタHeadが、E2を指すように変更する。

■最後尾への追加
・E4のポインタが、E1を指すように変更する。
・ポインタTailが、追加する要素を指すように変更する。

■最後尾からの取出し
・E3のアドレスを得るために、先頭からE1→E2→E3とたぐる(煩雑!)。
・E3のポインタが、どこも差さないように変更する。
・ポインタTailが、E3を指すように変更する。

 〔最後尾からの取出し〕は煩雑ですから、正解は選択肢です。


BohYoh.comトップページへ