応用情報２２年秋　午前　問５ - 実践！情報処理試験講座

【中分類】
アルゴリズムとデータ構造−１．データ構造
　−（２）データ構造の種類−２．リスト

【問題を解く前に】
今回は、まず問題文の読み方について、この問題を例に説明します。

・問題文の読み方

　　１．はじめにざっと読み、何を聞いているか、確認する
　　　　→今回は、「ポインタをたどる回数が最も多いのはどれか。」

　　２．解答群をみて、解答のポイントをはっきりさせる。
　　　　→聞いていることは２つ。
　　　　　　・先頭と末尾
　　　　　　・追加と削除
　　　　　この組み合わせ

　　３．解答を解くための条件をおさえる。
　　　　　・先頭からつながる単方向の線形リスト
　　　　　・先頭、末尾ポインタは持っている
　　　　　・追加するデータは、すぐにわかる

　これは、情報処理試験に限らず、たいていの試験に使えます（２に関しては、択一式しか使えませんが）。ただし、ＴＯＥＩＣなどのヒアリング試験では、この方法は使えません（やり方が限定されます。ただし、それらにも解くテクニックがあるので、そういう試験を受ける人は、それらの試験の参考書を見てください）

【解き方】

まず、具体的に(数値を入れて）考えます。
５個のデータがあって、６個目を追加するとします。
こんな図

（Ａ）６個目のアドレスは、「追加するデータは、すぐにわかる」ということにより、　一発で見つかるとします。
（Ｂ）先頭アドレスと、末尾アドレスは、そのアドレスを持っているので、
　一発で見つかります。
（Ｃ）他のものについては、前から順にたどり、前のものがわかれば、次のものが一発で判る。

　つまり、２のアドレスは、１のアドレスがわかっていれば、一発。
　　　　　３のアドレスは、１のアドレスがわかっていれば、
　　　　　　　１→２→３で、２発。
　ということです。

さて、以下、問題文を考えていきます。

（ア）先頭に追加

すべき処理は
・先頭アドレスを見つける＊
　　→上記（Ｂ）より一発

・追加するアドレスを見つける
　　→上記（Ａ）より一発

・追加するアドレスを先頭アドレスエリアにコピー
　　→問題は、参照回数を聞いているので、コピー時間は含みません

・追加するアドレスのNEXTに、＊のアドレスをコピー
　　→問題は、参照回数を聞いているので、コピー時間は含みません

合計２発

(イ）先頭のデータを削除する処理

すべき処理は
・先頭アドレスを見つけます＊
　　→上記（Ｂ）より一発

・先頭の次のアドレスを見つけます★
　　→＊の次なので、一発

・★のアドレスを、先頭アドレスエリアにコピー
　　→問題は、参照回数を聞いているので、コピー時間は含みません

・＊をフリーする
　　→問題は、参照回数を聞いているので、フリー時間は含みません

合計２発

（ウ）末尾にデータを追加する処理
すべき処理は
・末尾のアドレスを見つける＊
　　→上記（Ｂ）より一発

・追加するアドレスを見つける★
　　→上記（Ａ）より一発

・末尾アドレスエリアに、★をコピーする
　　→問題は、参照回数を聞いているので、コピー時間は含みません

・＊のNEXTに、★をコピーする
　　→問題は、参照回数を聞いているので、コピー時間は含みません

合計２発

（エ）末尾を削除
すべき処理は
・末尾のアドレスを見つける＊
　　→上記（Ｂ）より一発

・末尾の前のアドレスを見つける★
　　→＊の前（prev）というのはないので、
　　　先頭→２→３→４と聞いていかないといけない■

・末尾アドレスエリアに★をコピー
　　→問題は、参照回数を聞いているので、コピー時間は含みません

・＊をフリーする
　　→問題は、参照回数を聞いているので、フリー時間は含みません

合計：一発＋■＝２発以上、たくさん。

【答え】
（エ）

【解き終わって】

　なお、この問題は、受験テクニック的にも、予想が付きます。

　先頭ポインタからつながっている
　　　　　　→たぶん、末尾のほうが大変なんだろう。

　追加する〜→追加が楽ということが言いたいらしい
　　　　　　→たぶん、削除のほうが大変なんだろう。

　聞いているのは、回数が多い→末尾の削除の組み合わせが一番大変？

　ただ、これは、危険な方法で、まじめにちゃんと解いたほうがいいです。
　もし、「まったく想像が付かない」などというときだけ、使ってください。

　それと、ポインタを使った、このようなリスト処理については、実務上も出来たほうがいいです（特にＣ言語を使っている人）。
　単方向(NEXTのみ）だけでなく、双方向リンク(NEXT,PREV両方持つ）の場合の追加、削除、検索処理は、おさえておいてください。

　なお、Ｃ言語以外の人は、このような処理は、Iteratorで内部的にやってくれます。なので、受験的に、上記のリンクについて覚えると同時に、自分の言語では、Iteratorをどのように使うのか？についても、確認しておいてください。

【受験テクニック】

・問題文の読み方
　　１．はじめにざっと読み、何を聞いているか、確認する
　　２．解答群をみて、解答のポイントをはっきりさせる。
　　３．解答を解くための条件をおさえる。

・具体的に(数値を入れて）考える
　　→これについては、注意点があります。その注意点も含めて、
　　　詳しい話は、問７で説明します。