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)