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) .
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