The questions of Test_3

with two model answers - one correct (yes) and one incorrect (no)

Mark the correct/incorrect definitions and assertions about sorting algorithms.
(yes) Algorithm merge-sort sorts a sequence of size n in O(n log n) time in the worst case.
(no) Algorithm quick-sort sorts a sequence of size n in O(n log n) time in the worst case.

Mark the correct/incorrect definitions and assertions about search trees.
(yes) Keys stored at nodes in the left subtree of a node v (of a search tree) are less then or equal to the key at v.
(no) Each internal node of a (2,4) tree has at least four children.

Let us have a (2,4) tree ADT in parenthetic string representation T={12}({3,6,9},{15}). External nodes are not included in this representation. Determine the correct/incorrect resulting (2,4) tree after applying the corresponding operation.
(yes) insertItem(1) - T={12,6}({1,3},{9},{15})
(no) insertItem(1) - T={12,3}({1,6,9},{15})

Let us have a red-black tree ADT in parenthetic string representation, where black nodes are bold, and red nodes are italic. External nodes are not included in this representation. Determine the correct/incorrect resulting red-black tree after applying the corresponding operation.
(yes) 6(8) - insertItem(7) - 7(6,8)
(no) 6(8) - insertItem(9) - 6(8,9)

A simple open addressing strategy for collision handling in hash tables is linear probing. Let us have a bucket array A = {35,14,D,21,E,12,E} with capacity N = 7, where E means "empty" and D means "deattached" (or "available") item. The hash function is h(k) = k mod 7. Find the correct/incorrect correspondence, where -> means "is equivalent to".
(yes) insrtItem(7) -> A[2] = 7
(no) insrtItem(38) -> A[3] = 38

Let us have a binary tree ADT in parenthetic string representation T = a(b(d(h,i),e),c(f,g(j(l,m),k)). Is the given sequence a part of the sequence of nodes, obtained in Euler tour traversal of this binary tree?
(yes) abdhd
(no) abcde

Create a binary tree representation of the following arithmetic expression: (x + 2*(y - 2)) / 2. Is the given sequence a part of the sequence of nodes, obtained in preorder traversal of this binary tree?
(yes) / + x
(no) x * y

Create a binary tree representation of the following arithmetic expression: (x + 2*(y - 2)) / 2. Is the given sequence a part of the postorder traversal sequence of nodes of this binary tree?
(yes) x 2 y 2
(no) x y - *

Create a binary tree representation of the following arithmetic expression: (x + 2*(y - 2)) / 2. Is the given sequence a part of the postorder traversal sequence of this binary tree?
(yes) x + 2 * y
(no) / 2 - 2 2

Let us have a stack ADT S = (5,3,4,9). The top element is 5. For a stack operation, determine its return value and its effect on S.
(yes) push(1) - NONE - S = (1,5,3,4,9)
(no) push(10) - NONE - S = (5,3,4,9,10)

Let us have a queue ADT Q = (8,7,2). The front element is 8. For a queue operation, determine its return value and its effect on Q.
(yes) enqueue(5) - NONE - Q = (8,7,2,5)
(no) enqueue(7) - 7 - Q = (8,7,2,7)

Let us have a deque ADT D = (8,1,3). The front element is 8. For a deque operation, determine its return value and its effect on D.
(yes) insertFirst(5) - NONE - D = (5,8,1,3)
(no) size() - 2 - D = (1,3)