跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2022年8月実施 情報学基礎 F2-1

Author​

Isidore, 祭音Myyura

Description​

設問1​

自然数 の関数 に対するビッグオー記法 を考える。 ここで、 は自然数 の関数である。以下に示す各 について、最も簡潔な形を持つ を答えよ。

(1)

(2)

(3)

設問2​

スタックマシンを用いて計算式 の値を求めることを考える。 ここで、「+」は加算、「-」は減算、「*」は乗算、「/」は除算を表す。 このとき、以下の問いに答えよ。

(1) 上記の計算式に対応する構文木を図示せよ。

(2) 上記の計算式に対応する逆ポーランド記法を示せ。

(3) 構文木を走査することで逆ポーランド記法出力する疑似コードを示せ。但し、再起呼び出しを用いるとこ。

(4) 上記の計算式の値を得るまでのスタックの変化を図示せよ。

設問3​

互いに異なる 個の正の整数の集合 Extra close brace or missing open braceA = \{a_1, a_2, \ldots, a_n} と非負の整数 を考える。 正の整数 および非負の整数 について、 は、 の部分集合 であって、 を満たすものの数を表すものとする。

(1) とする。 と 、また、それぞれに対して等式を満たす部分集合を全て求めよ。

(2) を、 のうちのいくつかを用いて表せ。但し、便宜上 , , , , とする。

Kai​

設問1​

  • (1)
  • (2)
  • (3)

設問2​

(1)​

(2)​

(3)​

The answer is a Postorder Traversal for a binary tree:

outputRPN(node):
    if node->left_child is not Null then:
        outputRPN(node->left_child)
    if node->right_child is not Null then:
        outputRPN(node->right_child)
    output(node->value)

(4)​

5
5 3
2
2 2
4
4 7
4 7 4
4 3
4 3 2
4 3 2 1
4 3 3
4 1
5

設問3​

(1)​

By definition we need to find subsets of that satisfy . Therefore, the answer is

Similarly, we have

(2)​