The questions of Test_3
with
two model
answers - one correct (yes) and one incorrect (no)
Mark the correct/incorrect definitions and assertions about graphs.
(yes) A cycle is a path whose start and end vertices are the same.
(no) The space usage for adjacency matrix representation is O(n)
for a graph of n nodes.
Let us have a graph ADT with n vertices and m edges.
Let v and w be node positions, e be an edge position.
Mark the correct/incorrect correspondence between a function of this
ADT and its run-time in the edge-list
implementation of the graph.
(yes) numVertices() - O(1)
(no) degree(v) - O(m)
Let us have a graph ADT with n vertices and m edges.
Let v and w be node positions, e be an edge position.
Mark the correct/incorrect
correspondence between a function of this ADT and its run-time in the adjacency
list representation of the graph.
(yes) numVertices() - O(1)
(no) adjacentVertices(v)
- O(n)
Let us have a graph ADT with n vertices and m edges.
Let v and w be node positions, e be an edge position.
Mark the correct/incorrect
correspondence between a function of this ADT and its run-time in the
adjacency
matrix representation of the graph.
(yes) vertices() - O(n)
(no) aVertex() - O(n)
Let us have an undirected graph:
V = {A, B, C, D}, E = {e=(A,B),f=(B,C),g=(C,D),h=(B,D)}.
Determine the correct/incorrect pairs:
function, its output value. p(X)
means the position of the element X;
I denotes an iterator.
(yes) numVertices(), 4
(no) degree(p(B)), 2
Let us have a directed graph:
V = {A, B, C, D}, E = {e=(A,B),
f=(B,C), g=(C,D), h=(B,D)}.
Determine the correct/incorrect pairs:
function, its output value. p(X)
means the position of the element X.
(yes) destination(p(f)), p(C)
(no) origin(p(g)), p(A)
Let us have a directed graph G:
V={A,B,C,D}, E={e=(A,B),f=(B,C),g=(C,D),h=(B,D)}.
Determine the correct/incorrect pairs: function - new_G.
A pair is correct, when applying the given function on G,
the second member is the new graph G.
(yes) insertEdge(p(A),p(D),d) -
E={e=(A,B),f=(B,C),d=(A,D),g=(C,D),h=(B,D)}
(no) removeVertex(p(A)) -
V={B,C,D}, E={e=(A,B),g=(C,D),h=(B,D)}
Mark the correct/incorrect definitions and assertions about sorting
algorithms.
(yes) Algorithm merge-sort
sorts a sequence of size n
in O(n log
n) time in the worst case.
(no) Algorithm quick-sort
sorts a sequence of size n
in O(n log
n) time in the worst case.
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.
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})
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)
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
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) abcde
Create a binary tree
representation of the following arithmetic
expression:
(x + 2*(y - 2)) / 2.
Determine the correct/incorrect substrings of a string of nodes,
obtained in preorder traversal
of this binary tree.
(yes) / + x
(no) x * y
Create a binary tree
representation of the following arithmetic
expression:
(x + 2*(y - 2)) / 2.
Determine the correct/incorrect substrings of a string of nodes,
obtained in postorder traversal
of this binary tree.
(yes) x 2 y 2
(no) x y - *
Create a binary tree
representation of the following arithmetic
expression:
(x + 2*(y - 2)) / 2.
Determine the correct/incorrect substrings of a string of nodes,
obtained in inorder traversal
of this binary tree.
(yes) x + 2 * y
(no) / 2 - 2 2
Let us have a stack ADT S = (5,3,4,9). The top element
is 5.
Determine the
correct triples: operation -
output - new stack. The triple is
correct, when applying the given function on S, the second triple
member is its the return value and the third member is the new
stack S.
(yes) push(1) - NONE -
(1,5,3,4,9)
(no) push(10) - NONE -
(5,3,4,9,10)
Let us have a queue ADT Q = (8,7,2). The front element
is 8.
Determine the
correct triples: operation -
output - new queue. The triple is
correct, when applying the given function on Q, the second triple
member is its the return value and the third member is the new
queue Q.
(yes) enqueue(5) - NONE -
(8,7,2,5)
(no) enqueue(7) - 7 - (8,7,2,7)
Let us have a double-ended queue
(deque) ADT
D = (8,1,2). The front
element is 8.
Determine the
correct triples: operation -
output - new deque. The 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
deque D.
(yes) insertFirst(5) - NONE -
(5,8,1,2)
(no) size() - 2 - (1,2)