2017年春期の過去問題を解いていく、その8。
思考過程をメモしながら解いていって、最後に答え合わせ、考察を入れます。
2017年の各種過去問題は以下のウェブページから自由に閲覧できます。
IPA 独立行政法人 情報処理推進機構：問題冊子・配点割合・解答例・採点講評（2017、平成29年）
今回は午後の問題の問3から。
午後の問題は選択式ですが、いちおうすべての問題を見ていこうと思います。
問3
問3、設問1
今回は問題文を全部読む前に設問をざっと見ておきました。
設問を先に見ておく事で、後から改めて問題文に戻って内容を思い出したりする手間が省けます。
試験の時間は限られているので、少しでも効率良く問題を解けるように工夫するのも重要になりますね。
その結果、設問3から解くことになりました。
設問1は2番目に解いています。
探索処理関数の中身を完成させる問題となります。
表2の関数とかを使って埋めていくという事だろうと思う。
まずアはループの条件ということで、キューが空になるまで回す事になると思うので「isEmpty()」ですね。
イは回答の候補がnullの場合の処理で、取得した状態を回答の候補にするという処理。
「ansStatus ← currentStatus」かな。
ウも回答の候補の更新だから「ansStatus ← currentStatus」かな。
エは次の数があるかどうかを判定したいので、Status-nextIndexが0かどうかってことですかね。「currentStatus-nextIndexが0ではない」かな。
ア：isEmpty()
イ：ansStatus ← currentStatus
ウ：ansStatus ← currentStatus
エ：currentStatus-nextIndexが0ではない
問3、設問2
設問２は最後に解くことになりました。
最後はフラグの設定ですね。「探索中止」か「探索継続」が入ることでしょう。targetを超えたら処理を終えたいので、オが「探索中止」ですね。
オ：探索中止
カ：探索継続
問3、設問3
問題文の中で、まず最初にこの設問3に関係する「下線①」が出てきます。なので設問3からまずは詳しくみていきます。
（１）に関して、データ構造をキューにした場合の評価順序ですね。キューなので単純にアルゴリズムに沿って参照した順に評価されるはず。
- まずは初期状態（A）がキューに格納される。
- 初期状態（A）がキューから取り出される。（A）を取得した状態の評価をする。
- この時点では回答の候補はnullなので、初期状態（A）を回答の候補にする。
- 次の数が10なので、10を選択した状態（B）と、10を選択しない状態（C）をキューに格納する。
- 状態（B）がキューから取り出される。（B）を取得した状態を評価する。
- 状態（B）の解答の候補はnullなので、状態（B）を回答の候補にする。
- 次の数34を選択した状態（D）と、選択しなかった状態（E）をキューに格納する。
- キューには（E、D、C）が格納されている。
- 状態（C）がキューから取り出され、この状態を評価する。
- 状態（C）の解答の候補はnullなので、状態（C）を回答の候補にする。
- 状態（C）の次の数34を選択した状態（F）と、選択しなかった状態（G）を選択する。
- キューには（G、F、E、D）が格納される。
- この後の状態は考えなくていいので、キューはこれで完成。あとは順番に後ろからD、E、F、Gと評価されていく。
（2）について考える。
まず最初に（A）がスタックに入り、すぐに（A）が評価される。
次に（B）、（C）の順にスタックに入り、後から入った（C）が評価される。
（C）が評価されるとスタックに（F）、（G）が順に格納される。
スタックは（G）、（F）、（B）が格納された状態。
後から入った順に（G）、（F）と評価される。この時新たにスタックに追加される状態は無い。
スタックに残っている（B）が評価される。
スタックには（D）、（E）が順に格納される。
後から入った順に（E）、（D）と評価される。
（１）、（A）、（B）、（C）、（D）、（E）、（F）、（G）
（２）、（A）、（C）、（G）、（F）、（B）、（E）、（D）
問3、設問4
木構造のデータをキューを使って処理していくときに必要になるメモリの量か。どうやって計算するんだろ。
nが1の場合のメモリ消費は1mになってないと困るので、1mより大きくなってしまうア、イ、オは除外される。残るはウとエのどちらか。
nが2の場合は2mになるはずなので、当てはまるのはウのみ。
私の答え：ウ
問3、設問5
うーんなんだろう。前処理か。ああ、昇順にソートするってことか。
前処理の内容：数字が昇順になるようにソートする（16文字）
理由：合計が目標Xを超えた時に計算を止めることが出来る（24文字）
答え合わせ
- 設問1(ア)isEmpty()が0である 不正解
- 設問1(イ)ansStatus ← currentStatus 正解
- 設問1(ウ)ansStatus ← currentStatus 正解
- 設問1(エ)currentstatus.nextIndexが0ではない 不正解（記号が微妙に違ってた）
- 設問2(オ)"N" 不正解
- 設問2(カ)"Y" 不正解
- 設問3(1)A→B→C→D→E→F→G 正解
- 設問3(2)A→C→G→F→B→E→D 正解
- 設問4 ア 不正解
- 設問5(内容)数を降順にソートしておく 不正解
- 設問5(理由)早い段階で探索を打ち切る事ができる。 不正解
11問中4問正解。意外とボロボロだった。
考察
設問２は問題文を良く見ていなかったがための悲しいミス…
パソコンで見てるから見ずらいんですよ。考え方はあってるのに回答をミスるのが一番もったいない…
設問4は根本的に考え方が違っていたようだ…
設問5は考え方が微妙に違ってた。もうちょっとちゃんと考えないとだめだったなぁ。
プログラムの問題だし余裕だろうと調子に乗っていた。自分って駄目なプログラマーなんだなと思った。
疑似コードを使った問題のパターンに慣れておかないといけないな。
他の選択問題に比べると点数が取りやすそうなので、ここの対策はしっかりしておきたい。
今回はこんなところで。
