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

⇄問題文と設問を画面2分割で開く⇱問題PDF⇱解答用紙PDF

問2 プログラミング

文字列を圧縮するアルゴリズムに関する次の記述を読んで,設問1〜4に答えよ。

 データを圧縮するアルゴリズムの一つにランレングス法がある。ランレングス法とは,同じデータが連続して現れる箇所を,そのデータと連続している回数との組に変換する方法である。文字"a"〜"z"だけから成る文字列を圧縮する方法として,圧縮の表現形式の違う二つのプログラムを比較検討する。
 圧縮前と圧縮後のデータを管理する方法として配列を用いる。配列の各要素には,文字データの場合は8ビット表現の文字コードが,数値データの場合は0〜255の整数が格納される。圧縮前の配列を in,圧縮後の配列を out とする。配列 in の大きさは文字列の長さと等しく,2以上,255以下である。配列 out には圧縮後のデータを格納する十分な領域が確保されている。配列の添字は0から始まる。

〔圧縮方法その1〕
 圧縮の表現形式として,[圧縮対象文字][連続回数]を用いる方法の処理手順を次の(1)〜(5)に,そのプログラムを図1に示す。例えば,文字列"abbcccddddeeeee"を圧縮すると,a1b2c3d4e5 となる。ここで,a〜zは文字データを表し,数字は対応する数値データを表す。
  • 配列 in の初めの1文字を変数 prev に取り出す。連続回数を1にする。
  • 配列 in から次の1文字を取り出し,変数 prev と比較する。配列 in から取り出す文字がない場合,処理手順(5)へ進む。
  • 比較した二つの文字が等しい場合,連続回数に1を加える。等しくない場合,変数 prev と連続回数を配列 out に追加し,(2)で取り出した文字を変数 prev にコピーして,連続回数を1に戻す。
  • 処理手順(2)に戻る。
  • 変数 prev と連続回数を配列 out に追加する。
 図1中の関数 encode1 はプログラムのメイン処理であり,配列 out に追加されたデータの大きさを返す。
pm02_1.gif/image-size:355×420
〔圧縮方法その2〕
 圧縮の表現形式として,同じ文字が4回以上連続する場合に[圧縮対象文字][圧縮表現文字][連続回数]を用い,3回以下の場合はそのままとする方法の処理手順を次の(1)〜(5)に,そのプログラムを図2に示す。圧縮表現文字には,圧縮対象文字と区別するために,圧縮対象文字として使用されない文字を使う。ここでは"*"を圧縮表現文字とする。例えば,文字列"abbcccddddeeeee"を圧縮すると abbcccd*4e*5 となる。
  • 配列mの初めの1文字を変数prevに取り出す。連続回数を1にする。
  • 配列 in から次の1文字を取り出し,変数 prev と比較する。配列 in から取り出す文字がない場合,処理手順(5)へ進む。
  • 比較した二つの文字が等しくない場合,変数 prev の連続回数だけの繰返しを表す圧縮表現を配列 out に追加し,(2)で取り出した文字を変数 prev にコピーして,連続回数を1に戻す。等しい場合,連続回数に1を加える。
  • 処理手順(2)に戻る。
  • 変数 prev の連続回数だけの繰返しを表す圧縮表現を配列 out に追加する。
 図2中の関数 encode2 はプログラムのメイン処理であり,配列 out に追加されたデータの大きさを返す。関数 outputRun は,prev が runLength 回繰り返すことを表す圧縮表現を配列 out の添字 k の位置に追加し,次の追加位置を返す。
pm02_2.gif/image-size:355×632
〔プログラムに関する考察)
 二つの圧縮方法におけるデータ圧縮の効果について考える。
 いま,同じ文字がn個続く確率(出現率)を表1のとおり仮定する。例えば,配列 in の大きさが100の場合,1割の10文字が連続しない一つの文字として存在する。また,4割の40文字が4個連続する文字の割合である。このとき,4個連続している文字列は10組となる。
 圧縮後のデータの大きさを圧縮前のデータの大きさで割った値を圧縮比と定義する
と,この表1の場合,(圧縮方法その1〕での圧縮比は,〔圧縮方法その
2〕での圧縮比はと算出できる。
pm02_3.gif/image-size:360×68
 〔圧縮方法その1〕の場合,圧縮対象のデータによっては,圧縮後のデータが圧縮前より大きくなってしまうことがある。①最悪の場合には,圧縮比はとなってしまう。

設問1

文字列"xyyyzzzzxxyzzzzz'の圧縮について,(1),(2)に答えよ。
  • 〔圧縮方法その1〕によって圧縮した結果を答えよ。
  • 〔圧縮方法その2〕によって圧縮した結果を答えよ。

-解答入力欄-

-解答例・解答の要点-

    • x1y3z4x2y1z5
    • xyyyz*4xxyz*5

-解説-

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

設問2

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

-解答入力欄-

  • ア:
  • イ:

-解答例・解答の要点-

  • ア:in[i]とprevが等しい
  • イ:k+2

-解説-

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

設問3

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

-解答入力欄-

  • ウ:
  • エ:
  • オ:

-解答例・解答の要点-

  • ウ:in[i]とprevが等しくない
  • エ:prev←in[i]
  • オ:runLengthが3以下

-解説-

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

設問4

〔プログラムに関する考察〕について,(1),(2)に答えよ。
  • に入れる適切な数値を答えよ。
  • 本文中の下線①とは,どのような場合か,20字以内で答えよ。

-解答入力欄-

    • カ:
    • キ:
    • ク:

-解答例・解答の要点-

    • カ:0.8
    • キ:0.9
    • ク:2
    • 同じ文字が連続することが無い場合 (16文字)

-解説-

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

平成24年春期 午後問題一覧

問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 採点講評
© 2010-2021 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop