プログラミングの基礎」の授業用の予習問題と教科書問題

浅井 健一

1  基本データ型、変数、関数

  1. OCaml では、実数をそのまま整数として扱うことはできないが、 整数をそのまま実数として扱うことはできる。 [Yes/No]
  2. OCaml では、変数の値を変更することは基本的にはできない。 [Yes/No]
  3. OCaml では、型チェックに通ったプログラムを実行すると、 実行時に型エラーは絶対に起こらない。 [Yes/No]
(教科書問題)
ある関数 g の型が int -> int -> int であったとする。 g の型は、 括弧をつけて正確に書くと int -> (int -> int)(int -> int) -> int のいずれが正しいか。

2  条件文、デザインレシピ

  1. OCaml の if 文について、間違っている記述はどれか。
  2. 作った例をテストプログラムにしておけば、毎回、テストを手で入力しなくても、単にプログラムを OCaml に読み込むだけでテストができるようになる。 [Yes/No]
(教科書問題)
関数の argument とは日本語では ____ のことで、 sin 3.14 の場合、具体的には ____ のことである。

3  構造データとテンプレート

  1. OCaml で構造データの中身にアクセスする際に使う命令はどれか。
  2. 入力データの型から必然的に決まるプログラムの形 のことを ____ と呼ぶ。
(教科書問題)
レコードを作る際には、フィールドを省略することはできないが、 レコードのパターンを書く際には、フィールドを省略できる。 [Yes/No]

4  リストと再帰

  1. 以下で、間違っているものはどれか。
  2. sum [1; 2; 3] を実行したときに、 最初に行われる加算は次のうちのどれか。
(教科書問題)
int 型で表せる最大の整数のことを OCaml では ____ という。

5  いろいろな再帰関数

  1. 関数を作っている際に、 一部の仕事を行うために別の補助関数を作ることにした。 この補助関数は、ここでしか使わないので、 デザインレシピに従って書かなくても構わない。 [Yes/No]
  2. 以下のようなプログラムがある。
    let hanbetsushiki a b c = b * b - 4 * a * c
    let kai_no_kosuu a b c =
      if hanbetsushiki a b c > 0 then 2
      else if hanbetsushiki a b c = 0 then 1
      else 0
    
    このプログラムを kai_no_kosuu 1 2 3 と呼び出したとする。 このとき、関数 hanbetsushiki は何回、実行されるか。
(教科書問題)
局所定義された変数の有効範囲のことを ____ と呼ぶ。

6  ダイクストラ法

  1. 集合 U に入っている点は、最短距離が確定した点なので、 その後のアルゴリズムでその最短距離が変わることはない。 [Yes/No]
  2. 「直前に確定した点に接続している点」の最短距離は、 常に「直前に確定した点」が持っている最短距離に 2点間の距離を加えた値に更新される。 [Yes/No]
(教科書問題)
ダイクストラのスペルは ____ である。

7  関数の一般化と map

  1. 受け取った整数が 偶数かどうかを調べる int -> bool 型の関数 is_even がある。
    let is_even n = (n mod 2 = 0)
    
    今、map is_even [1; 2; 3] を実行したとすると、 返ってくるものの型はどれか。
  2. 以下のように、関数 f を定義して、 それを ...C... の部分で使うようなプログラムを書いた。 関数 f は、中で局所的に関数 g を定義している。
    let f x =
     let g y = ...A...
     in ...B... ;;
    ...C...
    
    このとき、f, g, x, y のスコープを それぞれ以下の中から選べ。
(教科書問題)
適当な型 A, B, C に対して、 A -> B -> C という型を持つ関数 f があったとする。 この関数 fA 型の値をひとつ渡した。 このとき関数 f が返すのは以下のどれか。

8  いろいろな高階関数

  1. List.filter の第1引数には、 List.map と同じように、'a -> 'b 型の任意の関数を 渡すことができる。 [Yes/No]
  2. List.fold_right f lst init を実行すると、 内部では f が「lst の長さ」回、実行される。 [Yes/No]
(教科書問題)
次の中で、* を prefix 関数にして実行しているのはどれか。

9  一般の再帰

  1. クイックソートのプログラム中に現れる quick_sort (take_less first rest) という再帰呼び出しは、 どのような再帰か。
  2. 一般の再帰では停止性の証明が必要だが、 構造に従った再帰のみを使っている限りは、その再帰は必ず停止する。 [Yes/No]
(教科書問題)
デザインレシピに従って作ったテストプログラムを削除するのは、次のうちのいつか。

10  再帰的なデータ構造

  1. 再帰的データ構造のテンプレートを挿入する場合、 もしその再帰的データ構造が2ヶ所で自己参照を行っていたら、 再帰呼び出しも2種類書くことになる。 [Yes/No]
  2. ビデオで示した関数 search の動きとして間違っているものはどれか。
(教科書問題)
OCaml では、変数名は小文字で始まらなくてはならない。 これを間違えて、例えば let A = 3 など 大文字を使ってしまった場合に起こるエラーはどれか。

11  例外と例外処理

  1. int option 型を持つ値は、次のうちどれか。
  2. ビデオで紹介した関数 tsuuchi(例外処理を使った方)を 呼び出したところ、 get_seiseki を実行中に DataNashi の例外が発生した。 このとき、関数 tsuuchi の4行目の
    name ^ " さんは " ^ seiseki ^ " です"
    
    の部分はどうなるか。
(教科書問題)
実行すると、場合によっては例外 Not_found を起こすのは 次のうちのどれか。

12  モジュールと抽象データ型

  1. モジュールの型を表すのは、次のうちのどれか。
  2. 抽象データ型に関する記述として間違っているものはどれか。
(教科書問題)
OCaml のプログラム(モジュール)を入れるファイルの拡張子は ml だが、 シグネチャを入れるファイルの拡張子は ____ である。

13  逐次実行

  1. unit 型を持つ値はどれか。
  2. (1 + 2) * (5 - 3) を OCaml で実行すると、 最初に実行されるのはどの演算か。
(教科書問題)
OCaml でスタンドアローンのプログラムを作ると、実行結果はどのように表示されるか。

14  値の書き換えと参照透過性

  1. int ref 型の変数 counter の値を 1 増やしたい。 正しいのは次のうちのどれか。
  2. 長さ 3 の配列 a の最後の要素を取ってくるのは、次のうちのどれか。
(教科書問題)
OCaml でレコードを宣言する際、フィールドを変更可能にするには、 フィールド名の前に ____ を書く。

15  ヒープ

  1. ヒープは木構造の一種で、 自分の値は左の子供の値よりも大きく、右の子供の値よりも小さい。 [Yes/No]
  2. 要素数が n 個のヒープに、新たにひとつデータを追加した。 これにかかる計算量は最大でいくらか。
(教科書問題)
ある OCaml のプログラムが型チェックに通った。 このプログラムを実行した際、理論的に保証されているのはどれか。

This document was translated from LATEX by HEVEA.