### 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) . Determine the correct/incorrect substrings of a string 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) . Determine the correct/incorrect substrings of a string 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)) . Determine the correct/incorrect substrings of a string 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)) . Determine the correct/incorrect substrings of a string 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 . Determine the correct/incorrect substrings of a string 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 . Determine the correct/incorrect substrings of a string of nodes, obtained in postorder traversal of this binary tree.
(yes) 95a
(no) 9/2

Mark the correct and 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 P = {(5,A),(7,D),(9,C)} . Determine the correct/incorrect triples: function-output-new_P . A triple is correct, when applying the given function on P , the second triple member is its the return value and the third member is the new priority queue 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 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 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)

Mark the correct and incorrect definitions and assertions about the dictionary ADT.
(yes) A dictionary ADT stores key-element pairs (k,e) which we call items, where k is the key and e is the element.
(no) Keys in a dictionary can be arbitrary objects on which a total order must be defined.

Let us have a dictionary ADT D = {(7,B),(2,C),(2,E)} . Determine the correct/incorrect triples: function-output-new_D . A triple is correct, when applying the given function on D, the second triple member is its the return value and the third member is the new dictionary D. The notation p(X) indicates the position of the item storing element X .
(yes) insertItem(8,A)-NONE-{(7,B),(2,C),(2,E),(8,A)}
(no) find(B)-p(7)-{(7,B),(2,C),(2,E)}

A simple way of realizing a {\bf dictionary} is to use an unordered vector, list, or general sequence to store the key-element pairs. Such an implementation is called a log file}. Mark the correct/incorrect correspondence between a function of this ADT and its performance.
(yes) size() - O(1)
(no) insertItem(k,e) - O(n)

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