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)
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"
cell 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
------------------------------------------------------------------------