応用情報技術者 2010年 春期 午後 問02

解答の論理構成

1. 付箋①が配列中のどの添字に入るかを確認します。問題文には
   「図1の付箋①〜⑤を順番に、配列及びリストにそれぞれ格納した際のイメージを図3、4に示す。」
   とあり、図3では左から順に①→②→③→④→⑤ が並んでいます。
2. 配列の添字規則について、問題文は
   「配列の添字は 0 から始めるものとする。」
   と明示しています。したがって先頭の付箋①は添字「0」です。
3. 構造体要素の表記規則は
   「構造体の要素は“.” を使った表記で表す。」
   と定義されており、具体例として
   「図3の付箋⑤のメモ内容は MemoArray[4].text」
   が示されています。
4. 付箋①の高さを取得したいので要素名は height を使います。
5. 以上より、配列 MemoArray の先頭要素（添字 0）の高さは
   MemoArray[0].height
   となります。

誤りやすいポイント

• 添字を「1」から始まると勘違いして MemoArray[1].height としてしまう。
• 構造体要素の区切りを -> やドットを忘れて MemoArray[0]height と書く記述ミス。
• リストと混同し、headNode.data.height としてしまう。

FAQ

解答の論理構成

1. 「図1の付箋①〜⑤を順番に、配列及びリストにそれぞれ格納した際のイメージを図3、4に示す。」とあるので、図4（リスト）の順序は①→②→③→④→⑤です。
2. 図4では最後尾（末尾）ノードが付箋⑤であり、リストの末尾を指す変数は tailNode です。したがって
   • tailNode … ⑤のノード
   • tailNode.prevNode … ⑤の直前、すなわち付箋④のノード
3. ノードが保持する付箋データは構造体 Memo であり、その要素の一つが height です（表「Memo : width, height」より）。よって求める値は「付箋④の高さ」。
4. 図1には等間隔のグリッドが描かれ、1目盛＝10 の縮尺になっています。付箋④は縦方向に3目盛分に相当する大きさで描かれているため
   $10\times 3=30$
   したがって tailNode.prevNode.data.height は 30 になります。

誤りやすいポイント

• tailNode を「先頭ノード」と取り違え、付箋①や②の高さを答えてしまう。
• prevNode と nextNode を混同し、tailNode.nextNode を参照しようとして null になるケース。
• 図1の縮尺（1目盛がいくつか）を読み違え、5目盛＝50 などと誤計算してしまう。

FAQ

解答の論理構成

1. 退避すべき付箋データ
   手順 (2) では「配列中の (1) で取得した位置の付箋データを一時変数へ退避する。」とあります。プログラムではその“位置”を変数 index に格納しているので、退避対象は MemoArray[index] です。したがって ア は 「MemoArray[index]」 となります。
2. for ループの終端値
   手順 (3) では「配列中の (1) で取得した位置の次から配列の最後の付箋データがある位置まで」を前へずらします。“最後の付箋データがある位置”は、現在格納されている要素数 memoArrayCount の直前の添字、すなわち memoArrayCount−1 です。プログラムの for ループで i をその添字まで増やす必要があるので、 イ は 「memoArrayCount−1」 になります。
3. 末尾への再配置
   手順 (4) では「配列中の最後の付箋データがあった位置へ (2) で退避した付箋データを代入する。」とあるため、ループ終了後の添字も memoArrayCount−1 で一致し、全体の整合性が取れます。

誤りやすいポイント

• 「最後の付箋データ」を固定長配列の末尾（MEMO_MAX_SIZE−1）と混同しやすい。実際には現在の要素数 memoArrayCount を基準にする点に注意。
• index の要素を退避せずに上書きしてしまい、データが失われるケース。
• ループ条件を i < memoArrayCount−1 と書き、最終要素をずらし損ねるミス。

FAQ

解答の論理構成

1. 前提
   問題文には、末尾以外にあるノードをリストの末尾へ移動する処理として、
   “(4) リストの末尾ノード（ノードn）中の次ノードへの参照をノードkへの参照に、ノードk中の前ノードへの参照をノードnへの参照に変更する。ノードk中の次ノードへの参照をnullに、リストの末尾ノードへの参照（tailNode）をノードkへの参照に変更する。”
   と記載されています。これをコード化したものが図7です。
