基本情報技術者試験

演習問題

次のプログラムを作りなさい (言語は C, Java, COBOL, CASL II のうちのいずれか)

問1

  1. 文字列で与えられた10進数を2進数として表示するプログラムを書きなさい
  2. 文字列で与えられた2進数を10進数として表示するプログラムを書きなさい
  3. 文字列で与えられた10進数を16進数として表示するプログラムを書きなさい
  4. 文字列で与えられた16進数を10進数として表示するプログラムを書きなさい

問2

  1. 文字列として "10+43" のような足し算の式が与えられた時、計算するプログラムを書きなさい
  2. 文字列として "-10+43-25" のような足し算、引き算の式が与えられた時、計算するプログラムを書きなさい
  3. 文字列として "-10+43*25" のような足し算、引き算、かけ算の式が与えられた時、計算するプログラムを書きなさい
  4. 文字列として "(-10+43)*25" のような足し算、引き算、かけ算とカッコを含む式が与えられた時、計算するプログラムを書きなさい

問3

  1. ファイルが与えられた時、文字数を数えるプログラムを書きなさい
  2. ファイルが与えられた時、行数を数えるプログラムを書きなさい
  3. ファイルが与えられた時、単語数を数えるプログラムを書きなさい

問4

配列に数が与えられている時、それを整列させる方式(アルゴリズム)はいくつかある。 次に説明する各方式により整列させるプログラムを書きなさい。 (配列の添字は 1 から n までとする)

  1. バブルソート
    1. i=1 とする。
    2. i 番目の値と i+1 番目の値が整列すべき順番と逆なら入れ換える。
    3. i に 1 を加え、上を繰り返す。

    これを i=1 から n まで繰り返すと、少なくとも最大の値が最後尾に移動する。 したがって、さらに、次に i=1 から n-1 まで行うと二番目に大きい値が n-1 番目に移動する。 よって、「i=1 から n」,「i=1 から n-1」,...,「i=1 から 2」と n-1 回繰り返すと全ての値が整列する。

  2. クイックソート(現在最も速いと言われているソートアルゴリズム)
    1. 配列の中から適当な値を選ぶ
    2. 選んだ値より大きいもののグループ、小さいもののグループに分ける。
    3. それぞれ分けたグループ内でさらに同様の操作を行う。
    4. これを全てのグループの要素が 1 つになるまで行う。

    これを実現するには以下のような「再帰処理」という方式が便利である。 今、分割を行うサブルーチンを partition(s,t) とする。これは、配列の s 番目から t 番目までに対して上記の処理を行うサブルーチンである。 このサブルーチンでグループ分けをした結果、 s 番めから u 番目が小さいもののグループ、u+1 番目から t 番目が大きいもののグループと分かれたとする。 この時、このサブルーチンの中で partition(s,u) と partition(u+1,t) が呼べると便利である。
    partition の説明
    但し、このようなサブルーチンの定義の中で自分自身を呼ぶようなことは C と Java しか利用できない。 他のプログラミング言語では、大量に発生する分割の位置をどのように覚えるかがプログラミングの重要な点である。

  3. ヒープソート

    ヒープとは根付二分木で常に自分より上の(根に向かう)頂点に入っている数が大きい木である。
    ヒープの例
    ヒープは通常配列上でa[i]の子がa[2i]とa[2i+1]であるように実現される。 (a[1]が根である)。

    今、与えられた配列からヒープを a[1] から a[n] まで作成したとする。 与えられた配列によりヒープを作成すると、最大値が根より得られる。 つまりa[1]が最大である。 この時、a[1] と a[n] を交換し、a[1] から a[n-1] までがヒープになるように再構築する。さらに a[1] と a[n-1] を交換して再構築、と繰り返していくと整列できる。

    再構築は次のように行う。 関係の壊れている a[i],a[2i],a[2i+1]のうち、最大値とa[i]を交換する。 交換された側だけ関係が壊れている可能性があるのでこれを繰り返す。
    再構築の図1
    再構築の図2
    再構築の図3

問5

配列 a[1] から a[n] には数値が与えられているとする。

  1. 合計を求めるプログラムを書きなさい
  2. 平均値を求めるプログラムを書きなさい
  3. 分散Vを求めるプログラムを書きなさい。但し、分散は次の公式で与えられる。 平均値を mとすると 
    V = (Σ(a[i]-m)2)/n
  = (Σ(a[i]2)/n -m2
  4. 配列 b[i] に配列 a[i] の偏差値を求めるプログラムを書きなさい。但し、偏差値は次の式で与えられる。 
    b[i] = 10 * (a[i] - m)/√V + 50

問6

関係データベースに、次の表が定義されているとする。

受験生
一次試験
二次試験

次の操作を行う SQL 文を作りなさい。

  1. 受験番号順に、受験番号と氏名を出力
  2. 一次試験の成績順に受験番号と氏名と点数を出力
  3. 一次試験が 300 点以上の受験生を、受験番号順に受験番号と氏名を出力
  4. 一次試験が 300 点以上の受験生を、二次試験の成績順に、受験番号、氏名、二次試験の点数を出力
  5. 一次試験が 300 点以上で、二次試験が 200 点以上の受験生を、受験番号順に、受験番号と氏名を出力
  6. 一次試験が 300 点以上の受験生を、一次試験と二次試験の点数の合計順で、受験番号、氏名、一次と二次の点数の合計を出力
  7. 一次試験が 300 点以上で、一次と二次の合計点が 500 点以上の受験生を、受験番号順に、受験番号と氏名を出力