中間試験 2024#

答えの表示/非表示

時間：60分，問題：33問，配分：Q1～Q33 各3点（出席点1点）

1. 序論 & 特徴と分類#

プログラミングパラダイムに関する説明のうち，適切なものを全て列挙せよ．

パラダイムとはプログラミング言語が採用する構文である
パラダイムとはプログラミング言語が採用する規範である
パラダイムの違いとはプログラミング言語が採用する計算モデルの違いである
複数のパラダイムを採用したプログラミング言語が存在する
オブジェクト指向はパラダイムの一種である
ノイマン型コンピュータはパラダイムの一種である

Exam-answer

2，3，4，5

Note

3 「計算」をどのように捉えるかによってパラダイムが変わる．

計算をRAM（機械語命令の列挙）で表現する → 命令型
計算をラムダ計算（関数の組み合わせ）で表現する → 関数型

すなわち「パラダイムの違い＝規範や哲学の違い＝計算モデルの違い」と捉えることができる．

6 ノイマン型コンピュータはコンピュータである．パラダイムではない．

ノイマン型コンピュータにおけるload→any process→storeの操作に対応するC言語の操作として，最も適切なものの番号を答えよ．

四則演算の繰り返し
ジャンプ命令による条件分岐
右辺に式を持つ代入文
ポインタによる間接アドレス指定

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 50, 'padding': 5}}}%%
graph LR
  classDef tr fill:white,stroke:black;
  CPU:::tr;
  メモリ:::tr;
  メモリ -- load --> CPU;
  CPU -- store --> メモリ;

Exam-answer

3

次のRAMプログラムを実行したときの出力を答えよ．右側の表はRAM命令の挙動である．
※cはメモリ，c(0)はレジスタ，pcはプログラムカウンタ

   load   #5
   store  1
   load   1
   sub    #3
   jgtz   L
   load   1
   add    #1
L: write  1
   halt

命令	挙動
`load a`	`c(0)` ← `c(a)`
`store a`	`c(0)` → `c(a)`
`add a`	`c(0)` ← `c(0) + c(a)`
`sub a`	`c(0)` ← `c(0) - c(a)`
`jgtz b`	`pc` ← `b`，`c(0) > 0`ならば
`write a`	`c(a)`を出力

Exam-answer

5

Note

次のソースコードと等価である．

int n = 5;
if (n <= 3) {  // if (n - 3 <= 0)
    n++;
}
printf("%d", n);

2. 構文#

プログラミング言語の構文に関する説明のうち，適切なものを全て列挙せよ．

構文規則は文脈自由文法やBNFによって定義される
プログラミング言語の一部の構文には曖昧さが含まれる
プログラミング言語の一部の構文は，演算子の優先度や結合性を鑑みて設計されている
構文の生成規則の書き換えによって，文法の曖昧性を排除できることがある
演算子の優先度とは同一の演算子が並んでいるときに，どちらの演算を優先するかを示す性質である

Exam-answer

1，2，3，4

Note

2は適切である．構文が本質的に曖昧な場合，そもそも曖昧さは除去できない．

やむを得ず曖昧な文法が採用される場合は，複数の解析木のうちどれを選択するかをあらかじめ定めておく必要がある．

3は適切．

プログラミング言語の構文は，プログラム記述時の使い勝手だけでなく，文法の曖昧さや演算子の優先度，解析コストの低さなど様々な要素を鑑みて設計されている点をよく認識せよ．

5は優先度ではなく結合性の説明である．

結合性（associativity）とは同一の演算子が並んでいるときに，どちらの演算を優先するかを示す性質である．

以下はC言語のプログラムである．

n = i * 2;
if (n > 5) i++;

このプログラムを構成する要素のうち，全ての文を列挙せよ．要素の区切りは,とせよ．

Exam-answer

n = i * 2;，if (n > 5) i++;，i++;

Note

if文は本文i++まで含めて一つの文である．

C言語においては;や}を末尾に持つ要素が文である．

if文はさらにi++;を入れ子構造として持っている．

文と式は入れ子構造を取る．
if文とif-else文のEBNF
<if文>     ::= if (<式>) <文> ;

このプログラムを構成する要素のうち，全ての式を列挙せよ．要素の区切りは,とせよ．要素名が重複していても省略せず全て列挙すること．

Exam-answer

i * 2，i，2，n > 5，n，5，i++，i

Note

式の説明は以下の通り．

式は四則演算などの評価結果となる値を持つ要素である．代入文の右辺の要素は全て式と考えてよい．

