115 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《資料結構》

1. Given a two-dimensional array A[5][4] (5 rows and 4 columns), assuming it is stored in a "row-major" manner and each element occupies 2 bytes, if the address of A[0][0] is 1000, what is the address of A[2][3]?
   (A) 1018
   (B) 1022
   (C) 1024
   (D) 1011

2. What are the main disadvantages of storing a sparse matrix using a general two-dimensional array?
   (A) Access speed is too slow
   (B) The code is too complex
   (C) Wasting a lot of memory space
   (D) Matrix multiplication cannot be performed

3. The time complexity of multiplying two $n \times n$ matrices using the standard three-loop algorithm is:
   (A) $O(n)$
   (B) $O(n^2)$
   (C) $O(n^3)$
   (D) $O(2^n)$

4. If we use an array A[0...N-1] to implement a circular queue, and use the variables front and rear, If the condition for a queue to be "empty" is $front == rear$, what is the condition for a queue to be "full"? (To distinguish between empty and full, one space is usually sacrificed.)
   (A) $(rear + 1) \mod (N+1) == front$
   (B) $(front + 1) \mod (N-1) == rear$
   (C) $(rear + 1) \mod N == front$
   (D) $(front + 1) \mod N == rear$

5. Which of the following situations would lead to Stack Overflow?
   (A) Try popping data from an empty stack.
   (B) The recursion is too deep and there is no convergence condition.
   (C) The front of the circular queue caught up with the rear
   (D) The number of nodes in the implementation of linked sequences is too small.

6. Given an input sequence of 1, 2, 3 (pushed into the stack in that order), which of the following is "not possible" the order in which the elements are popped out?
   (A) 3, 2, 1
   (B) 1, 2, 3
   (C) 2, 3, 1
   (D) 3, 1, 2

How do we use a stack structure when evaluating postfix expressions (e.g., $3\ 4 + 5 * 7 / 2-$)?

(A) When encountering an operand, push; when encountering an operator, pop two numbers. Perform the operation on the two numbers and then push the result.
(B) When encountering an operator, use Push; when encountering an operand, use Pop.
(C) Push all operands and operators encountered, and then calculate again at the end.
(D) This requires using columns, not stacks.

If a series of distinct numbers of length $n$ are pushed onto a stack in sequence, and can be popped at any time during the process (as long as the stack is not empty), how many different valid permutations can be generated?

(A) $\frac{1}{n}\binom{2n}{n+1}$
(B) $2^n$
(C) $\frac{1}{n+1}\binom{2n}{n}$
(D) $(n+1)!$

Given a "Perfect Binary Tree" (i.e., every level is full), with a height of $h$ (total number of nodes $n \approx 2^{h+1}$), compare the worst-case space complexity of using a stack for depth-first search (DFS) versus using a queue for breadth-first search (BFS).

(A) Depth-first search (DFS) is relatively memory-intensive because of its deep recursion depth.
(B) BFS is relatively memory-intensive because a queue needs to store all the leaf nodes at the lowest level.
(C) Both consume roughly the same amount of memory $O(n)$.
(D) Both consume roughly the same amount of memory $O(\log n)$

Inserting a node named "new" after a node named "p" in a doubly linked list (assuming $p$ is not the last node), which of the following four lines of code is in the correct order?

1. new->next = p->next;
2. p->next->prev = new;
3. p->next = new;
4. new->prev = p;

(A) $1 \rightarrow 3 \rightarrow 2 \rightarrow 4$
(B) $3 \rightarrow 4 \rightarrow 1 \rightarrow 2$
(C) $1 \rightarrow 2 \rightarrow 4 \rightarrow 3$
(D) $3 \rightarrow 1 \rightarrow 4 \rightarrow 2$

To detect whether a cycle exists in a singly linked list, the most famous Floyd's Cycle Detection Algorithm (the tortoise and the rabbit algorithm) uses two metrics. Assume the distance from the beginning of the linked list to the start of the cycle is $A$, and the length of the cycle is $L$. Assume the rabbit's speed is twice that of the tortoise. When the tortoise and rabbit meet, assume the tortoise has traveled a distance $B$ within the cycle. What is the total distance the rabbit has traveled at this point?

(A) $A + B$
(B) $2(A + B)$
(C) $A + B + L$
(D) $2A + B$

If we change the rabbit's speed to "3 steps each time" and the tortoise's speed to "1 step each time", can this algorithm still detect the cycle?

(A) No, the rabbit might jump over the tortoise to reach NULL.
(B) Maybe, check if $L$ is a multiple of $B$.
(C) Maybe, check if $L$ is a multiple of 2.
(D) Perhaps, we can check if $L+A-B$ and 2 are coprime.

