110年 - 110 國立清華大學_碩士班招生考試_資訊工程學系:基礎計算機科學#105771

1.(10 points) Consider L= f{aⁿbⁿ } and the statement S=integer m. Write the statement of 7S (the negation of S).
Hint:

(5 points) (b) Given an undirected, weighted graph in Figure 1, what is the minimum spanning tree (MST)?

(5 points) (c) Describe the sequence of adding edges to form the MST of the graph in Figure 1 using the greedy Kruskal's algorithm.

3.(8 points) Use the Euclidcan algorithm to find the greatest common divisor of 167,076 and 1,928,737.

4.(5 points) Five people occupy five seats. If five seats are arranged in a circle, bow many different ways can the five people select their seats?

5. (4 points) Let G = (V, E) be a graph. If V has twelve members, in which four members each has a degree of three, and the degree of each remaining member is five, how many members does E have?

6. (8 points) A class at a college consists of 19 students who sit at a circular table. The instructor wants each student to sit next to two different classmates cach day. For bow many days can they do this?

(a) T(n) = T(n-1) + 2n

(b) T(n) = 2T(n-1) +n

8. (8 points) Given a sequence of n integers A = (a₁, a₂,..., a_n), the longest increasing subsequence problem is to find a longest subsequencealk For example, (1,2,5,8) is a longest increasing subsequence of (4,1,7,5,2,5,8,4). Please use the dynamic programming technique to design an O(n²) time algorithm for solving the longest increasing subsequence problem. Please also justify your algorithm and its time complexity.

9. (7 points) Given a set S of n numbers, the k-partition problem is to determine whether or not S can be partitioned into k subsets of the same sum. For example, let S ={1,2,9,12,18}. Then for the two-partition problem, we indeed can partition S into two subsets S₁ = {1,2,18} and S₂ = {9,12} such that the sum of all elements in S₁ equals to the sum of all elements in S₂. In fact, it can be proved that the two-partition problem is NP-complete. In the situation where the two-partition problem is already NP-complete, please prove that the three-partition problem is also NP-complete.

(a) Iff(n)= O(g(n)), we can say that g(n) ≥f(n) for n ＞ 1.

(b) Merge Sort has worst-case time complexity O(n log n), while the worst-case time complexity of Insertion Sort is O(n². One weakness of Merge Sort is that it requires additional space. Therefore, if space allows, we should always use Merge Sort for better efficiency.

(c) Searching a specific key in a binary search tree takes O(log n) time, where n is the number of keys in the binary search tree.

(d) Given the pre-order and level-order traversal sequences, we can construct a unique binary tree.

(a) Please sequentially insert the following keys into the given AVL tree: 17, 19, 18. Please sbow the final result of the AVL tree after all the keys are inserted. Only the final result is needed, no step-by-step illustration is required.

(b) Continue with the previous sub-problem. After the keys in sub-problem (a) are inserted, please sequentially delete keys 25 and 17 (when deleting a non-leaf node from the AVL tree, please replace it by the node with the largest key in its left subtree). Please show the final AVL tree only (no step-by-step illustration is required).

(a) (3 points) A center of a graph is a vertex that incurs the minimum eccentricity. That is, a center c is defined as:. Is it possible for a graph to have more than one center? If yes, please provide an example; If no, please provide a proof.

(b) (2 x 3 points) In contrast to the center, which must be a vertex, an absolute center is a point that can be on an edge or on a vertex, such that its maximum sbortest path distance to all vertices is minimum. Take the following graph as an example, the point x is an absolute center, because the shortest path distances from x to vertices a, b, c, d are 6.5, 2.5, 6.5, 2.5, respectively. That is, the maximum sbortest path distance from x to all the other vertices is 6.5, which is minimum among all possible cases.

Given the definition of the absolute center, we know that there may be multiple absolute centers in a graph. So, please answer the following questions. (b-i) If there are multiple absolute centers in a graph, can all of them be on vertices, i.e, no absolute center is on an edge? If yes, please provide an example; If no, please provide a proof. (b-ii) If there are multiple absolute centers in a graph, can some of them be on vertices, and some of them be on edges at the same time? If yes, please provide an example; If no, please provide a proof.

110年 - 110 國立清華大學_碩士班招生考試_資訊工程學系:基礎計算機科學#105771

試卷資訊

選擇題 (0)

申論題 (20)