平成21年度 春期 午前 問5

✓ これが正解ウスタック

解説

後入れ先出しのスタックが呼出しに合います。

関数や手続の呼出しは入れ子になります。ある手続が別の手続を呼び、その先がさらに別の手続を呼ぶと、戻るときは最も内側から順に外へ向かって戻ります。したがって、戻り番地や途中のデータをしまう場所には、最後にしまったものを最初に取り出すという並び方が必要です。これを後入れ先出しといい、そのとおりに出し入れするデータ構造がスタックです。呼び出すたびに戻り番地とその時点のデータを積み、戻るときに上から取り出すので、入れ子がどれだけ深くなっても順序が崩れません。見分けるときの軸は、取り出す順序が呼出しの入れ子と合っているかどうかの一点です。同じ関数が自分自身を呼ぶ再帰的な呼出しが成り立つのも、この積み方が下にあるからです。

ほかの選択肢はなぜ違うのか

• ア2 分探索木：値の大小によって枝を分け、目的の要素を少ない回数で見つけるための構造を挙げています。探すことが本来の役目であり、出し入れの順序を呼出しの深さに合わせる働きは持ちません。
• イキュー：キューは先に入れたものから先に出す並び方なので、いちばん外側で呼ばれた手続の情報が最初に出てきます。内側から順に外へ戻るという流れとは向きが逆になります。
• エ双方向連結リスト：前後どちらの向きにもたどれる並びで、データをしまうこと自体はできます。ただし、どこから取り出すかは使う側が決める必要があり、戻る順序を構造として保証してくれません。