2. 先頭ノード以外の場合の分岐
   先に “node.prevNode.nextNode ← node.nextNode” で k−1 が k+1 を指すようにし、さらに k+1 が k−1 を指す必要があります。
   したがって ウ には
   node.nextNode.prevNode ← node.prevNode
   が入ります。
3. 末尾側へ連結する処理
   既存の末尾ノード（tailNode）から新たに移動するノード k への参照は、図7中に既に “tailNode.nextNode ← node” と書かれています。
   続いてノード k の prevNode を tailNode に向け替える必要があります。
   よって エ には
   node.prevNode ← tailNode
   が入ります。
4. これにより、
   ・リストからノード k を一度切り離す
   ・旧 tailNode とノード k を相互接続する
   ・node.nextNode を null、tailNode を node に更新する
   という“(4)”で要求された操作がすべて満たされ、整合性が保たれます。

誤りやすいポイント

• prev と next を取り違えて循環参照や断絶を起こす
• “node.nextNode ← null” を忘れ、末尾ノードが次ノードを保持してしまう
• headNode や tailNode の更新順序を誤り、一時的にリスト構造が壊れる
• 先頭ノードだった場合とそれ以外の場合の分岐を混同する

FAQ

解答の論理構成

• 問題文は、配列の場合について「末尾へ移動する要素より後のすべての要素をずらす必要が生じる」と述べています。これは要素数を $n$ とすると最悪で $n-1$ 回のコピーが必要であり、時間計算量はサイズに比例します。
  ⇒ $[オ]=O(n)$
• リストの場合については「少数の参照の変更だけでデータ同士の相対的な位置関係を簡単に変えられる」とあります。双方向リストではノードの切り離しと末尾への再接続は固定回数のポインタ書き換えで済み、要素数に依存しません。
  ⇒ $[カ]=O(1)$
• 設問中で「関数findArrayIndex及び関数findListNodeの計算量は無視する」と明示されているため、探索コストを考慮する必要はありません。したがって上記がそのまま最終答となります。

誤りやすいポイント

• findArrayIndex や findListNode の線形探索を含めてしまい、リスト側まで $O(n)$ と誤答する。
• 配列のシフトで平均ケース（約 $n/2$ 要素移動）を考え、$O(n/2)$ と書く。定数倍は O 記法では無視される点を失念。
• リストで「末尾ポインタ更新」を忘れ、操作回数が増えると誤解して $O(n)$ としてしまう。

FAQ

解答の論理構成

1. 問題文はメモリ使用量の比較を次のように示しています。

   「全体で必要とする領域は、配列の場合、キ としておかなければならない。リストの場合、配置されている付箋データの個数分だけ領域を確保すればよい。」
   この一文から、配列では“現在の個数”ではなく“最大個数”を見込んだ領域確保が必要であることが読み取れます。

2. そもそも配列は宣言時に連続領域を確保する静的データ構造です。途中でサイズを伸縮できないため、最初に「最悪の場合」を想定した長さを確保しておく必要があります。
3. 本問で配列のサイズを決める指標は、定数「MEMO_MAX_SIZE」に対応する次の記述です。

   「MEMO_MAX_SIZE: デスクトップに配置できる付箋の最大数。」

4. したがって [キ] には、配列が確保しなければならない領域量＝「デスクトップに配置できる付箋の最大数分の領域を確保」という趣旨の語句が入ります。
5. この結論をまとめると、[キ] は
   「デスクトップに配置できる付箋の最大数分の領域を確保」
   となります。

誤りやすいポイント

• 「配列＝メモリ効率が良い」と短絡的に考え、最大数ではなく「現在数＋α」で十分だと誤解する。配列は伸縮しないため将来追加できなくなるリスクを見落としがちです。
• 「MEMO_MAX_SIZE」を単なる上限チェック用定数と捉え、メモリ確保量にまで関係すると気付かない。
• リストなら動的確保＝常に最小メモリ、配列は固定確保＝最大メモリという本質的な違いを混同し、両者の長所短所を取り違える。

FAQ