基本情報技術者試験（FE）｜科目A データ構造・アルゴリズム問題01
問題 1
二回のpop()で取り出される要素を、取り出す順に並べたものはどれか。
解説を見る
最初の三回のpush後は下からA、B、Cの順であり、最初のpop()は最後に入れたCを取り出す。次にDをpushするとDが最上部になるため、二回目はDを取り出す。スタックは最後に格納した要素を先に取り出すLIFOである。
問題 2
この後、キューが空になるまでdequeue()を繰り返したときの取出し順はどれか。
解説を見る
最初の二回のdequeue()ではA、Bがこの順に取り出され、未取出しのCが先頭に残る。その後D、Eを末尾へ追加するので、残りの論理順序はC、D、Eである。循環配列上で格納位置が折り返しても、FIFOの順序は変わらない。
問題 3
Qへの参照を失わずに挿入する代入の順序として適切なものはどれか。
解説を見る
まずR.nextにQを設定してRから元の後続節へつなぎ、その後P.nextをRへ変更する。P.nextを先にRへ変更してからR.nextへP.nextを代入すると、R自身を指す循環ができ、Qへの参照を失う。
問題 4
キー24が格納される添字はどれか。
解説を見る
10 mod 7、17 mod 7、24 mod 7はいずれも3である。10を添字3、衝突した17を次の添字4へ格納するため、24は3、4の順に調べた後の空きである添字5へ入る。衝突したキーで既存要素を上書きしてはならない。
問題 5
この木を左部分木、節、右部分木の順に間順走査した結果はどれか。
解説を見る
左部分木では1、3、6の順、次に根8、右部分木では10、14の順に訪問する。したがって1、3、6、8、10、14となる。二分探索木を間順走査するとキーを昇順に取り出せる。
問題 6
頂点をキューから取り出して処理する順序はどれか。
解説を見る
Aの処理でB、Cをキューへ入れる。次にBを処理してDを追加し、Cを処理するとDは訪問済みなのでEだけを追加する。キューの順に取り出すとA、B、C、D、Eとなる。A、B、Dと一つの経路を深くたどるのは深さ優先探索に近い。
問題 7
AからDへの最短経路と重みの合計の組合せはどれか。
解説を見る
A→C→B→Dの重みは1＋2＋1＝4であり、A→B→Dの5、A→C→Dの6より小さい。辺の本数が増えても重みの合計が小さければ最短経路になり得る。A→B→C→DはB→Cの辺がないため経路として成立しない。
問題 8
f(4)の返却値はどれか。
解説を見る
f(4)＝4×f(3)＝4×3×f(2)＝4×3×2×f(1)であり、基底条件からf(1)＝1なので24となる。10は4＋3＋2＋1と加算した場合の値、16は4を二乗した値である。
問題 9
処理Xの総実行回数と、この処理の時間計算量の組合せはどれか。
解説を見る
内側のループはi＝1、2、…、nに対してそれぞれi回実行される。総数は1＋2＋…＋n＝n(n＋1)/2回で、最高次の項はn^2/2なので定数係数と低次項を除いた時間計算量はO(n^2)である。
問題 10
整列後の順序はどれか。
解説を見る
得点の昇順なので70点の二件が先、90点の二件が後になる。安定な整列では同じキーを持つ要素の元の相対順序を保つため、70点はBの後にD、90点はAの後にCとなる。選択肢2は得点順だが同点者の順序を逆転させている。