応用情報技術者過去問題 平成22年春期 午後問2

問2 プログラミング

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

 PCのデスクトップ上の好きな位置に付箋(ふせん)を配置できるアプリケーションの実行イメージを図1に,付箋1枚のデータイメージを図2に示す。
pm02_1.gif/image-size:439×177
 複数の付箋データを管理する方法として,配列と双方向リスト(以下,リストという)のいずれがよいかを検討することにした。そこで,図1の付箋③のようにほかの付箋の背後にある付箋を一番手前に移動するアルゴリズムを,配列とリストそれぞれで実装して比較検討する。使用する構造体,配列,定数,変数及び関数を表に示す。また,図1の付箋①〜⑤を順番に,配列及びリストにそれぞれ格納した際のイメージを図3,4に示す。
 なお,配列及びリストの末尾に近い付箋データほど,デスクトップ上の手前に表示される。
pm02_2.gif/image-size:532×758
 構造体の要素は"."を使った表記で表す。"."の左には,構造体を表す変数又は構造体を参照する変数を書く。"."の右には,要素の名前を書く。配列の場合,図3の付箋⑤のメモ内容は MemoArray[4].text,また,リストの場合,図4の付箋②のIDは headNode.nextNode.data.id と表記できる。

〔関数 moveForeArray〕
関数 moveForeArray の処理手順を次の(1)〜(4)にそのプログラムを図5に示す。
  • 配列中の付箋IDが id である付箋データの添字を取得する。
  • 配列中の(1)で取得した位置の付箋データを一時変数へ退避する。
  • 配列中の(1)で取得した位置の次から配列の最後の付箋データがある位置までの付箋データを一つずつ前へずらす。
  • 配列中の最後の付箋データがあった位置へ(2)で退避した付箋データを代入する。
pm02_3.gif/image-size:324×183
〔関数 moveForeList〕
 関数 moveForeList の処理手順を次の(1)〜(4)に処理手順中の(3)(A)及び(4)の操作を図6に示す。また,関数 moveForeLis tのプログラムを図7に示す。
  • リストから,付箋IDが id である付箋データをもつノードへの参照を取得する。
  • (1)で取得したノード(ノードk)が末尾ノードの場合,処理を終了する。
  • ノードkが先頭ノードの場合は(@)を,そうでない場合は(A)を実行する。ここで,ノードkの次ノードをノードk+1,前ノードをノードk−1と呼ぶ。
    1. リストの先頭ノードへの参照をノードk+1への参照に変更し,ノードk+1中の前ノードへの参照をnullに変更する。
    2. ノードk−1中の次ノードへの参照をノードk+1への参照に変更し,ノードk+1中の前ノードへの参照をノードk−1への参照に変更する。
  • リストの末尾ノード(ノードn)中の次ノードへの参照をノードkへの参照に,ノードk中の前ノードへの参照をノードnへの参照に変更する。ノードk中の次ノードへの参照をnullに,リストの末尾ノードへの参照(tailNode)をノードkへの参照に変更する。
pm02_4.gif/image-size:478×590
〔二つのアルゴリズムに関する考察〕
 まず,時間計算量について考える。配列の場合,末尾へ移動する要素より後のすべての要素をずらす必要が生じる。この処理の計算量はである。リストの場合,末尾へ移動する付箋データの位置にかかわらず,少数の参照の変更だけでデータ同士の相対的な位置関係を簡単に変えられる。この処理の計算量はである。
 次に,必要な領域の大きさについて考える。付箋データ1個当たりの領域の必要量は,配列の方が小さい。リストは参照を入れる場所を余分に必要とする。しかし,全体で必要とする領域は,配列の場合,しておかなければならない。リストの場合,配置されている付箋データの個数分だけ領域を確保すればよい。

設問1

図1の付箋①〜⑤を格納した図3の配列及び図4のリストについて,(1),(2)に答えよ。
  • 配列に格納されている,付箋①の高さ20を求める適切な式を答えよ。
  • tailNode.prevNode.data.heightの値を答えよ。

-解答入力欄-

-解答例・解答の要点-

    • MemoArray[0].height
    • 30

-解説-

この設問の解説はまだありません。

設問2

図5中のに入れる適切な字句を答えよ。

-解答入力欄-

  • ア:
  • イ:

-解答例・解答の要点-

  • ア:MemoArray[index]
  • イ:MemoArrayCount−1

-解説-

この設問の解説はまだありません。

設問3

図7中のに入れる適切な字句を答えよ。

-解答入力欄-

  • ウ:
  • エ:

-解答例・解答の要点-

  • ウ:node.nextNode.prevNode ← node.prevNode
  • エ:node.prevNode ← tailNode

-解説-

この設問の解説はまだありません。

設問4

〔二つのアルゴリズムに関する考察〕について,(1),(2)に答えよ。
  • 本文中のに入れる適切な字句をO記法で答えよ。
     なお,配列及びリスト中の付箋データの個数をnとし,関数 findArrayIndex 及び関数 findListNode の計算量は無視する。
  • リストの場合,配置されている付箋データの個数分だけ領域を確保すればよ
    いのに対し,配列の場合はどうしなければならないのか。に入れる適切な字句を30字以内で答えよ。

-解答入力欄-

    • オ:
    • カ:
    • キ:

-解答例・解答の要点-

    • オ:O(n)
    • カ:O(1)
    • キ:デスクトップに配置できる付箋の最大数分の領域を確保 (25文字)

-解説-

この設問の解説はまだありません。
問2成績
【22年春期 午後問題】
 問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12
© 2010-2019 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop