115 年 國立中正大學資訊工程學系碩士班《軟體設計》

If you want to store the string literal "123456", which string variable can be used to store this string successfully?

(A) char str1[5];
(B) char str2[6];
(C) char str3[7];
(D) char str4[8];
(E) char str5[9];
(F) none of the above

The following C program is intended to output the message "The sum is: 30." However, the current program produces incorrect output or undefined behavior. Which of the following statements correctly explain the errors in the main function?

#include <stdio.h>
int main()
{
int a = 10;
int b = 20;
printf("The sum is: " + a + b);
return 0;
}

(A) The variable a should be declared as a float variable instead of an int variable.
(B) The + operator cannot be used in the function call of printf.
(C) The printf function should use a format specifier in its format string.
(D) The return statement should return the sum of a and b.
(E) The format string and the integer expression a + b should be separated by a comma, not a + operator.
(F) none of the above

Which of the following statements regarding C operators are correct?

(A) Given an integer variable a with an initial value of $0$, the expression a++ increments the value of a after the current value is used in the expression.
(B) The modulus operator % can be used with float or double types.
(C) The return value of (5 < 10) && (15 < 10) || !(5 != 0) is $0$.
(D) The return value of !(1 < 2) && 2 / 1 || 0.5 / 2 || 10 % 3 is $1$.
(E) The precedence of the relational operators is higher than that of the arithmetic operators.
(F) none of the above

What are the correct expressions for blanks (1), (2), and (3) in the C program below to make the array num contain the values $\{6, 5, 0, 3, 2, 0\}$?

#include <stdio.h>
int main()
{
int num[2][3] = {6, 5, 4, 3, 2, 1};
int (1), *pt;
for (p = num; (2); p++) {
(3);
}
return 0;
}

(A) (1) (*p)[3]; (2) p <= num + 1; (3) (*p)[2] = 0
(B) (1) (*p)[2]; (2) p <= num + 2; (3) (*p)[3] = 0
(C) (1) *p[3]; (2) p <= num + 1; (3) *p[2] = 0
(D) (1) *p[2]; (2) p <= num + 2; (3) *p[3] = 0
(E) None of the options is correct.

Which of the following statements regarding bitwise operators in C are correct?

(A) Given a 16-bit unsigned integer variable i with the assigned value $7$, the return value of i << 2 is $56$.
(B) Given a 16-bit unsigned integer variable i with the assigned value 0x0010, the return value of i >> 3 is $1$.
(C) Given two 16-bit unsigned integer variables i with the assigned value $3$ and j with the assigned value $5$, the return value of i ^ j is $6$.
(D) Given two 16-bit unsigned integer variables i with the assigned value $3$ and j with the assigned value $5$, the return value of i | j is $9$.
(E) Given a 16-bit unsigned integer variable i with the assigned value 0x0030, the return value of i | 2 << 2 is $56$.
(F) none of the above

What are the correct expressions for blanks (1) and (2) to make the following program output the information stored in s1 correctly?

#include <stdio.h>

struct item {
char name[100];
char date[10];
};

typedef struct {
struct item product[2];
int row;
} Shelf;

int main()
{
Shelf s1 = {
.product[0] = {"A Little Life", "20150310"},
.product[1] = {"Taiwan Travelogue", "20200331"},
.row = 2
};
Shelf *s1_ptr = &s1;

int num = sizeof(s1.product) / sizeof(s1.product[0]);

for (int i = 0; i < num; i++) {
    printf("Product Name: %s; ", ____(1)____);
    printf("date: %s\n", ____(2)____);
}
return 0;

}

(A) (1) s1.product[i].name; (2) s1.product[i].date
(B) (1) s1.product[i]->name; (2) s1.product[i]->date
(C) (1) *s1_ptr.product[i].name; (2) *s1_ptr.product[i].date
(D) (1) (*s1_ptr).product[i].name; (2) (*s1_ptr).product[i].date
(E) (1) s1_ptr->product[i]->name; (2) s1_ptr->product[i]->date
(F) none of the above

