Algorithm and Programming
61 questions · Fundamental Engineering · 1–50
In the binary search tree below, when a new node of value 11 is inserted, where will this insertion be made?
For integers x and y (x > y ≥ 0), a function F(x, y) is defined as below:
What is the value F(231, 15)? Here, “x mod y” represents the remainder after division of x by y.
Which of the following is the appropriate description of constructors in Object-Oriented Programming (OOP)?
The table below shows the data in a list structure that has bidirectional pointers. In this table, a new Employee G is to be inserted between Employee A and Employee K. Which of the following contains only the pointers (among a through f) whose values change after the insertion?
Table
Table after the addition
The flowchart shown below expresses an algorithm that determines the greatest common divisor between two integers a and b. How many times is A passed?
Among the four tree traversal techniques—breadth-first, in-order, post-order, and pre-order—which of the following is the appropriate combination to ensure that the last two nodes visited are the same in the tree shown below, when the left child is explored first?
In the graph shown below, which of the following is the output of a depth-first traversal starting from vertex A, and visiting all vertices in ascending character order?
A hash table of size 11 uses open addressing with hash function h(k)=k mod 11, and linear probing. The table shown below is created after inserting 4 values into an initially empty hash table. Which of the following is the sequence that represents a possible order in which the key values were inserted into the table?
Which of the following is the computational complexity of the Heapsort algorithm? Here, n is the number of elements to be sorted, and all comparisons, swaps, and other needed operations can proceed in constant time.
What is the value of the arithmetic expression resulting from an in-order traversal of the binary tree below?
The function f(n) is recursively defined in terms of the natural number n as below. Which of the following is the value of f(5)?
f(n): if n≦1 then return 1 else return n + f(n−1)
Which of the following is the appropriate description of the “selection sort” algorithm?
The flowchart below shows an algorithm that determines the sum (i.e. “1 +3+ 5+ … + (2N−1)”) of the first N odd integers from 1 through 2N−1 (where N ≥ 1) and inserts the result into variable x. Which of the following is an expression to be inserted in blank A ?
How many swaps are required in bubble sort when N elements in the array are already sorted in reverse order?
Which of the following is the appropriate explanation of ideal hashing used during a data search?
When the series of stack operations below is performed on an empty stack, which of the following is the data that is read out by the last READ operation? Here, “PUSH x” is the operation to put data x in the stack, “POP” is used to retrieve data from the stack, and “READ” is used to read data from the top of the stack without removing the original data.
PUSH 2 → READ → PUSH 3 → PUSH 6 → POP → READ → PUSH 4
→READ → PUSH 7 → PUSH 5→ POP → POP → READ
In the table below, there are five items A through E. Each item cannot be divided into smaller pieces. When a knapsack with a maximum volume of 7 units is used for carrying the items, which of the following is a set of items to be packed in the knapsack so that the total price can be maximized?
The operations for a queue are defined as below.
On an empty queue, the operations ENQ 1, ENQ 2, ENQ 3, DEQ, ENQ 4, ENQ 5, DEQ, ENQ 6, DEQ, DEQ are performed. After that, when DEQ is performed, what is the value that is removed?
A five-digit number a1a2a3a4a5 needs to be stored in an array by means of hashing. When the hash function is mod (a1+a2+a3+a4+a5, 13) and the number is stored in the array element at the position corresponding to the calculated hash value, which of the following is the position where 54321 is stored in the array? Here, the value of mod (x, 13) is the remainder after dividing x by 13.
Which of the following is a program that achieves dynamic processing in a web environment and operates only on a web server?
Five (5) characters, A, C, K, S, and T, are input in this order. When using stacks, what is the minimum number of stacks required to rearrange the characters and output S, T, A, C, and K, in this order? Here, when a pop operation is performed for any stack, the popped character always becomes an output. Also, characters cannot be moved between stacks.
When a two-dimensional array A(5,5) is mapped to computer memory (i.e. a one-dimensional array) in row-major (row-directional) order or column-major (column-directional) order, how many elements occupy the same memory addresses in both cases? Here, the first element A(1,1) is mapped to the same starting memory address in either case.
Which of the following is a technology used to provide dynamic UI contents without reloading the entire web page by using an asynchronous communication feature of JavaScript?
For two-dimensional integer array A, whose (i, j)-th element A[i, j] is 2 × i + j, what is the value of element A[A[1, 1] × 2, A[2, 2] + 1]?
For two non-negative integers x and y, which of the following is the result of the procedure shown in the flowchart below?
When the Bubble sort algorithm is used, how many exchange operations are required to sort the numbers in ascending order?
9, 2, 13, 21, 3, 0
The GCD (Greatest Common Divisor) of two positive integers, x0 and x1 (x0 > x1), is computed by the procedure below. When x0 = 175 and x1 = 77, how many times should step (2) of this procedure be executed before it stops? Here, “A ← B” indicates that B is substituted for A.
[Procedure]
When a sequence of data, A, B, C, D, arrives in this order, which of the following is a possible sequence that can be produced using a single stack?
The in-order traversal of a binary tree is a procedure that visits all nodes of the tree. For a non-empty binary tree T, it performs the following operations in order.
Which of the following is the ordered sequence of nodes when the in-order traversal is performed on the binary tree below?
Which of the following is a technology that provides a dynamic user interface without page transition using an asynchronous communication in JavaScript?
When sorting an array of n elements by using a randomized version of the quicksort algorithm, where the pivot is selected randomly, which of the following shows the average-case and the worst-case time complexities? Here, big-O notation, O(x), is used to denote the growth rate.
After the procedure shown below has been executed in the listed order, which value will be stored in variable y? Here, the stack and queue structures are initially empty, and the four types of operations are defined as shown below.
[Procedure]
enq(1)
enq(2)
push(3)
push(deq())
enq(4)
push(deq())
y ← pop()
Which of the following is the name for the tree depicted below? Here, the number in each node represents the key of the node.
When the function M(n) is defined as shown below, what is the value of M(97)?
A list is implemented with two arrays box and next. Each element in the list corresponds to a pair (box[i], next[i]), where box[i] is the value of the element, and next[i] is the index to the next element in the list. When the element of value "H" is inserted between the third and fourth elements in the list shown below, which of the following is the value contained in next[8]? Here, next[0] contains the index of the leading (first) element of the list, the index i whose next[i] is 0 indicates the last element of the list, and each index i whose next[i] is blank indicates that the element is out of the list.
Two operations against a queue are defined below.
For an empty queue, a sequence of operations,
“ENQ 1, ENQ 2, ENQ 3, DEQ, ENQ 4, ENQ 5, DEQ, ENQ 6, DEQ, DEQ”,
is performed in this order. When another DEQ is performed in succession, what is the number to be removed by this operation?
Which of the following is a binary search tree? Here, the number in each node represents its value.
The flowchart below calculates the greatest common divisor of two (2) numbers, A and B, using the Euclidean algorithm with repeated subtraction. When A is 876 and B is 204, how many comparisons are required to obtain the result?
There are three stacks, A, B, and C, each having an initial state [1, 2, 3], respectively. When the recursively defined function, f(), below, is called and terminates, what is the state of stack B? Here, [a0, a1, …, an-1] represent the state of a stack. When an is pushed into this stack, the state becomes [a0, a1, …, an-1, an].
f() {
if A is empty {
do nothing
} else {
pop a value from A, then push it into C
call f()
pop a value from C, then push it into B
}
}
Two stack operations are defined:
PUSH n: Pushes a data (integer value n) to the stack.
POP: Pops a data from the stack.
For an empty stack, which of the following is the result of performing stack operations in the sequence below?
PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 →
PUSH 4 → POP → POP → PUSH 3
In a table search, which of the following is a characteristic of the search technique known as hashing?
The binary search algorithm is used to search for a given item when items are sorted. If the number of items is 1 million, which of the following is the closest to the maximum number of comparisons required to find the item?