The questions of Test_2

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


Mark the correct and incorrect definitions and assertions about trees.
(yes) If node u is the parent of node v, we say that v is a child of u.
(no) Nodes that are children of the same parent are called leaves.

Let us have a tree ADT with n elements. Let
v and w be positions in the tree. Mark the correct/incorrect correspondence between a function of this ADT and its run-time assumptions.
(yes)
root(v) - O(1)
(no)
parent(v) - O(n)

Let us have an ordered tree ADT in parenthetic string representation
T=A(B(H,E(I,J),F),C(G),D). Determine the correct/incorrect pairs: function, its output value. p(X) means the position of the element X. [Hint: See p.268 for "parenthetic string representation".]
(yes)
root(), p(A)
(no)
root(), p(D)

Let us have an ordered tree ADT in parenthetic string representation
T=A(B(H,E(I,J),F),C(G),D). Is the given sequence a part of the sequence of nodes, obtained in preorder traversal of the tree?
(yes)
ABH
(no)
EB

Let us have an ordered tree ADT in parenthetic string representation
T=A(B(H,E(I,J),F),C(G),D). Is the given sequence a part of the sequence of nodes, obtained in postorder traversal of the tree?
(yes)
HIJ
(no)
EB

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 inorder traversal of this binary tree?
(yes)
hdib
(no)
hdie

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)
bdhid

Create a binary tree representation of the following arithmetic expression:
(9 * (5 + a) + b) / 2. Is the given sequence a part of the sequence of nodes, obtained in preorder traversal of this binary tree. [Hint: See p.258, Example 6.5.]
(yes)
/+*
(no)
9/2

Create a binary tree representation of the following arithmetic expression:
(9 * (5 + a) + b) / 2. Is the given sequence a part of the postorder traversal sequence of this binary tree.
(yes)
95a
(no)
9/2

Mark the correct/incorrect definitions and assertions about priority queues and heaps.
(yes) A key is an object that is assigned to an element as a specific attribute for that element and that can be used to identify, rank, or weight that element.
(no) In a heap storing n keys, upheap (bubbling) algorithm runs O(n) time.

Let us have a priority queue ADT with n elements implementation with an unsorted sequence. Mark the correct/incorrect correspondence between a function of this ADT and its performance.
(yes)
minElement() - O(n)
(no)
minKey() - O(1)

Let us have a priority queue ADT
P={(5,A),(7,D),(9,C)}. For a function of this ADT determine the return value and its effect on P.
(yes)
insertItem(3,B)-NONE-{(3,B),(5,A),(7,D),(9,C)}
(no)
minElement()-5-{(5,A),(7,D),(9,C)}

Let us have a priority queue ADT with n elements implementation with a sorted sequence. Mark the correct/incorrect correspondence between a function of this ADT and its performance.
(yes)
minElement() - O(1)
(no)
minElement() - O(n)

Let us have a priority queue ADT with n elements for the heap implementation. Mark the correct/incorrect correspondence between a function of this ADT and its performance.
(yes)
minElement() - O(1)
(no)
minElement() - O(n)

Let us have the vector representation of a heap. Guess the correct representation after applying the method InsertItem(1,1).
(yes) 2,4,5 -> 1,2,5,4
(no) 2,4,5 -> 1,2,4,5

Let us have the vector representation of a heap.Guess the correct representation after applying the method RemoveMin().
(yes)
1,2,5,4 -> 2,4,5
(no) 1,2,5,4 -> 4,2,5