Algorithms Test 5

Number of Questions: 25 Section Marks: 30

Directions for questions 1 to 25: Select the correct alterna- 6. If we run Dijkstra’s algorithm starting from ‘S’ to find
tive from the given choices. shortest path ‘T’, consider the following statements:
1. Which of the following is NOT a tree? I. Dijkstra’s algorithm returns shortest path with
minimum total weight.
(A)
II. Dijkstra’s algorithm returns shortest path, with
minimum number of edges.
Which of the following is TRUE?
(A) I only (B) II only
(C) Both I and II (D) None of the above
7. The reason for using Bellman-Ford algorithm for find-
ing the shortest path between 2 vertices in a graph,
(B)
when Dijkstras algorithm does the same thing:
I. Bellman-Ford Algorithm is faster than Dijkstra’s
Algorithm.
II. Bellman-Ford Algorithm works on any directed
graph, with negative weights also.
(C) Which of the following is TRUE?
(A) I only (B) II only
(C) Both I and II (D) None of these
8. Consider the following statements:
I. By applying Breadth First search, on a tree with
(D) None of the above all edges having equal weight; finds minimum dis-
2. What is the number of vertices in a tree with 57 edges? tance from root to any node.
(A) 58 (B) 26 – 4 II. Use of greedy algorithm to solve the knapsack
(C) 56 (D) 57 with fractions is optimal.
3. Consider 2 graphs G1 and G2: Which of the following is TRUE?
I. G1 is connected and every edge is a bridge. (A) I only (B) II only
II. In G2 for any pair of vertices in the graph there is (C) Both I and II (D) None of the above
one and only one path joining them. 9. Consider the set of keys {1, 4, 5, 10, 16, 17, 21}, Draw
Which of the following is TRUE? a binary search tree with height ‘2,’ Then what values
(A) G1 is a tree but G2 is not a tree will appear at internal nodes? [height of root node is
(B) G1 is not a tree but G2 is a tree ‘0’]
(C) Both G1 and G2 are trees (A) 10, 5, 16 (B) 10, 4, 17
(D) Both G1 and G2 are not trees (C) 4, 17, 21 (D) 5, 10, 17
4. How many spanning trees does the following graph 10. Consider the set of keys {2, 5, 6, 11, 17, 18, 22}, Draw
contain, (Assume that all edges have same weight)? a binary search tree with height ‘6’, then, what will be
the child node values (height of root node is 0).
a
(A) 2 (B) 22
(C) Either 2 or 22 (D) None of the above
b c
11. The following is a directed graph
G = (V, E):
d e V = {a, b, c, d, e, f, g}
E = {(a, b), (c, a), (b, c), (c, d), (d, e),
(A) 2 (B) 3 (e, f), (e, g), (f, g), (d, g)}
(C) 4 (D) 5 Identify the correct strongly connected components,
5. Suppose we have a graph where each edge value which of the following is TRUE?
appears atmost twice, then what will be the number (A) There are 3 strongly connected components.
(atmost) of minimum spanning Trees of this graph? (B) There are 4 strongly connected components.
(A) 2 (B) 3 (C) There are 5 strongly connected components.
(C) 4 (D) 6 (D) None of the above
 Algorithms Test 5 | 3.103

12. Consider the given graph, with some edges in bold: 16. Consider the given tree:
A 40
9 10
6 39
2
B C

