115 年 國立成功大學人工智慧科技碩士學位學程《程式設計（含資料結構與演算法）》

A campus system stores device IDs. Each ID is a 6-bit binary string. Given the following seven 6-bit keys: 000001, 000010, 000011, 001111, 100000, 101011, 111110. Please insert the 7 keys into an empty digital search tree in the order given above. When searching for key 001111, list the keys visited on the search path, in order.

Answer format: key1->key2->...

(Continue Question 1) Build the compressed binary trie for the same seven 6-bit keys. For each branch node, define its bitNumber as the bit index used at that node to choose the left or right child. The leftmost bit is index 1 and the rightmost bit is index 6. Perform BFS starting from the root. When visiting a branch node, enqueue the left child before the right child. List the bitNumber of each visited branch node in BFS order.

Answer format: bitNum1, bitNum2, ...

A binary tree stores distinct keys. Based on the following postorder and inorder sequences, please list the keys of nodes at level 3 of the tree from left to right. Note that the root is at level 1.

• Postorder sequence: ABCKDIGJHFE
• Inorder sequence: ACBDKEIGFHJ
Answer format: key1, key2, ...

For the number of nodes n = 15, what is the maximum possible height of an AVL tree, and what is the maximum possible height of a red-black tree? Note that the root is at level 1.

Answer format: AVL max possible height=?, Red-black tree max possible height=?

Which description best matches what the program does to build the backbone?
(A) It starts from one vertex and repeatedly adds the cheapest edge that leaves the visited vertices.
(B) It sorts all edges by cost, scans them in that order, and adds an edge only if it connects two different groups.
(C) It visits vertices level by level using a queue and records a tree of visits.
(D) It repeatedly selects the closest vertex based on a distance array and updates distances.
(E) It computes shortest paths between every pair of vertices, then selects edges from those paths.

What is the program output for the following input?
Input:
6 11
0 1 4
0 2 3
0 3 6
1 2 5
1 4 2
2 3 7
2 5 8
3 5 1
4 5 9
1 3 10
0 4 11
(A) 16 5
(B) 16 4
(C) 15 5
(D) 15 4
(E) 14 4

The backbone is the graph formed by the k chosen edges. A vertex is an articulation point if removing it (and its incident backbone edges) disconnects the backbone. For the dataset in Question 6, which set of vertices are articulation points in the backbone?
(A) {0, 1, 4}
(B) {0, 2, 3}
(C) {1, 3, 5}
(D) {0, 1, 3}
(E) No articulation point

The operator wants one more feature: besides the current output, also print the number of connected components in the input graph (using all m edges). Print three integers in one line: total k c
where c is the number of connected components. Which modification is correct?
(A) Add the following code right before printf(...), and change the printf format:
int c = 0;
for(int i=0;i<n;i++) {
if(f1(i) == i) c++;
}
printf("%lld %d %d\n", total, k, c);
(B) Add the following code right before printf(...), and change the printf format:
int c = 0;
for(int i=0;i<n;i++) {
if(P[i] == -1) c++;
}
printf("%lld %d %d\n", total, k, c);
(C) Add the following code right before printf(...), and change the printf format:
int c = 0;
for(int i=0;i<n;i++){
if (S[i] == 1) c++;
}
printf("%lld %d %d\n", total, k, c);
(D) Add the following code right before printf(...), and change the printf format:
int c = 0;
for(int i=0;i<n;i++) {
c += (P[i] == 1);
}
printf("%lld %d %d\n", total, k, c);
(E) None of the above.

You need operations: insert(x), delete(x), find(x), and also "find predecessor/successor of x". Please select all that are correct for the predecessor/successor queries.
(A) A red-black tree supports the queries in O(log n) worst case when the input is a key x.
(B) A binary heap supports the queries in O(log n) worst case when the input is a key x.
(C) A B+ tree supports the queries in O(1) average time when the input is a key x.
(D) An AVL tree supports the queries in O(log n) worst case when the input is a key x.
(E) Hashing supports the queries in O(1) average time when the input is a key x.

A system needs a priority queue with: frequent meld (A, B), frequent delete-min, and occasional find-max. Please select all that are correct.
(A) A Fibonacci heap is a good match for frequent meld and delete-min.
(B) A leftist heap is a good match for frequent meld and delete-min.
(C) An SMMH directly supports find-max and find-min efficiently.
(D) A Fibonacci heap supports find-max in O(1) without any extra structure.
(E) A leftist heap supports find-max in O(1) without extra structure.