What is the return type of a class constructor?

(A) An instance of the class.
(B) No return on a constructor.
(C) An int (the size of the class in bytes).
(D) A string (the name of the class).
(E) none of the above

Which of the following is NOT true about the special variable “this”?

(A) It is a reference value.
(B) You are allowed to change what it points to within a method.
(C) It points to the calling instance of a method.

Which of the following are true about a function which is templated?

(A) It is itself not a function, but a way to create a function.
(B) It contains the keyword template.
(C) It makes use of a template parameter to represent a calling type.
(D) none of the above

Which of the following describes the term “memory leak”?

(A) An undeclared array.
(B) A pointer that points to the value nullptr.
(C) Memory that was allocated by new but not deleted with delete.
(D) Memory that is untyped.
(E) none of the above

You are using a dynamic array (table) that doubles when full and halves when it is $\leq \frac{1}{4}$ full.

Which sequence results in the highest amortized cost per operation?

(A) $n$ insertions into an empty table
(B) $2n$ insertions followed by $n$ deletions
(C) Alternate insert/delete: insert, delete, insert, delete... for $n$ times ($n$ insertions, $n$ deletions)
(D) Insert $n$ times, delete all, insert $n$ times again
(E) none of the above

A stack supports operations push, pop, and multipop(k) (which pops up to $k$ elements).

Let $S$ be the stack and $|S|$ be the stack size. Consider the potential function:

$\Phi(S)=|S|$

Assume:

• push costs $2$.
• pop costs $0$.
• multipop(k) costs the number of elements actually popped.

The amortized cost of multipop(k) can be described as a function $g(k)$. Find the true statements below.

(A) $g(k)\in O(k)$
(B) $g(k)\in \Theta(1)$
(C) $g(k)\in \omega(\log k)$
(D) The amortized cost of multipop(k) also depends on the current stack size $|S|$.
(E) none of the above

Consider the $S,t$ flow network shown below.

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

After three augmenting paths have already been applied, the residual graph contains a backward edge with capacity $7$. Which of the following statements are true?

(A) The current flow is maximum.
(B) The flow violates capacity constraints.
(C) The residual graph must contain a cycle.
(D) A previous augmenting path used that edge forward.
(E) none of the above

Consider a simple graph $G(V,E)$ with $V=\{A,B,C,D,E,F,J,H,I\}$ and

$E=\{(A,B),(A,F),(A,J),(B,C),(B,D),(B,E),(B,J),(C,D),(E,F),(J,I),(J,H),(I,H)\}.$

What are the biconnected components?

(A) $\{A,B,C,D\}$
(B) $\{B,C,D\}$
(C) $\{A,B,E,F\}$
(D) $\{G,H,I\}$
(E) none of the above

Assume a hash table with $9$ slots that uses linear probing and the hash function $h(k)=k\bmod 9$. Insert the keys $8,17,26,35,44,0,9$ into the table in this order. Show the resulting array representation of the hash table (use “_” for empty slots).

(A) $[0,9,35,44,\_,17,26,\_,8]$
(B) $[17,9,0,26,35,44,\_,\_,8]$
(C) $[0,17,26,35,44,9,\_,\_,8]$
(D) $[17,26,35,44,0,9,\_,\_,8]$
(E) none of the above

Suppose we are debugging a Quicksort implementation that is intended to sort an array in ascending order. After the first partition step has been completed, the contents of the array are:

$5,2,8,11,20,18,14,12$

Which of the following statements are incorrect about the Quicksort?

(A) Quicksort is a stable sorting algorithm because elements equal to the pivot always preserve their relative order during partitioning.
(B) If the pivot is always chosen as the smallest or largest element, Quicksort still produces a correctly sorted array, even though its running time becomes $O(n^2)$.
(C) The pivot could have been $11$, but could not have been $14$.
(D) Quicksort always runs in $O(n\log n)$ time because each partition step divides the array into two nearly equal parts.