13 18 15 22 38
8
3
4 16 12 11
D E
5
The MAX HEAP property is applied on the above tree,
The bold edges given in the above graph cannot form a (box area), at node with value ‘6’, which of the follow-
spanning Tree because ing is BEST suitable?
(A) The bold edges are not connected (A) First compare 6 and 18 then swap them if required
(B) The bold edges are not least weight edges (B) First compare 6 and 15 then swap them if required.
(C) First compare 18 and 15, then compare the greater
(C) The kruskals algorithm is not implemented on the
element with ‘6’ and swap them if required.
above graph.
(D) Any one of the above
(D) Both (A) and (B)
17. Consider the following statements about Depth First
13. Consider the given statements: traversal:
I. A digraph is a graph with exactly 2 vertices. I. Suppose we run DFS (Depth First search) on an
n
II. A spanning tree of a graph must contain atleast undirected graph and find exactly 15 back edges.
edges always. 2 Then the graph is guaranteed to have at least one
III. The sorted edges algorithm for solving the trav- cycle.
elling salesman problem always gives optimal re- II. DFS on a directed graph with ‘n’ vertices and at
sult. least ‘n’ edges is guaranteed to find at least one
back edge.
Which of the following is TRUE?
Which of the following is TRUE?
(A) I and II (B) II and III (A) I only (B) II only
(C) I and III (D) Only II (C) Both I and II (D) None of the above
14. Consider the given AVL-tree, 18. Suppose ‘G’ is a connected, undirected graph, whose
edges have positive weights. Let M be a minimum
7 spanning Tree of this graph. We modify the graph by
adding ‘6’ to the weight of each edge, which of the fol-
14 lowing is TRUE?
(A) The order of edges added to minimum spanning
5 tree using kruskal’s algorithm, will change.
10 17
(B) The modification adds 6(|V| – 1) to the total weight
3 6 of all spanning trees.
11 (C) The order of edges added to minimum spanning
tree using prim’s algorithm, will change.
If the element with value ‘12’ is inserted into above (D) None of the above
AVL tree, How many rotations are required to balance
the tree? 19. Consider the following graph:
(A) 0 (B) 1 A C E G
(C) 2 (D) 3
15. In which order, the element must be inserted into an
AVL tree, so that, no single Rotation is required, for the
B D F H
given
Elements = {1, 2, 3, 4, 5, 6, 7} Which of the following orderings not a valid topologi-
(A) {4, 2, 6, 1, 3, 5, 7} cal sort of the graph?
(B) {4, 2, 1, 3, 5, 6, 7} (A) BACEDFGH (B) ABCDEFGH
(C) {7, 6, 5, 4, 2, 1, 3} (C) ABCDEGFH (D) BACDEFGH
(D) {4, 1, 2, 3, 5, 6, 7}
3.104 | Algorithms Test 5