A database index is stored on disk. Minimizing disk I/O is important. Fan-out means the maximum number of children of a node. Please select all that are correct.

(A) A B-tree is suitable for disk because a node can store many keys and child pointers in one disk page/block. This gives high fan-out and small height (few page reads).

(B) A red-black tree is suitable for disk because its fan-out is 2, which reduces the number of disk page reads.

(C) A B+ tree is suitable for disk indexes for the same reason as a B-tree (high fan-out, small height).

(D) A B+ tree is often used when range queries are common, because its leaves can be linked for fast sequential scan on disk.

(E) For disk-based indexes, a red-black tree usually needs more page reads than a B-tree/B+ tree when searching for a key, because the tree is taller.

Consider an algorithm with a running time function $T(n)=50n^2+200n\log n+10^6$. Is it mathematically correct to claim that $T(n)=O(n^2)$?

(A) True

(B) False

Consider the famous "Halting Problem", which has been mathematically proven to be undecidable. Because the Halting Problem is strictly harder than any problem in NP, it satisfies the definition of being NP-Hard. Since the Halting Problem satisfies the NP-Hard property, it is therefore correctly classified as an NP-Complete (NPC) problem.

(A) True

(B) False

If a decision problem belongs to the class NP, it implies that given a specific candidate solution, there exists a deterministic algorithm that can verify whether this solution is correct in polynomial time.

(A) True

(B) False

The 0/1 Knapsack Problem can be solved optimally by using a Greedy strategy that always selects the item with the highest value-to-weight ratio first.

(A) True

(B) False

Suppose a problem called "Robot-Path-Planning" is a known NP-Complete problem. To prove that a related new problem "3-SAT" is also NP-Complete, we must demonstrate that "3-SAT" is in NP, and we must construct a polynomial-time reduction from "3-SAT" to "Robot-Path-Planning".

(A) True

(B) False

Assuming that you are a medical information analyst, currently analyzing an algorithm designed to process a 3D MRI volume. The input is a cubic volume of data with side length $n$ (total voxels $=n\times n\times n$). Assume $n$ is a power of 2.

Pseudo-code:

Surface_Scan($n$)

• total_intensity = 0
• For $i=1$ to $n$:
  • For $j=1$ to $100$:
    • total_intensity = total_intensity + Read_Pixel(i, j)
• Return total_intensity

MRI_Voxel_Process($n$)

• If $n\leq 1$, return.
• For $k=1$ to $n$:
  • Surface_Scan(n)
• For $x=0$ to $1$:
  • For $y=0$ to $1$:
    • For $z=0$ to $1$:
      • MRI_Voxel_Process(n/2)

Assume that the function Read_Pixel(i, j) takes constant time.

Questions:

(1) [3%] Analyze the Surface_Scan(n) function and determine its time complexity using $\Theta$-notation.

• Time complexity: ____

(2) [3%] Write down the recurrence relation for the running time $T(n)$ of MRI_Voxel_Process(n).

• $T(n)=$ ____

(3) [4%] Analyze the asymptotic growth rate of the algorithm, and determine the overall asymptotic tight bound ($\Theta$) for the running time of MRI_Voxel_Process(n). Please write down your calculation process.

• Calculation process: ____
• Overall asymptotic tight bound: ____

You are a process engineer managing a critical Lithography Machine. The machine has a strict thermal constraint: You cannot schedule production for two consecutive shifts. If Shift $i$ is active, Shifts $i-1$ and $i+1$ must be idle (cooling).

The estimated Production Yield Value for the upcoming 13 shifts is listed below.

Questions:

(1) [4%] Identify the set of shifts that results in the maximum possible total value while satisfying the thermal constraint.

• Selected Shifts: ____ (e.g., S1, S2, …)
• Total Value: ____

(2) [4%] A very important client demands that Shift 7 (Value: 40) MUST be included in the schedule. Under this mandatory condition, what is the maximum total value you can achieve for the 13 shifts?

• Selected Shifts with S7: ____
• Total Value with S7: ____

(3) [2%] Process Upgrade: The High-Temperature Machine Imagine the factory installs a new, high-performance machine. This machine generates significantly more heat, so the safety constraint is updated: After any active shift, the machine must cool down for TWO consecutive shifts.

