【応用情報】データ構造解けなかった問題メモ

平成28年春期　問5

A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。

平成25年秋期　問6

葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

枝の個数がnならば，葉を含む節点の個数もnである。
木の深さがnならば，葉の個数は2n-1である。
節点の個数がnならば，深さはlog2nである。
葉の個数がnならば，葉以外の節点の個数はn－1である。

平成24年秋期　問5

配列を用いてスタックを実現する場合の構成要素として，最低限必要なものはどれか。

スタックに最後に入った要素を示す添字の変数
スタックに最初に入った要素と最後に入った要素を示す添字の変数
スタックに一つ前に入った要素を示す添字の変数を格納する配列
スタックの途中に入っている要素を示す添字の変数

平成21年春期　問20

データ構造のキューを実現する方法において，片方向リンクに比べた場合の双方向リンクの特徴として，適切なものはどれか。

片方向リンクよりオーバヘッドが小さい。
追加は，最後尾だけに対して行える。
途中への挿入・取外しが容易に行える。
取外しは，先頭だけに対して行える。

参考
ヒープは最小値（または最大値）を求めるのに適した木構造の一種であり、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ。子要素が複数ある場合、子要素間の大小関係に制約はない。
フィボナッチヒープの場合、挿入や最小値検索やマージが一定償却時間で行え、削除は O(log n) で行える。
優先度つきキューの実装としても使われる。プリム法やダイクストラ法などのグラフ問題のアルゴリズムでも使われている。

平成17年秋期　問11

キューの実装のうち，キューへの追加と取出しの手間が最少のものはどれか。ここで，キューの要素数は可変とし，図中の矢印は，ポインタの指示を表す。

平成22年春期　問6

指定された点が指定された多角形の内部にあるか外部にあるかを判定したい。多角形のすべての辺について，点から水平に延ばした半直線との交差回数を調べる。点Aのように交差回数が奇数回ならば内部，点Bのように交差回数が偶数回又は0ならば外部とする。点Cのように半直線が多角形の頂点上を通過する場合，二つの辺の端点(上端又は下端)と交差することになるが，このときの交差回数の数え方として，適当なものはどれか。ここで，多角形に水平な辺はないものとし，辺の上の点は考えない。