メインコンテンツへ
アルゴリズムとプログラミング

双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員Gを社員Aと社員Kの間に追加する。追加後の表のポインタa~fの中で追加前と比べて値が変わるポインタだけを全て列記したものはどれか。

アドレス社員名次ポインタ前ポインタ
100社員A3000
200社員T0300
300社員K200100
アドレス社員名次ポインタ前ポインタ
100社員Aab
200社員Tcd
300社員Kef
400社員Gxy
ア.a、b、e、f
イ.a、e、f
ウ.a、f正解
エ.b、e

解説

双方向リストへの挿入は「行列に割り込む人の手つなぎ直し」。変わるのは割り込まれた隣人2人が新人Gへ向ける手(ポインタ)だけで、それ以外の手はそのまま。

なぜ ウ が正解か

GはAとKの間に入るので、AはNextを「K(300)」から「G(400)」に書き換える→これがa。KはPrevを「A(100)」から「G(400)」に書き換える→これがf。AのPrev(b)は元から0で変わらず、KのNext(e)は依然Tを指したまま、TのポインタはそもそもGの挿入点より遠くて無関係。だから変わるのはaとfの2本だけ。

なぜ ア は間違いか

bはAのPrevだが、AはリストのHead(前に誰もいない)なので挿入後も0のまま変わらない。eはKのNextでKの後ろはT——GはAとKの間に入ったのでKとTの関係は一切乱されない。b・eまで変わると思うのは「周辺全員の手を握り直す」イメージで、割り込み屋Gに全員巻き込まれすぎ。

なぜ イ は間違いか

eはKのNextポインタ(=T向き)で、GはKの前に入るのでKとTの繋がりは健在。「KのNext」はそのままTを指し続けるため変化なし。eを仲間に引き込んだ時点で1本多い。

なぜ エ は間違いか

bはAのPrev(=0、変化なし)、eはKのNext(=T向き、変化なし)を選んでいて、本当に変わるaとfを両方スルーしている。変えるべき手と変えなくていい手を完全に入れ替えた、ある意味パーフェクトな逆答案。

出典: 基本情報技術者試験 令和5年 公開問題