Let $f[i]$ be the maximum value achievable considering shifts up to $i$, and let $v_i$ be the value of Shift $i$. Please write down the complete Recurrence Relation (Mathematical Equation) for:

• $f[i]$: ____

You are analyzing the routing latencies for a constellation of 4 satellites (Nodes A, B, C, D). Below is the adjacency list with the latency between specific nodes:

• A $\to$ B: 10
• A $\to$ C: -5
• C $\to$ B: 4
• B $\to$ D: 5
• D $\to$ C: 2
• D $\to$ A: 3

Requirement: You need to analyze the latency characteristics of the network so that shortest communication paths can be efficiently determined when needed.

Questions:

(1) [4%] Based on the specific properties of the edges in this graph and the problem requirement, identify the single most appropriate standard algorithm to use. Explain your choice by pointing out the specific graph feature that disqualifies other algorithms, and explicitly state why at least one other commonly used shortest-path algorithm would fail or be inappropriate in this case.

• Algorithm: ____
• Why choosing this algorithm? ____

(2) [2%] Let $M$ be the initial $4\times 4$ distance matrix used at the start of your chosen algorithm. Please construct and write down $M$ clearly.

(Note: Use $\infty$ for non-existing edges and $0$ for self-loops. Order: A, B, C, D.)

• $M=$ ____

(3) [4%] After the algorithm completes execution:

(a) [2%] What is the final shortest path cost from Node D to Node B? Please trace the path logic (e.g., $D\to\cdots\to B$).

• Final shortest path cost: ____
• Final path logic: ____

(b) [2%] State the asymptotic Time Complexity $\Theta$ of this algorithm.

• Time Complexity: ____

You are optimizing the core engine of an image editing tool called "Smart Lasso". The tool helps users extract objects by automatically finding the best boundary between a Start Pixel ($S$) and a Target Pixel ($T$). The image is represented as a grid of pixels. Each pixel has an associated "Energy Cost" (representing high-frequency noise or weak edges). Here are some rules:

• Movement Rule: From any pixel, you can move to adjacent pixels (Up, Down, Left, Right). Diagonal movement is not allowed.
• Path Cost: The sum of the Energy Costs of all pixels visited on the path (excluding $S$, but including $T$).

The energy cost matrix is shown below (assume the cost of entering $T$ is 0):

In the following, we will use (row, col) as coordinate representation. Top-left is $(0,0)$.

If two neighbors have the same cost, prioritize the direction in this order:

Right $\to$ Down $\to$ Up $\to$ Left

Questions:

(1) [4%] A junior developer implemented a "High-Speed Mode" for the lasso. The logic is simple:

"At every step, the cursor simply snaps to the immediate neighbor with the lowest energy cost to get closer to the target. It does not plan ahead."

Please trace the path generated by this method from $S$ to $T$ and calculate the total cost.

• Path Sequence: ____ (e.g., $(0,0)\to(0,1)\to\cdots$)
• Total Path Cost: ____

(2) [4%] Users have complained that the "High-Speed Mode" (from Q. 4.1) often gets "trapped" in noisy areas or takes expensive detours, failing to find the true object boundary. Your manager asks you to rewrite the core engine. The new requirement is:

"The tool must guarantee finding the mathematically optimal boundary—the path with the absolute minimum Total Cumulative Cost from Start to Target—even if it takes a bit more computation time."

Please trace the path generated by this method from $S$ to $T$ and calculate the total cost.

• Path Sequence: ____ (e.g., $(0,0)\to(0,1)\to\cdots$)
• Total Path Cost: ____

(3) [2%] The solution in Q. 4.2 works great on small grids. However, when applied to a 4K Image (with $N$ pixels), the tool becomes laggy. Profiling reveals the bottleneck is in the Open Set (Priority Queue)—specifically, the operation of repeatedly finding and removing the pixel with the minimum cumulative cost. You are comparing two underlying data structures for this Priority Queue: a simple Unsorted Array vs. a Binary Min-Heap. Please analyze the Time Complexity (Big-O) for the "Extract-Min" operation in both cases:

• Case 1: You use a simple Unsorted Array to store the candidate pixels; the time complexity for Extract-Min is: ____
• Case 2: You switch to a Binary Min-Heap to store the candidate pixels; the time complexity for Extract-Min is: ____