111 年 國立成功大學電機資訊學院碩士班─資訊聯招《程式設計》

1. [4%] The following C program converts a preorder expression to its postorder form. For example, "+AB++ABC" is converted to "AB+AB+C+" with the program. Please fill in the missing parts of the program in C language.

#include<stdio.h>
#include<stdlib.h>

#define MAX_INPUT 100000

typedef struct _Stack_node{
    char val;
    struct _Stack_node *prev;
} Stack_node;

typedef struct _Stack{
    Stack_node *top;
} Stack;

Stack *new_stack(){
    Stack *stk = malloc(sizeof(Stack));
    stk->top = NULL;
    return stk;
}

char Stack_pop(Stack *stk){
    char value = stk->top->val;
    Stack_node *tmp = stk->top;
    /** TODO (A) **/
    free(tmp);
    return value;
}

void Stack_push(Stack *stk, char value){
    Stack_node *new_node = malloc(sizeof(Stack_node));
    new_node->val = value;
    /** TODO (B) **/
    stk->top = new_node;
    return;
}

int Stack_is_empty(Stack *stk){
    return stk->top == NULL;
}

void pre_to_post(char *);
void post_to_pre(char *);

int main(){
    char input[MAX_INPUT];
    scanf("%s", input);
    pre_to_post(input);
    return 0;
}

void pre_to_post(char *input){
    Stack *stk = new_stack();
    for (int i = 0; input[i] != '\0'; ++i){
        switch(input[i]){
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
            case '%':
                Stack_push(stk, input[i]);
                break;
            default:
                printf("%c", input[i]);
                while (!Stack_is_empty(stk) && stk->top->val == 'A'){
                    char top = Stack_pop(stk);
                    printf("%c", Stack_pop(stk));
                }
                if (!Stack_is_empty(stk)) Stack_push(stk, 'A');
        }
    }
    printf("\n");
}

2. [2%] We rely on the tree data structure to represent a set of elements. Two elements are in the same set if they share the common root. Given two sets as follows, which is true if we union the two sets? Assume the union follows the height union rule.

🖼️【此處有附圖，請對照原卷】
The two sets (each tree written as node → its children):

• Set 1: root 1; 1 → a, 2, 3; a → 4, 5.
• Set 2: root 6; 6 → 7, b, 8; 7 → 9, 10; 9 → 12; 8 → 11.

(A) One tree with root 6; 6 → 1, 7, b, 8; 1 → a, 2, 3; a → 4, 5; 7 → 9, 10; 9 → 12; 8 → 11.
(B) Two trees: root 1 with 1 → 2, 3; and root 6 with 6 → 7, b, 8; 7 → 9, 10; 9 → 12; b → a; a → 4, 5; 8 → 11.
(C) One tree with root 1; 1 → a, 2, 3, 6; a → 4, 5; 6 → 7, b, 8; 7 → 9, 10; 9 → 12; 8 → 11.
(D) One tree with root 6; 6 → 1, a, 7, b, 8; 1 → 2, 3; a → 4, 5; 7 → 9, 10; 9 → 12; 8 → 11.
(E) None.

3. [2%, 3%] You are given the red-black tree in the following, where the dark colored nodes are red nodes. We insert the data item "62" into the tree. (i) Which of the followings is true? (ii) Please illustrate its 2-3-4 tree counterpart representation after 62 is inserted.

