京都大学 情報学研究科 知能情報学専攻 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$ 的方案数，同种物品不区分。

考点

• BST 插入、删除与中序遍历：按比较路径建树，处理删除与重新插入，并利用左—根—右遍历升序输出。
• 树排序复杂度：结合 BST 高度分析最好 $O(n\log n)$、最坏 $O(n^2)$。
• 子集和与无界零钱 DP：分别建立 0-1 可达性、无界最少件数和无界组合计数递推。