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

标签：

• Kyoto-University
• Binary-Search-Tree-Insertion-and-Deletion
• Inorder-Tree-Traversal
• Tree-Sort-Complexity
• Subset-Sum-Problem
• Unbounded-Minimum-Coin-Change
• Unbounded-Coin-Change-Counting

Author

itsuitsuki

Description

大学公表の原題

Q.1

Answer the following questions. (1) Depict the binary search tree, in the same way as that shown in Fig. 1, constructed by inserting the keys prepared in a number list $(8, 3, 4, 12, 10, 6, 9, 14, 1)$ one by one from the first element. Note that once a key is inserted, it is not moved.

(2) Depict the binary search tree after deleting key 6 from the binary search tree shown in Fig. 1.

(3) Depict the binary search tree after re-inserting key 6 to the binary search tree made in (2).

(4) Given a list of $n$ different numbers, consider sorting the numbers in ascending order by first constructing a binary search tree from the list and then using a recursive function that traverses the nodes of it. Let us refer to this recursive function as traverse_tree(x) and a node of the tree as x. Answer the correct order of the calls to the following three functions inside traverse_tree(x) when x is not NIL. Note that x.left is the left child node and x.right is the right child node of x, and each of them becomes NIL when it does not exist.

1. traverse_tree(x.right)
2. traverse_tree(x.left)
3. print(x)

(5) Answer the best-case time complexity order and worst-case time complexity order of the sorting algorithm in (4) for a list of $n$ different numbers.

Q.2

Assume that there are $N$ types of items, $1, 2, \dots, N$, and that the weight of each item is $c_i$ ($i = 1, 2, \dots, N$). Note that $c_i$ is a positive integer and $c_1 = 1$. Also assume that there are a sufficient number of items of each type. Answer the following questions. Note that the solutions must be given as equations that can be evaluated in constant time.

(1) $I[i, j]$ denotes whether it is possible to make the total weight equal to a given non-negative integer $j$, using at most one item of each type from $1$ to $i$. If possible, $I[i, j] = 1$, otherwise, $I[i, j] = 0$. Express $I[i, j]$ using some $I[i', j']$ (for $i' \leq i, j' \leq j$) other than $I[i, j]$. You do not need to care about boundary conditions (i.e., you only need to consider the cases where $i \geq 2, j \geq \max\{c_1, c_2, \dots, c_N\}$).

(2) $S[i, j]$ denotes the minimum number of items required to make the total weight equal to a given non-negative integer $j$, using as many items of each type from $1$ to $i$ as needed. Express $S[i, j]$ using some $S[i', j']$ (for $i' \leq i, j' \leq j$) other than $S[i, j]$. As in (1), you do not need to care about boundary conditions.

(3) $P[i, j]$ denotes the number of ways to make the total weight equal to a given nonnegative integer $j$, using as many items of each type from $1$ to $i$ as needed. Express $P[i, j]$ using some $P[i', j']$ (for $i' \leq i, j' \leq j$) other than $P[i, j]$. Note that there is no distinction between items of the same type. As in (1), you do not need to care about boundary conditions.

题目描述

1. 回答二叉搜索树问题：

   1. 按顺序插入键 $(8,3,4,12,10,6,9,14,1)$，插入后不移动已有键，按题图样式画 BST。
   2. 从题图 BST 删除键 6 后画树；再向该树重新插入 6 后画树。

   

   3. 用递归遍历 BST 输出不同数的升序，确定 traverse_tree(x.right)、traverse_tree(x.left)、print(x) 的正确先后。
   4. 求该树排序算法最好、最坏时间复杂度阶。

2. 有 $N$ 种物品，重量 $c_i$ 为正整数且 $c_1=1$，每种数量充足。写可在常数时间求值的递推式，边界可忽略：

   1. $I[i,j]$：前 $i$ 种每种至多一个时能否凑出 $j$；
   2. $S[i,j]$：前 $i$ 种每种可任取时凑出 $j$ 的最少件数；
   3. $P[i,j]$：前 $i$ 种每种可任取时凑出 $j$ 的方案数，同种物品不区分。

Kai

Q.1

(1)

The successive comparisons give the following tree.

(2)

Use the inorder successor $7$ to replace the root $6$. The successor's right child $8$ becomes the left child of $9$.

Using the inorder predecessor $5$ is another valid deletion convention.

(3)

With the successor convention used in (2), the comparisons are $6<7$, $6>4$, and $6>5$. Thus $6$ becomes the right child of $5$.

(4)

The call order is $2\to3\to1$: visit the left subtree, print the current key, then visit the right subtree. Induction on subtree size proves that this inorder traversal prints all keys in increasing order.

(5)

Traversal takes $\Theta(n)$ in every case. Constructing a balanced tree by insertion takes $\Theta(n\log n)$, which is also the best possible order for this procedure: even the shallowest binary tree has total node depth $\Theta(n\log n)$. In the worst case, sorted input makes a chain and costs $1+2+\cdots+(n-1)=\Theta(n^2)$ comparisons. Therefore the total best and worst orders are $\Theta(n\log n)$ and $\Theta(n^2)$.

Q.2

Split each case according to whether an item of type $i$ is used.

(1) With at most one item per type,

$$I[i,j]=\max\{I[i-1,j],I[i-1,j-c_i]\}.$$

(2) For an unlimited supply, removing one item of type $i$ leaves a problem in which type $i$ is still available. Thus

$$S[i,j]=\min\{S[i-1,j],1+S[i,j-c_i]\}.$$

(3) The cases using zero items of type $i$ and at least one such item are disjoint. Removing one item is a bijection from the latter set to combinations of total weight $j-c_i$ using the first $i$ types. Therefore

$$P[i,j]=P[i-1,j]+P[i,j-c_i].$$

Each recurrence uses a constant number of previously computed entries. Addition and comparison are counted as unit-cost operations; the bit complexity of large counts can grow with their size.