🖼️【此處有附圖，請對照原卷】
The given tree (R = red node, B = black node; each line lists a node's left and right children):

• 50(B): left 10(B), right 80(R)
• 80(R): left 65(B), right 90(B)
• 65(B): left 60(R), right 70(R)

Options for (i):
(A) 65(B): left 50(R), right 80(R); 50(R): left 10(B), right 60(B); 60(B): right 62(R); 80(R): left 70(B), right 90(B)
(B) 50(B): left 10(B), right 80(R); 80(R): left 65(B), right 90(B); 65(B): left 60(R), right 70(R); 60(R): right 62(B)
(C) 50(B): left 10(B), right 65(R); 65(R): left 60(B), right 80(B); 60(B): right 62(R); 80(B): left 70(R), right 90(R)
(D) 50(B): left 60(R), right 70(R); 60(R): left 10(B), right 62(B); 70(R): left 65(B), right 80(B); 80(B): right 90(R)

4. [4%] You are given a Bloom filter with the three hash functions as follows, where $modf(.)$ returns the fractional part of a floating point number.

Bloom Filter

Which of the followings is (are) true?
(A) 8 is not in
(B) 8 may be in
(C) 8 is in
(D) 9 is not in
(E) 9 may be in
(F) 9 is in

5. [2%] A B-tree is shown in the following. We remove the data items 70, 10, 60 and 95 in order over the B-tree. What is the resultant of B-tree after the deletions?

🖼️【此處有附圖，請對照原卷】
The B-tree: root [50, 80] with three children [10, 20], [60, 70] and [90, 95]; each of the three children has three empty (external) child pointers.

6. [2%, 3%] You are given a Patricia as follows. We insert 1001, 1100, 0000 and 0001 in order into the Patricia. (i) Please show the resultant Patricia after the four data items are inserted. (ii) Please also depict its compressed binary trie counterpart.

🖼️【此處有附圖，請對照原卷】
The given Patricia: the header node holds 1000 with bit number 0, and its child pointer leads to the node 0010 with bit number 1; node 0010's left pointer points to itself and its right pointer points back to the header node 1000.

7. [2%] Consider the graph as follows. The DFS traversal is performed, starting from node 1. What are the potential sequences for the traversal?

🖼️【此處有附圖，請對照原卷】
The undirected graph has nodes 1–9 and edges (1,3), (1,7), (1,8), (2,4), (2,5), (2,8), (2,9), (3,5), (3,6), (4,6), (7,9).

(A) 1 7 9 2 4 6 3 5 8
(B) 1 3 6 4 2 5 9 7 8
(C) 1 7 8 3 5 6 4 2 9
(D) 1 8 2 4 6 3 5 9 7
(E) 1 2 5 6 4 2 9 7 8

8. [4%] The following is a hash table with linear probing. Assume the hash function is $f(x) = x \bmod 17$ for indexing the hash table. Data items 23, 52, 11, 1, 50, 99, 65, 20, 35, 34 and 82 are inserted into the hash table in order. Please fill the five blanks in the table.

9. [1%, 1%, 1%, 1%] The following C program implements Quick sort. Please fill the four missing parts of the program.

int Partition(int *arr, int front, int end){
    int pivot = arr[end];
    int i = front -1;
    for (int j = front; j < end; j++) {
        if (arr[j] < pivot) {
            _(A)_;
            swap(&arr[i], &arr[j]);
        }
    }
    i++;
    swap(&arr[i], &arr[end]);
    _(B)_;
}
void QuickSort(int *arr, int front, int end){
    if (front < end) {
        int pivot = Partition(arr, front, end);
        QuickSort(___C___);
        QuickSort(___D___);
    }
}

(i) Which of the order does the function perform?
(A) preorder
(B) inorder
(C) postorder
(D) level order
(E) None of the above.

(ii) You are given the following input. Once the unknown(r) is performed, what is the value of the rightmost leaf node?
(A) 7
(B) 6
(C) 3
(D) 2
(E) None of the above

🖼️【此處有附圖，請對照原卷】
The input tree (r points to the root; each line lists a node's children):

• 20: left 18, right 15
• 18: left 13, right 12
• 13: right 3
• 12: left 6, right 7
• 15: left 10, right 11
• 10: left 2, right 4
• 11: left 5, right 9

(i) [Step 1] Next job is extracted from the job queue for execution. What is the value of $Q[4]$ in the remaining job queue?
(A) 15
(B) 18
(C) 20
(D) 26
(E) None of the above

(ii) [Step 2] After Step (1) is executed, next job is extracted from the job queue for execution. What is the value of $Q[5]$ in the remaining job queue?
(A) 13
(B) 15
(C) 18
(D) 24
(E) None of the above

(iii) [Step 3] After step (2) is executed, a new job with priority 11 is inserted in to the job queue. What is the value of $Q[9]$ in the remaining job queue?
(A) 18
(B) 20
(C) 24
(D) 26
(E) None of the above

(i) Which of the following for (1) is true?
(A) $x.key < y.key$
(B) $x.key > y.key$
(C) $x.key \ge y.key$
(D) $x.key \le y.key$

(ii) Which of the followings is true for (2)?
(A) $NIL$
(B) $y$
(C) $x$
(D) None of the above

(iii) What is the amortized time complexity of function DecreaseKey?
(A) $O(1)$
(B) $O(n)$
(C) $O(\lg n)$
(D) $O(\lg n^2)$

(iv) What is the time complexity of inserting node into F-heap?
(A) $O(1)$
(B) $O(n)$
(C) $O(\lg n)$
(D) $O(\lg n^2)$

13. (10%) Give asymptotic tight bound ($\Theta$) for $T(n)$ where $T(n) = 2T\left(\frac{n}{4}\right) + \sqrt{n}\log(n)$. (Assume that $T(n)$ is a constant for sufficiently small $n$.)

14. (10%) Given a sequence $K = \langle k_1, k_2, k_3, k_4, k_5 \rangle$ of five distinct keys in sorted order (so that $k_1 < k_2 < k_3 < k_4 < k_5$) and six dummy keys $d_0, d_1, d_2, d_3, d_4, d_5$ representing values not in $K$, we have a probability $p_i$ for $k_i$ and a probability $q_i$ for $d_i$. Determine the cost of an optimal binary search tree for $K$ with the following probabilities:

15. (10%) Given a directed and strongly connected graph $G = (V, E)$, please design an algorithm to determine whether it contains a (directed) cycle of odd length.

16. (10%) Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:

17. (10%) Given a finite set $X$ and a family $F$ of subsets of $X$ such that every element of $X$ belongs to at least one subset in $F$, the set-covering problem is to find a minimum-size subset $\zeta \subseteq F$ whose members cover all of $X$: $X = \bigcup_{S \in \zeta} S$. The following algorithm is a $\delta$-approximation algorithm to find a set cover $\zeta$ satisfying $|\zeta| \le \delta |\zeta^*|$ where $\zeta^*$ is an optimal solution. Please compute the minimum value of $\delta$.

GREEDY-SET-COVER(X, F)
1  U = X
2  ζ = ∅
3  while U ≠ ∅
4      select an S ∈ F that maximizes |S ∩ U|
5      U = U − S
6      ζ = ζ ∪ {S}
7  return ζ