読み込み中
問題 #14 ・ リスト・スタック・キュー ・ 難易度 3
次のプログラムは、単方向連結リストの先頭ノードを受け取り、リストの要素の並びを反転させた新しい先頭ノードを返す関数 reverse である。プログラム中の〔 a 〕と〔 b 〕に入れる字句の正しい組合せを、選択肢の中から選べ。 ここで、連結リストの各ノードは次の構造をもつクラス Node で表される。 ┌──────────────────────────┐ │ クラス Node │ │ 整数型: value … ノードが保持する値 │ │ Node: next … 次のノードへの参照 │ │ （末尾は未定義） │ └──────────────────────────┘ 例えば、value が 1, 2, 3 の順に並ぶリスト（先頭が 1）を渡すと、value が 3, 2, 1 の順に並ぶリスト（先頭が 3）を返す。
○Node: reverse(Node: head)Node: prev ← 未定義Node: curr ← headNode: tmpwhile (curr ≠ 未定義)tmp ← curr.nextcurr.next ← 〔 a 〕prev ← currcurr ← 〔 b 〕endwhilereturn prev
この関数は「反復によるリスト反転」の典型的なアルゴリズムである。ポインタ prev, curr, tmp の3つを使い、先頭から順にリンクの向きを逆にしていく。 ■ 動作の流れ（1 → 2 → 3 の例） 【初期状態】 prev=未定義, curr=Node(1) --- 1回目のループ --- tmp ← curr.next → tmp=Node(2) curr.next ← prev(=未定義) → Node(1).next=未定義 prev ← curr → prev=Node(1) curr ← tmp → curr=Node(2) リスト状態: 1→未定義 2→3→未定義 --- 2回目のループ --- tmp ← curr.next → tmp=Node(3) curr.next ← prev(=Node(1)) → Node(2).next=Node(1) prev ← curr → prev=Node(2) curr ← tmp → curr=Node(3) リスト状態: 2→1→未定義 3→未定義 --- 3回目のループ --- tmp ← curr.next → tmp=未定義 curr.next ← prev(=Node(2)) → Node(3).next=Node(2) prev ← curr → prev=Node(3) curr ← tmp → curr=未定義 リスト状態: 3→2→1→未定義 ループ終了。return prev → Node(3) が新しい先頭。 したがって、〔 a 〕= prev、〔 b 〕= tmp が正解であり、選択肢エが正しい。
登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。
この問題は AI が作り、別の AI に解かせて検証し、人が確認したうえで公開しています。 誤りに気づいたら goku.tore9@gmail.com までお知らせください。
記号の意味に迷ったら擬似言語の記法で確かめられます。