AP22春後問2

AP22春後問2

応用情報技術者試験平成22年度春午後問2

 アプリケーションで使用するデータ構造とアルゴリズムに関する次の記述を読んで,設問 1 ~ 4 に答えよ。

 PC のデスクトップ上の好きな位置に付箋を配置できるアプリケーションの実行イメージを図 1 に,付箋 1 枚のデータイメージを図 2 に示す。


f:id:tamagopanda:20100604212458p:image:leftf:id:tamagopanda:20100604212459p:image



 複数の付箋データを管理する方法として,配列と双方向リスト(以下,リストという)のいずれがよいかを検討することにした。そこで,図 1 の付箋 3 のようにほかの付箋の背後にある付箋を一番手前に移動するアルゴリズムを,配列とリストそれぞれで実装して比較検討する。使用する構造体,配列,定数,変数及び関数を表に示す。また,図 1 の付箋 1 ~ 5 を順番に,配列及びリストにそれぞれ格納した際のイメージを図 3,4 に示す。

 なお,配列及びリストの末尾に近い付箋データほど,デスクトップ上の手前に表示される。

※問題掲載者より注意

実際の試験問題文では,付箋 丸1~丸5(○の中に数字)でしたが,機種依存文字のため,付箋 1 ~ 5 (○なし)に置き換えて表記しています。

f:id:tamagopanda:20100604213436p:image


f:id:tamagopanda:20100604213535p:image


f:id:tamagopanda:20100604213536p:image



 構造体の要素は“.”を使った表記で表す。“.”の左には,構造体を表す変数又は構造体を参照する変数を書く。“.”の右には,要素の名前を書く。配列の場合,図 3 の付箋 5 のメモ内容は MemoArray[4].text,また,リストの場合,図 4 の付箋 2 の ID は headNode.nextNode.data.id と表記できる。

〔関数 moveForeArray〕

 関数 moveForeArray の処理手順を次の (1) ~ (4) に,そのプログラムを図 5 に示す。

(1) 配列中の付箋 ID が id である付箋データの添字を取得する。

(2) 配列中の (1) で取得した位置の付箋データを一時変数へ退避する。

(3) 配列中の (1) で取得した位置の次から配列の最後の付箋データがある位置までの付箋データを一つずつ前へずらす。

(4) 配列中の最後の付箋データがあった位置へ (2) で退避した付箋データを代入する。


function moveForeArray(id)

 index ← findArrayエndex(id)

 tempMemo ← [ ア ]

 for(i を index+1 から [ イ ] まで 1 ずつ増やす)

  MemoArray[i-1] ← MemoArray[i]

 endfor

 MemoArray [ イ ] ← tempMemo

endfunction

図5 関数moveForeArrayのプログラム


〔関数 moveForeList〕

 関数 moveForeList の処理手順を次の (1)~(4) に,処理手順中の (3) (ii) 及び (4) の操作を図 6 に示す。また,関数 moveForeList のプログラムを図 7 に示す。

(1) リストから,付箋 ID が id である付箋データをもつノードヘの参照を取得する。

(2) (1)で取得したノード(ノード k)が末尾ノードの場合,処理を終了する。

(3) ノード k が先頭ノードの場合は(i)を,そうでない場合は(ii)を実行する。ここでノード k の次メードをノード k+1,前ノードノード k-1 と呼ぶ。

 (i)リストの先頭ノードヘの参照をノード k+1 への参照に変し,ノード k+1 中の前ノードヘの参照を null に変する。

(ii)ノード k-1 中の次ノードヘの参照をノード k+1 への参照に変し,ノード k+1 中の前ノードヘの参照をノード k-1 への参照に変する。

(4)リストの末尾ノードノード n)中の次ノードヘの参照をノード k への参照に,ノード k 中の前ノードヘの参照をノード n への参照に変する。ノード k 中の次ノードヘの参照を null に,リストの末尾ノードヘの参照(tailNode)をノード k への参照に変する。


f:id:tamagopanda:20100606202431p:image


function moveForeList(id)

 node ← findListNode(1d)

 if(node.nextNode と null が等しい)

  // 末尾ノードの場合

  return

 endif

if(node.prevNode と null が等しい)

 // 先頭ノードの場合

 headNode ← node.nextNode

 node.nextNode.prevNode ← nu11

else

 // 先頭ノード以外の場合

 node.prevNode.nextNode ← node.nextNode

endif

tallNode.nextNode ← node

 node.nextNode ← null

 tailNode ← node

endfunction

図7 関数 moveForeList のプログラム


〔二つのアルゴリズムに関する考察〕

 まず,時間計算量について考える。配列の場合,末尾へ移動する要素より後のすべての要素をずらす必要が生じる。この処理の計算量は[ オ ]である。リストの場合,末尾へ移動する付箋データの位置にかかわらず,少数の参照の変だけでデータ同士の相対的な位置関係を簡単に変えられる。この処理の計算量は[ カ ]ある。

 次に,必要な領域の大きさについて考える。付箋データ1 個当たりの領域の必要量は,配列の方が小さい。リストは参照を入れる場所を余分に必要とする。しかし,全体で必要とする領域は,配列の場合,[ キ ]しておかなければならない。リストの場合,配置されている付箋データの個数分だけ領域を確保すればよい。


設問1

 図 1 の付箋 1 ~ 5 を格納した図 3 の配列及び図 4 のリストについて,(1),(2) に答えよ。

 (1) 配列に格納されている,付箋 1 の高さ 20 を求める適切な式を答えよ。

 (2) tailNode.prevNode.data.height の値を答えよ。


設問2

 図 5 中の [ ア ],[ イ ]に入れる適切な字句を答えよ。


設問3

 図 7 中の [ ウ ],[ エ ]に入れる適切な字句を答えよ。


設問4

〔二つのアルゴリズムに関する考察〕について,(1),(2) に答えよ。

 (1)本文中の [ オ ],[ カ ]に入れる適切な字句を O 記法で答えよ。なお,配列及びリスト中の付箋データの個数を n とし,関数 findArraylndex 及び関数 findListNode の計算量は無視する。

 (2)リストの場合,配置されている付箋データの個数分だけ領域を確保すればよいのに対し,配列の場合はどうしなければならないのか。 [ キ ] に入れる適切な字句を 30 字以内で答えよ。


問題掲載者による注意書き

  • 実際の問題文では,[ ア ][ イ ][ ウ ] 等は,四角で囲まれていたが,テキスト表現をするため,[ ]で置き換えた。