文と同じく式の中にはさらに式を取り得る．

文と式は入れ子構造を取る．

\[ E \ra num\ |\ id\ |\ E+E\quad //\ \textrm{Expression} \ \textsf{式}\\ \]

🤔代入文の左辺 n は厳密には式ではないが，そこまで厳格には採点はしない．nを含めても○としている．

次のCF文法\(G_1\)は曖昧さを含んでいる．

\[ \displaylines{ G_1=(&N &=& \{E\}, \\ &\mathit{\Sigma} &=& \{num,+,*,/,(,)\},\\ &P &=& \{E \ra E+E \ |\ E*E \ |\ num \ |\ (E)\},\\ &S &=& E\quad)\\ } \]

\(G_1\)を曖昧さのない文法\(G_1'\)に書き換えよ．演算子の優先度は* > +とし，どちらの演算子も左結合とすること．

Exam-answer

\[ \displaylines{ G_1'=(& N &=& \{E,T,F\},\\ & \mathit{\Sigma} &=& \{num,+,*,(,)\},\\ & P &=& \{\\ & & & \quad E \ra E + T \ |\ T,\\ & & & \quad T \ra T * F \ |\ F,\\ & & & \quad F \ra (E) \ |\ num\\ & & & \},\\ & E & ) } \]

Note

講義資料と同じ題材である．

問題文の終端記号 / は無視してください．タイポです．

\(G_1'\)に対するnum+num*numの解析木を記述せよ．非終端記号は□，終端記号は◯で囲うこと．

Exam-answer

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 30, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E]
  e1 --- e2[E];
  e2 --- e3[T];
  e3 --- e4[F];
  e4 --- num1(num):::tr;
  e1 --- plus(#43;):::tr;
  e1 --- e5[T];
  e5 --- e6[T];
  e6 --- e7[F];
  e7 --- num2(num):::tr;
  e5 --- times(#42;):::tr;
  e5 --- e8[F];
  e8 --- num3(num):::tr;

Note

講義資料と同じ題材である．

2種類の文字0と1のみで構成される言語Lを生成するCF文法\(G_2\)を答えよ．ただし先頭と末尾は同じ文字とする．

OK：0 1 00 11 101 01011110
NG： 01 10 11100 0001011001

Exam-answer

\[ \displaylines{ G_2=(& N &=& \{E,T\},\\ & \mathit{\Sigma} &=& \{0,1\},\\ & P &=& \{\\ & & & \quad E \ra 0\ |\ 1\ |\ 0T0\ |\ 1T1,\ \\ & & & \quad T \ra 0T\ |\ 1T\ |\ \varepsilon \\ & & & \},\\ & S &=& E\quad) } \]

Note

宿題と同じ題材である．

次のCF文法\(G_3\)は，x a bの3つの文字で構成される言語を生成する．

\[ \displaylines{ G_3=(&N &=& \{S, T\}, \\ &\mathit{\Sigma} &=& \{x,a,b\},\\ & P &=& \{\\ & & & \quad S \ra xS \ |\ xT, \\ & & & \quad T \ra aTb\ |\ \varepsilon\\ & & & \},\\ & S &=& S\quad)\\ } \]

\(G_3\) が生成する言語\(L(G_3)\)の中で，文字列の長さが5文字以下のものを全て列挙せよ．要素の区切りは,とせよ．

Exam-answer

x，xx，xxx，xxxx，xxxxx, xab，xxab，xxxab，xaabb

Note

以下のように考えると良い．

T：複数のaの後にbが同数出現する文字を生成する（ ab aabb ... ）
S：xの連続（x xx xxx ...）の連続の後にTを結合した文字を生成する

axbという文字は生成できないので注意せよ．

3. 命令型言語#

以下はC言語のプログラムである．

L1: while (i < size) {
    if (i % 2) goto L1;
    if (arr[i] == '\0') goto L2;
    ...
}
L2: ...

goto L1;の部分を構造化プログラミングに従うように書き換えよ．

Exam-answer

continue;

goto L2;の部分を構造化プログラミングに従うように書き換えよ．

Exam-answer

break;

以下はC言語のプログラムである．

int x = 5;
int *p = &x;
printf("%d\n", x);   // 1
printf("%d\n", &x);  // 2
printf("%d\n", p);   // 3
printf("%d\n", &p);  // 4
printf("%d\n", *p);  // 5

変数xの右辺値が出力されるprint文の番号を全て列挙せよ．

Exam-answer

1，5

Note

5はポインタを経由して間接的にxの右辺値を取り出している．

変数xのアドレス（左辺値）が出力されるprint文の番号を全て列挙せよ．

Exam-answer

2，（3）

Note

3はポインタ変数pの右辺値であり，この値は変数xのアドレス（左辺値）でもある．🤔問題文として曖昧さがあるので3を含めなくても○とする．

ポインタ変数pの右辺値が出力されるprint文の番号を全て列挙せよ．

Exam-answer

3，（2）

Note

2は3と全く同じ出力だがpの右辺値ではない．2はあくまで変数xのアドレスである．🤔問題文として曖昧さがあるので2を含めても○とする．

以下はC言語の構文に則った擬似言語のプログラムである．

void swap(int a, int b) {
    int tmp = a;  a = b;  b = tmp;
}
void main() {
    int x[] = {0, 1, 2};
    int a = 9;
    swap(x[0], x[1]);
    printf("%d %d %d %d", x[0], x[1], x[2], a);
}

この疑似言語において，関数呼び出しの引数結合方法が参照渡しだった場合の出力結果を答えよ．

Exam-answer

1 0 2 9

Note

参照渡し，つまりポインタで引数を渡すとどうなるかという問題である．参照を渡すのでswap()側での代入処理がmain()側にも作用する．

C言語メモリのスタック領域に関する説明として，適切なものを全て列挙せよ．

グローバル変数はスタック領域に積み上げられる
ローカル変数はスタック領域に積み上げられる
malloc等の動的メモリ確保にはスタック領域が利用される
再帰的関数の駆動レコードにはスタック領域が利用される
スタック領域の確保と解放は自動で行われる
ポインタによる参照先は常にスタック領域である

Exam-answer

2，4，5，(1)

Note

1 🤔グローバル変数は厳密にはスタックに積み上げられないが，講義資料の中ではスタックの最下部に積み上がっているような説明をしていた．よって1を含めても○とする．

実行時スタックの変化

                  [n=0 x=1] →3
       [n=1 x=?]  [n=1 x=?]  [n=1 x=3] →6
[g=2]  [g=2]      [g=2]      [g=2]      [g=2]
---------------------------------------------> t
    call       call       done       done
    f(1)       f(0)       f(0)       f(2)

3 mallocの確保先は常にヒープ領域である．

6 ポインタの参照先はヒープ・スタックの両方がありうる．

4. オブジェクト指向言語#

オブジェクト指向言語に関する説明として，適切なものを全て列挙せよ．

オブジェクト指向は命令型パラダイムの一種である
オブジェクト指向におけるオブジェクトとは複数の操作をまとめた単位である
オブジェクト指向の利点の一つは再利用性による効率的なプログラミングである
オブジェクト指向言語を用いれば自動的にデータの隠蔽化が可能である
委譲とはクラスの継承によって，ある処理を別のクラスに依頼する操作である
ポリモーフィズムとは，異なる処理を持つインスタンスを同一の操作で扱うことができる性質のことである

Exam-answer

1，3，6

Note

2 オブジェクトはデータと操作をまとめた単位である．

4 データの隠蔽化のためには適切なクラス設計が必要である

5 委譲とはある処理を別のクラスに依頼する操作であるが，継承は関係がない．

以下はJavaのプログラムである．

public class Sample {
    public int x1;
    public int[] x2;
    private ArrayList<Integer> x3;
    public Sample() { ... }
    public String x4() { ... }
    private static void x5(int z) { ... }
}

このプログラムに含まれる全てのフィールド名を列挙せよ．

Exam-answer

x1，x2，x3

各フィールドについて，プリミティブ型か参照型かをそれぞれ答えよ．

Exam-answer

x1はプリミティブ型，x2とx3は参照型

Note

配列は常に参照型である．

このプログラムに含まれる全てのメソッド名を列挙せよ．

Exam-answer

Sample()，x4()，x5()

Note

コンストラクタSample()もメソッドの一種である．

各メソッドについて，アクセス修飾子をそれぞれ答えよ．

Exam-answer

Sample()はpublic，x4()はpublic，x5()はprivate

Note

static修飾子はアクセス修飾子ではない．可視性の制御とは無関係である．

以下はJavaのプログラムである．

class A {
    public int x1;
    public int x2;
    private int x4;
}
class B extends A {
    public int x3;
}
class C extends B {
    public int x1;
}

クラスCのインスタンスから直接アクセスできるフィールド名を列挙せよ．

Exam-answer

x1，x2，x3

Note

privateなx4以外はアクセスが可能．

クラスCとBの関係，及びクラスCとAの関係を何と呼ぶか．それぞれ答えよ．

Exam-answer

CとB：継承（またはis-a関係），CとA：継承（またはis-a関係）

以下はJavaのプログラムである．

public class Stack {
    int[] elements;               // 1
    int stackpointer;             // 2
    void push(int element) {...}  // 3
    int pop() {...}               // 4
    boolean isEmpty() {...}       // 5
    int size() {...}              // 6

スタッククラスとして情報隠蔽すべき要素の番号を全て列挙せよ．

Exam-answer

1，2

Note

隠蔽化の基本は「データを隠蔽・操作を公開」である．特にスタックやリストの場合はデータの隠蔽化が適切である．データ構造を利用者に意識させない．

5と6は集合クラスに共通する基本操作である．

文字列クラスStringが持つべき公開メソッドのシグネチャを5個列挙せよ．シグネチャはJava構文に従って記述すること．コンストラクタは含めないこと．要素の区切りは,とすること．

Exam-answer

void toUpperCase()，void toLowerCase()，int length()，
boolean isEmpty()，boolean contains(String)，char charAt(int index)，
String trim()，String repeat(int count)，String substring(int start, int end)など

Note

シグネチャとは何か，文字列に対する典型処理は何かの2点を問う問題である．上記以外でも様々な回答があり得る．文字列に対して行うべき処理だと共感できれば○としている．また返り値と引数の関係も重要である．

void isEmpty() NG．必ず返り値があるべき．booleanが適切だがintもOK．
String repeat() NG．繰返し回数が必須のはず．
void toLowerCase() OK．返り値ではなく内部の文字列データを書き換えていると解釈できる．

シグネチャではなくメソッド名のみの記述にも部分点を与えている．

5. 関数型言語#

関数型言語に関する説明として，適切なものを全て列挙せよ．

関数型の計算モデルはラムダ計算である
関数型では関数の組み合わせによりプログラムを表現する
関数型では値と関数を区別せずに考える
関数型における条件分岐は関数の一種である
関数型における関数は参照透過性を満たす
関数型の優れた性質は命令型プログラミングでも適用できる

Exam-answer

1，2，3，4，5，6

式 (a * b) / (c + (d - e)) をポーランド記法（前置記法）で記述せよ．

Exam-answer

/ * a b + c - d e

Note

括弧があっても○とする．ポーランド記法は括弧不要という点が利点である．

式 (λfx. + (f 3) x) (λy. * y 4) 5 の関数適用の結果を答えよ．

Exam-answer

17

カリー化に関する説明として，適切なものを全て列挙せよ．

カリー化とは関数を第一級オブジェクトに変換する操作のことである
カリー化とは複数の引数を取る関数を，単一の引数を取る関数に変換する操作のことである
カリー化とは単一の引数を取る関数を，複数の引数を取る関数に変換する操作のことである
カリー化とは複数の引数を取る関数に，一部の引数を適用する操作のことである
カリー化の利点はプログラムの構成要素の共通化にある

Exam-answer

2，5

Note

1 カリー化は第一級オブジェクトとは全く関係がない．

3 逆である．

4 部分適用のことである．

次のラムダ式のうち，高階関数に該当する式の番号を列挙せよ．

1. λx. 3                    4. λfx. f (+ x x)
2. λx. + x x                5. λxy. * x (/ y 3)
3. λf. f 3 5                6. λx. (λy. + x y)

Exam-answer

3，4，6

Note

関数を引数に取る，または関数を返す関数を高階関数（higher-order function）と呼ぶ．

以下はラムダ式の同値関係である．

1. λx. * x x = square
2. λx. f x = f
3. λx. x = λy. y
4. (λx. x) 3 = 3
5. λfx. f x = λgx. g x
6. (λfx. f x) (λyz. * y z) = λx. (λyz. * y z) x

\(\alpha\)変換に該当する同値関係の番号を列挙せよ．

Exam-answer

3，5

Note

\(\alpha\)変換：束縛変数の名前が異なっていても2つのラムダ式が同値であることを意味している．
λx. * x x  ->a  λy. * y y

\(\beta\)変換に該当する同値係式の番号を列挙せよ．

Exam-answer

4，6

Note

\(\beta\)変換：関数適用のことであり，関数適用の前後は同値であることを意味している．
(λx. * x x) z  ->b  * z z

2は\(\eta\)変換である．