List the depth-first search numbers (starting from $1$) for each vertex in the order $A,B,C,D,E,F,G,H,I$.

What are the output values of $low(v)$ for each vertex $v$ in the given graph, listed in the order of $A,B,C,D,E,F,G,H,I$, when determining the articulation points from the previous question?

(A) $(1,2,4,3,6,4,4,6,6)$
(B) $(1,1,4,1,6,5,9,6,6)$
(C) $(1,1,4,1,6,4,4,7,8)$
(D) $(1,1,4,1,6,4,4,6,6)$
(E) none of the above

Based on the results of the previous two questions and the given graph, identify the articulation points.

(A) $(A,C,E,I)$
(B) $(B,G,E)$
(C) $(C,D,E,F)$
(D) $(A,C,E)$
(E) none of the above

Given the fully parenthesized arithmetic expression below, construct the corresponding expression tree and determine its pre-order traversal.

$((((A\times B)-(C\times D))-(E/F))+G)-(H/I)$

(A) $- + - - \times A B \times / C D E F G / H I$
(B) $- + / - G H I - / \times \times E F A B C D$
(C) $- + - - \times A B \times C D / E F G / H I$
(D) $- + / / G H I - F \times E - D \times C A B$
(E) none of the above

The following directed graph represents a project network, where each node denotes an event and each directed edge represents an activity with its duration. What is the critical path of the project?

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

(A) $1\to2\to4\to6\to10$
(B) $1\to3\to4\to7\to9\to10$
(C) $1\to3\to4\to5\to8\to9\to10$
(D) $1\to2\to4\to5\to7\to9\to10$
(E) none of the above

Given the following failure function in the KMP string-matching algorithm and a string “AAABAAAABAAAB” with $13$ characters, what are the values of the failure function for the entire string?

(A) $-1,0,1,-1,0,1,2,0,-1,0,1,2,3$
(B) $-1,0,1,0,1,2,2,2,3,4,5,6,-1$
(C) $-1,0,1,-1,0,1,2,2,3,4,5,6,3$
(D) $-1,-1,0,-1,-1,0,1,2,3,4,5,6,3$
(E) none of the above

Given the following in-order and post-order traversals of a binary tree, reconstruct the binary tree uniquely determined by these traversals, and then delete node $D$ from the tree. What is the level-order traversal of the resulting tree after the deletion?

In-order: $A,B,G,E,D,I,J,F,H,C$

Post-order: $G,E,J,I,H,F,D,C,B,A$

(A) $A,B,C,E,F,G,I,H,J$
(B) $A,B,G,E,C,I,J,F,H$
(C) $A,B,C,E,G,F,I,J,H$
(D) $A,B,C,J,E,F,G,I,H$
(E) none of the above

Determine the order in which vertices are selected by Dijkstra’s algorithm on the graph below, starting from source vertex $A$. If two unvisited vertices have the same tentative distance, select the vertex with the smaller alphabetical label first.

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

(A) $(A,D,B,E,F,C,G)$
(B) $(A,B,F,G,C,D,E)$
(C) $(A,D,B,F,G,C,E)$
(D) $(A,B,D,F,C,G,E)$
(E) none of the above

[Operator Overloading] Vector is widely used in the engineering and science world. Suppose we create a class called vector_2d. It can be used to represent a 2D vector, with $x$ and $y$ as its values. The partial code of this vector is shown below.

class vector_2d {
private:
double x;
double y;

public:
vector_2d() { x = 0; y = 0; }
vector_2d(double x_, double y_) { x = x_; y = y_; }

double get_x() const { return x; }
double get_y() const { return y; }

// Add overloaded operator+= here

}

Implement operator+= for vector_2d as a member function. If $a=\langle x_1,y_1\rangle$ and $b=\langle x_2,y_2\rangle$, after a += b, $a$ becomes $\langle x_1+x_2,y_1+y_2\rangle$, whereas $b$ is unchanged. Write no more than $5$ lines of code.