Skip List is a probabilistic data structure based on linked lists. What is its main purpose in addressing the shortcomings of standard linked lists?

(A) Solving the problem of slow insertion
(B) Solving the problem of not being able to perform fast searches
(C) Solving the problem of excessive memory usage
(D) Solving the problem of being unable to traverse in reverse

What would be the effect of using the standard "3-Way Partitioning Quick Sort (Dutch National Flag problem)" on an array containing a large number of duplicate keys?

(A) Efficiency became very poor, close to $O(n^2)$
(B) Extremely efficient, close to $O(n)$
(C) lead to Stack Overflow
(D) No significant difference

If writing to memory (Write/Swap) is very expensive (e.g., Flash Memory), we want to minimize the number of writes. Which of the following algorithms guarantees the fewest number of writes?

(A) Selection Sort
(B) Cycle Sort
(C) Heap Sort
(D) Quick Sort

What problems can arise from linear probing?

(A) Primary Clustering
(B) Memory leak
(C) Unable to delete data
(D) Need to perform recursive function call

If the pre-order of a binary tree is AB D E C F and the in-order is D B E A F C, what is its post-order?

(A) D E B F C A
(B) D E B C F A
(C) E D B F C A
(D) Not Unique

Regarding the comparison between Red-Black Trees and AVL Trees, which of the following statements is correct?

(A) AVL trees have more lenient balance conditions than red-black trees, so they can be taller.
(B) Red-black trees guarantee that the longest path from the root to a leaf is no more than twice the length of the shortest path.
(C) In scenarios with a large number of lookups, red-black trees are faster than AVL trees.
(D) In scenarios involving numerous insertions and deletions, AVL trees outperform red-black trees.

2-3 Tree is a special type of B-Tree. What conditions must all its leaf nodes satisfy?

(A) In the Same level
(B) It must contain 3 key-value pairs.
(C) In different level only $l$ and $l+1$.
(D) Must be filled from left to right

Which of the following comparisons between BST and Heap is incorrect?

(A) In-order traversal of a BST is ordered, while that of a Heap is not.
(B) The time complexity of searching for any value in the Heap is $O(\log n)$.
(C) A heap is a complete binary tree, while a BST is not.
(D) Heaps are typically implemented using arrays, while BSTs are typically implemented using pointers.

Suppose that we have a Binary Search Tree (BST) consisting of nodes, where each node stores a unique integer between 1 and 1000. Which of the following sequences could be a VALID sequence of nodes examined when searching for the number 101?

(A) 80, 252, 90, 130, 110, 100, 120, 101
(B) 252, 130, 120, 110, 100, 90, 80, 101
(C) 80, 90, 252, 110, 130, 120, 100, 101
(D) 80, 252, 90, 100, 130, 120, 110, 101
(E) 252, 130, 110, 80, 90, 100, 120, 101

Height: Assume that the height of a tree node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.

Balance: The balance of a binary tree node is defined as the left child node's height minus the right child node's height. The balance of a leaf node is 0 (since the height of a NULL child node is defined as -1).

What is the height of the root of a Binary Search Tree (BST) after inserting 5, 3, 9, 2, 4, 7, 1, 6, 10, 8? The tree is empty initially.

(A) 3
(B) 4
(C) 5
(D) 6
(E) 7

What is the balance of the root of a Binary Search Tree (BST) after inserting 5, 3, 9, 2, 4, 7, 1, 6, 10, 8? The tree is empty initially.

(A) -2
(B) -1
(C) 0
(D) 1
(E) 2

If you want to find the top 100 students by scanning a list of scores, which of the following data structures will offer the best computational time?

(A) min-heap sized 100
(B) max-heap sized 100
(C) balanced binary search tree such as AVL-tree with 100 nodes
(D) sorted linked list sized 100
(E) sorted array sized 100

To find the top 100 words by appearance frequency in a book, which of the following data structures will offer the best computational time for counting the word frequency?

(A) list of linked lists
(B) queue
(C) tree
(D) array
(E) hash table

Which of the following traversal methods takes a Breadth-First search (BFS) approach?

(A) pre-order traversal
(B) in-order traversal
(C) post-order traversal
(D) level-order traversal
(E) None of the above

Which of the following arrays is NOT a valid Max-Heap or Min-Heap?

(A) int A[]={10,7,9,4,1};
(B) int A[]={16,14,9,2,4,1,8,3};
(C) int A[]={25,20,24,10,15,20,8,5};
(D) int A[]={50,45,30,15,20,10};
(E) int A[]={3,6,4,10,7,9};

What does the for-loop between Lines 28 and 29 print?

(A) 4,1,3,2,16,9,10,14,8,7,
(B) 16,14,10,8,7,9,3,2,4,1,
(C) 1,2,3,4,7,8,9,10,14,16,
(D) 16,14,10,8,7,3,9,1,4,2,
(E) 16,14,10,9,8,7,4,3,2,1,

