うごく基本情報

サンプル問題セット(2022年12月公開) 科目B 問10

単方向リスト ・ 参照

次のプログラム中の[ ]に入れる正しい答えを,解答群の中から選べ。
手続 delNode は,単方向リストから,引数 pos で指定された位置の要素を削除する手続である。引数 pos は,リストの要素数以下の正の整数とする。リストの先頭の位置を 1 とする。
クラス ListElement は,単方向リストの要素を表す。クラス ListElement のメンバ変数の説明を表に示す。ListElement 型の変数はクラス ListElement のインスタンスの参照を格納するものとする。大域変数 listHead には,リストの先頭要素の参照があらかじめ格納されている。
表クラス ListElement のメンバ変数の説明メンバ変数型説明val 文字型要素の値next ListElement[ ]次の要素の参照次の要素がないときの状態は未定義

大域: ListElement: listHead  // リストの先頭要素が格納されている

○delNode(整数型: pos)  /* posは,リストの要素数以下の正の整数 */
  ListElement: prev
  整数型: i
  if (pos が 1 と等しい)
    listHead ← listHead.next
  else
    prev ← listHead
    /* posが2と等しいときは繰返し処理を実行しない */
    for (i を 2 から pos - 1 まで 1 ずつ増やす)
      prev ← prev.next
    endfor
    prev.next ← [ a ]
  endif
a
アlistHead
イlistHead.next
ウlistHead.next.next
エprev
オprev.next
カprev.next.next

出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問10

正解と解説を見る

正解:カ

ポイント:単方向リストから要素を消す:1つ前の要素の next を、消す要素の次(prev.next.next)につなぎ替える。

pos 番目の要素を消す手続です。pos が 1 のときは、先頭を次の要素に変えるだけです。
2 以上のときは、for 文で prev を pos-1 番目の要素まで進めます(pos=2 なら繰り返さず、prev は先頭のまま)。消す要素は prev.next で、その次の要素は prev.next.next です。prev.next を prev.next.next につなぎ替えれば、pos 番目の要素はリストからたどれなくなり、消えたことになります(カ)。
例:a → b → c → d で pos=3 なら、prev は b。b.next を c.next(=d)にして、a → b → d になります。
オ(prev.next):自分に自分を入れるだけで、何も変わりません。
エ(prev):b.next ← b となり、b が自分自身を指す輪になってしまいます。
ア〜ウ:listHead からの位置で、pos によっては別の要素につながってしまいます。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

サイトで、1行ずつ動かして読む →