第1章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下にmis2というフォルダを作って， そこで作業することを前提とする．作成していない時は，ターミナルから 
mkdir ~/mis2
を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( C++ sources(講義独自版) ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は， 
cd ~/mis2
tar zxvf ods-cpp.tgz
ods-cpp.tarというファイルができた時は， 
cd ~/mis2
tar xvf ods-cpp.tar
を実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

[投票]queueの中でスタック(stack)と呼ばれるのは?

以下の入力を与えた時の出力は?
  1. FIFO (first-in-first-out) queue
  2. Priority queue
  3. LIFO (last-in-first-out) queue

[投票]次の中でUSet でなくSSet を使う必要があるのは?

  1. 0から263-1までの数の集合について，ある数が集合の要素に含まれるかどうかを調べる．
  2. 0から263-1までの数の集合について，最小の数を求める．
  3. 0から263-1までの数の集合について，要素数を求める．

[投票]以下のうち正しいのは?

  1. O(2n2) ⊆ O(n2)
  2. O(1.01n) ⊆ O(n100)
  3. O(n2.001) ⊆ O(n2 log n)
  4. O(n2 log2 n) ⊆ O(n2 log n)

[投票]次の関数 f(n)について最も適切なO-記法で表わせ

f(n) = 2 * n3 + 3 * n2 * log n
  1. O(n2)
  2. O(n2 log n)
  3. O(n3)
  4. O(n3 + n2 log n)
  5. O(n3 log n)

[投票]次の関数 f(n, m)について最も適切なO-記法で表わせ

f(n,m) = 2 * n2 log m + 2 * m + 3 * m log n
  1. O(n2)
  2. O(n2 log m)
  3. O(n2 log m + m)
  4. O(n2 log m + m + m log n)
  5. O(n2 log m + m log n)

[投票]確率変数X, Y に対してE[X * Y] = E[X] * E[Y] は成り立つ?

  1. 成り立つ
  2. 成り立たない
  3. 一般には成り立たないが X, Y が独立なら成り立つ

[投票]次の環境のうちw-bit RAMのw=64と仮定するのが適当なものを選べ(正解複数)

  1. iMac端末のWindows環境
  2. iMac端末のMac環境
  3. iPhone SE
  4. 任天堂Wii
  5. Apple Watch