20. What is the time complexity to print all the keys of a (A)
binary search tree in sorted order? abef cd
(A) O (log n) (B) q (n)
(C) q (n2) (D) O (n + log n)
21. Let T1, T2, T3, T4, T4, T5, T6 are tasks given along with
their deadlines and profits:
Tasks T1 T2 T3 T4 T5 T6
g h
Deadlines 2 1 3 2 3 1
Profit 6 4 3 7 2 8 (B)
abe cd
Which of the following tasks are not completed?
(A) T6, T4, T3 (B) T6, T1, T2
(C) T1, T2, T5 (D) T4, T5, T6
22. Consider the below program fragment:
for i ← 1 to length (A) – 1
{ f gh
element ← A [i]
pos ← i
(A)
while pos > 0 and A [pos – 1] de
{ abc
A[pos] ← A[pos – 1]
pos ← pos –1
{
A[pos] ← element.
}
This code implements fg h
(A) Bubble sort (B) Insertion sort
(C) Heap sort (D) Bucket sort (D)
abe cd
23. What is the best case time complexity of given algo-
rithm in Q. 22?
(A) q (n2) (B) q (log n)
(C) q (n) (D) q (n log n)
24. Which of the following is an acyclic component graph fg h
of given graph using strongly connected components
algorithm?
25. Consider an undirected graph
a b c d G = (V, E)
V = {r, s, t, u, v, w, x, y}
E = {(r, s), (r, v), (s, w), (w, t), (w, x), (t, u),
(t, x), (u, y), (u, x) (x, y)}
Which node has the highest degree?
e f g h (A) w (B) x
(C) u (D) t

Answer Keys
1. C 2. A 3. C 4. B 5. C 6. A 7. B 8. C 9. B 10. C
11. C 12. A 13. D 14. B 15. A 16. C 17. A 18. B 19. A 20. B
21. C 22. B 23. C 24. D 25. B
 Algorithms Test 5 | 3.105

Hints and Explanations

1. A graph without any cycles is called a Tree graph. 5. Assume the following graph:
Option (C) 2 3
4
f 1
1
2 3
b e
Spanning Tree 1: Spanning Tree 2:
2 3
2
4 4
a g 1 1
c d 1 1
3
There is a cycle (b – e – f – d – b) in the graph.
Choice (C) Spanning Tree 3: Spanning Tree 4:
3
2. A tree with ‘n’ vertices contains (n – 1) edges. 4 4
1 1 1 1
n – 1 = 57 2 3 2
Number of vertices, n = 58 Choice (A)
3. G1: Example: Atmost 4 minimum spanning trees are possible.
b d f Choice (C)
6. I. Dijkstra’s algorithm always returns shortest path
with minimum total weight.
a c e g II. 1
a b
2
∴ No cycles, It is a tree 1
G2: Example: S
a T
3
c 1

b c Dijkstra’s Algorithm gives, shortest path (length = 3)

d 1 1 2
S a b T

e But the shortest path

∴ No cycles, S
3
c
1
T
If we have cycle
a
has length = 2
I–TRUE, II–False Choice (A)
b 7. Dijkstra’s is faster than Bellman-Ford, but It cannot
c
work on graphs with negative weight edges.
d
Choice (B)
8. Applying BFS on a tree with equal weights results the
e same tree and it gives minimum distance from root to
There will be different paths from (a – e) other nodes. Knapsack fractional problem is optimally
(i) a – b – d – e solved using greedy design strategy. Choice (C)
(ii) a – c – d – e 9. 1, 4, 5, 10, 16, 17, 21
∴ G2 is also a tree. Choice (C)
10
4. Spanning trees:
4 17

16 21
1 5

With height = 2, Internal nodes are 10, 4, 17.

Choice (B) Choice (B)
3.106 | Algorithms Test 5

10. 2 II–TRUE
22
III. There is no optimal solution for Travelling sales
5 18 person problem.
∴ Only II is TRUE Choice (D)
6 17
14. 7
11
11 14
5 10
6 R
17 10 17
3 6 -2 11
5 ª R
18 11 -1
12
2
22 12 0
7
Tree 1: Child 22 Tree 2: Child 2
14
Choice (C) 11 5
11. 17
12 ª 3 11
10 6
a b c
10 12

RR–Imbalance: perform Left Rotation.

d e f ∴ 1 Rotation. Choice (B)
15. Option (A):
4
g
2 6
Strongly connected components are:
{abc} {d} {e} {f} {g} 1 3 5 7
There are five strongly connected components.
Choice (C) Option (C):
12. Kruskals algorithm is been implemented on the given
graph. The bold edges are least weight edges, because 7

the complete spanning tree will contain following

6
edges:
9 5

2
requires LL rotation
3 for 1st 3 elements
Option (B): Option (D):
5 4
4
5
Choice (A) 2 1
13. I. Digraph:
6
There is no limit on number of vertices, In digraph 1 2
edges will have directions.
7
I–False requires LL rotation 3
II. Example: Spanning tree
for 1st 3 elements

G1 T1
If we have Imbalance, we need to perform Rotation.
Option (A) has no Imbalance. Choice (A)
16. First compare the children of a node. If it is a max heap,
then compare the child with greater value to parent
T2
G2 node, if required swap them. Choice (C)
 Algorithms Test 5 | 3.107

17. I. If the graph has a back edge, then it has a cycle. Order of execution of tasks to maximize the profit
II. a 8 7 3
T6 T4 T3
b c
0 1 2 3 4 5
The uncompleted tasks are T1, T2, T5
DFS on the above graph starting at ‘a’ does not Choice (C)
find any back edge. 22. The given code implements insertion sort. In insertion
a
sort, every iteration removes an element from the input
data and insert it into the correct position in the already
sorted list until no input elements remain. Choice (B)
23. The best case input is when the array is already in
b
sorted order. Then time complexity is q(n) because in
each iteration, the first remaining element of input is
only compared with the right-most element of sorted
c list of the array. Choice (C)
24. Strongly connected components of a directed graph
∴ I–TRUE, II–False Choice (A) G = (V, E) is a maximal set of vertices C ⊆ V such that
18. The order of edges added to minimum spanning tree for every pair of vertices u and v in C, vertices u and
does not change, because we are adding same weight to v are reachable from each other. In the given graph the
all the edges. connected components are {a, b, e}, {f, g}, {c, d} and
To the total weight we have to add 6(V – 1), because in {h}.
a spanning tree, there will be (V – 1) edges, For every Hence, the required acyclic component graph will be
edge additional weight ‘6’ is added. Choice (B)
abe cd
19. Option (A):
BACEDFGH
There is an edge from D → E
Where as in the order E appears first and D appears
next. Which is invalid.
Check the other options in the same manner. fg h
Choice (A)
20. We can print all the keys of a binary search tree in
sorted order using inorder traversal which will take Choice (D)
q(n) time. Choice (B) 25. r s t u

21. Arrange the given tasks according to their profits

Tasks T6 T4 T1 T2 T3 T5
Profit 8 7 6 4 3 2 v w x y

Deadline 1 2 2 1 3 3 Highest degree node = x(degree = 4) Choice (B)