(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

in the class

(yes)

(no) The function is recursive.

14 Let

(yes)

(no) 2

15 Look at Code Fragment: SSPQ2. Mark the correct/incorrect assertions.

(yes) The object

(no)