What does the code at Line 31 print? Counter : ____

(A) 6
(B) 10
(C) 12
(D) 14
(E) 16

What is the computational complexity of build_heap()?

(A) $O(n)$
(B) $O(\log n)$
(C) $O(n^2)$
(D) $O(n^3)$
(E) $O(n^{1/2})$

Given a graph $G(V, E)$ where vertices $V=\{A, B, C, D, E, F\}$ and Edges $E=\{(\_, \_), (\_, \_), \dots\}$. $(X, Y)$ represents a directed edge from vertex $X$ to vertex $Y$. Which of the following $E$ does NOT form a Directed Acyclic Graph (DAG)?

(A) $E=\{(D, E), (B, D), (C, E), (A, B), (B, C), (E, A)\}$
(B) $E=\{(A, B), (B, C), (C, D), (D, E), (B, D), (C, E)\}$
(C) $E=\{(B, A), (A, C), (B, D), (C, E), (D, F), (E, F)\}$
(D) $E=\{(E, C), (C, D), (B, F), (E, B), (D, B), (A, E)\}$
(E) $E=\{(A, B), (B, C), (C, E), (E, F), (B, D), (D, E)\}$

The adjacency-matrix representation of a graph $G=(V, E)$ assumes that the vertices are numbered $1, 2, \dots, |V|$. Then the adjacency-matrix representation of a graph $G$ consists of a $|V| \times |V|$ matrix $A = (a_{ij})$ such that

$a_{ij} = \begin{cases} 1 & \text{if } (i, j) \in E \\ 0 & \text{otherwise.} \end{cases}$

Let $V = \{1, 2, 3, 4, 5\}$ and its adjacency matrix be

Which of the following descriptions is WRONG or the least accurate?

(A) $E=\{(1,2), (1,4), (2,5), (3,5), (4,2), (5,4)\}$
(B) The graph is a directed acyclic graph
(C) The graph has 5 vertices
(D) The graph has 6 edges
(E) There is no path that can go from vertex 1 to vertex 3

In graph theory an undirected graph has two kinds of incidence matrices: unoriented and oriented. The unoriented incidence matrix of an undirected graph is an $n \times m$ matrix $B$, where $n$ and $m$ are the number of vertices and edges respectively, such that

$B_{ij} = \begin{cases} 1 & \text{if vertex } v_i \text{ is incident with edge } e_j \\ 0 & \text{otherwise} \end{cases}$

An undirected graph (with no self-loops) consisting of 4 nodes and 4 edges is given as followed:

🖼️【此處有附圖，請對照原卷】

The incidence matrix of the undirected graph above is ($e_1$: $(1,2)$, $e_2$: $(1,3)$, etc.):

The incidence matrix of a directed graph is an $n \times m$ matrix $B = (b_{ij})$ such that

$b_{ij} = \begin{cases} -1 & \text{if edge } e_j \text{ leaves vertex } v_i \\ 1 & \text{if edge } e_j \text{ enters vertex } v_i \\ 0 & \text{otherwise} \end{cases}$

The oriented incidence matrix of an undirected graph is the incidence matrix of ANY orientation of the graph. Check the following oriented incidence matrices of the given graph with ANY chosen edge direction. Which of the following matrix $B$ with the multiplication: $BB^T$ (T: transpose) will generate a result that is different from the others?

(A) $\begin{bmatrix} 1 & 1 & 1 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & -1 \end{bmatrix}$
(B) $\begin{bmatrix} -1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & -1 \end{bmatrix}$
(C) $\begin{bmatrix} 1 & -1 & 1 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix}$
(D) $\begin{bmatrix} -1 & -1 & -1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 1 \end{bmatrix}$
(E) All of the above generate the same results

The following is an oriented incidence matrix with another orientation setting. What is the result of the multiplication: $BB^T$ (T: transpose)

$B = \begin{bmatrix} 1 & -1 & -1 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 1 \end{bmatrix}$

(A) $\begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 \\ -1 & 0 & 2 & 1 \\ -1 & 0 & 1 & 2 \end{bmatrix}$
(B) $\begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 \\ -1 & 0 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}$
(C) $\begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 2 & 0 & 0 \\ -1 & 1 & 1 & 1 \\ -1 & 0 & 1 & 2 \end{bmatrix}$
(D) $\begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 2 & 0 & 0 \\ -1 & 0 & 1 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}$
(E) $\begin{bmatrix} 3 & 1 & 1 & 0 \\ 1 & 1 & -1 & 0 \\ 1 & -1 & 2 & -1 \\ 0 & 0 & -1 & 2 \end{bmatrix}$