The questions of Test 2
with two model answers - one correct
(yes) and one incorrect (no)
1 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.
2 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)
3 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)
4 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
5 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
6 Let us have a binary tree in parenthetic
string representation. Is the given sequence a part of the
sequence of nodes, obtained in inorder
traversal of this binary
tree?
(yes) c(b(a,d),e); bdc
(no) d(e,c(g,a(f,b))); cfb
7 Create a binary tree representation of the
given arithmetic
expression and check that
the sequence x2y is
a part of the postorder traversal.
(yes) (x+2*(y-2))/2
(no) (x-2)*y
8 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
9 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.
10 Let us have a priority queue ADT with n elements implementation
with unsorted sequence,
denoted by "U:"
or with sorted sequence, denoted by "S:".
Mark the correct/incorrect correspondence between a
function of this ADT and its performance.
(yes) U: minElement() - O(n)
(no) U: minKey() - O(1)
11 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
12 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
13 Specify true and false claims to the following definition of
the member function
Element& element(const
Position& p)
{
return
p.element().element();
}
in the class HeapPriorityQueue (see html-7.8 (HPQ1)).
(yes) p is
an
object of the class Position.
(no) The function is recursive.
14 Let n be number of nodes, e -
number of external nodes, i - number of internal nodes of
a proper binary tree, and h be its height. Mark correct and
incorrect equalities and inequalities.
(yes) i = e - 1
(no) 2e = n
15 Look at Code Fragment: SSPQ2. Mark the correct/incorrect
assertions.
(yes) The object S is an implementation of Sequence ADT.
(no) comp is a comparator class name.