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 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 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)}. For a function of this ADT determine the return value and its effect on P. 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 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 realization of dictionary ADT and its performance. (yes) size() - O(1) (no) insertItem(k,e) - O(n) ------------------------------------------------------------------------