The
questions of Final
Test
with
two
model
answers
-
one
correct (yes) and one incorrect (no)
1 Mark correct/incorrect assertions about asymptotic notation for the
following functions.
(yes) 2n +
3n2 is O(n2)
(no) n
+ n2 is O(n)
2 We have:
int i =
4, j =
2, k = 1;
Determine the correct/incorrect value,
given
as
a
comment for the folowing expressions:
(yes) i -= j // 2
(no) j *= -j // 4
3 Mark the
correct/incorrect
definitions and assertions about search
trees.
(yes) Keys stored at nodes in the left subtree of a node v (of a search tree) are less then or
equal
to the key at v.
(no) Each internal node of a (2,4)
tree has at least four children.
4 Let us have a (2,4) tree ADT
in parenthetic string representation
T={12}({3,6,9},{15}).
External nodes are not included in this
representation.
Determine the correct/incorrect resulting (2,4) tree after
applying the
corresponding
operation.
(yes) insertItem(1) -
T={12,6}({1,3},{9},{15})
(no) insertItem(1) -
T={12,3}({1,6,9},{15})
5 Let us have a red-black
tree ADT in parenthetic string
representation,
where black nodes are bold, and red nodes are italic.
External nodes are not included in this representation.
Determine the correct/incorrect resulting red-black
tree after applying
the corresponding
operation.
(yes) 6(8) - insertItem(7) - 7(6,8)
(no) 6(8) - insertItem(9) - 6(8,9)
6
A simple open addressing strategy for collision handling in hash
tables is linear
probing.
Let
us
have
a bucket array A =
{35,14,D,21,E,12,E} with
capacity N = 7,
where E means
"empty" and
D means "deattached"
(or
"available") item.
The hash function is h(k) = k mod 7. Find the
correct/incorrect
correspondence,
where -> means
"is
equivalent to".
(yes) insrtItem(7) ->
A[2] = 7
(no) insrtItem(38) ->
A[3] =
38
7 Let us have a binary tree ADT
in parenthetic string representation a(b(c(d,e),f),g(h,i(j(k,l),m)).
Is
the
given
sequence a part of the sequence of nodes, obtained in Euler tour traversal of this
binary
tree?
(yes) abcd
(no) ecbc
8 Create a binary tree
representation of the following arithmetic
expression:
(x + 2*(y - 2)) / 2.
Is the given sequence a part of the sequence of nodes, obtained in
preorder traversal of
this binary
tree?
(yes) / + x
(no) x * y
9 Let us have a deque ADT
D = (8,1,3). The front
element is 8.
For a deque operation, determine its return value and its effect
on D.
(yes) insertFirst(5) - NONE
-
D = (5,8,1,3)
(no) size() - 2 - D = (1,3)
10 Let us have an AVL tree ADT
in parenthetic string representation 44(17(-,32),78(50(48,62),88)).
External nodes are not included in this representation. Determine
the
correct/incorrect resulting AVL tree after applying the
corresponding
operation.
(yes) insertItem(54)
44(17(-,32),62(50(48,54),78(-,88)))
(no) insertItem(54)
44(17(54,32),78(50(48,62),88))
11 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
12 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
13 Mark the
correct/incorrect definitions and assertions about linear data
structures.
(yes) A linear sequence that support access to its elements by
their
ranges is called a vector.
(no) A linear sequence that support access to
its
elements by their positions is called a vector.
14 Mark the
correct/incorrect definitions and assertions about trees.
(yes) A node is internal if it has one or
more
children.
(no) A node is internal if it has no
children.