CS502 Quiz

CS502 – Fundamentals of Algorithms · Important Macq’s for Final Term · By · CS Experts

Q1. Dijkstra’s Algorithm is used to solve _____________ problems.

1. All pair shortest path
2. Single source shortest path
3. Network flow
4. Sorting

Correct answer: Single source shortest path

Q2. Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?

1. Max priority queue
2. Stack
3. Circular queue
4. Min priority queue

Correct answer: Min priority queue

Q3. What is the time complexity of Dijikstra’s algorithm?

1. O(N)
2. O(N3)
3. O(N2)
4. O(logN)

Correct answer: O(N2)

Q4. Dijkstra’s Algorithm cannot be applied on ______________

1. Directed and weighted graphs
2. Graphs having negative weight function
3. Unweighted graphs
4. Undirected and unweighted graphs

Correct answer: Graphs having negative weight function

Q5. How many priority queue operations are involved in Dijkstra’s Algorithm?

1. 1
2. 3
3. 2
4. 4

Correct answer: 3

Q6. How many times the insert and extract min operations are invoked per vertex?

1. 1
2. 2
3. 3
4. 0

Correct answer: 1

Q7. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to ___________

1. Total number of vertices
2. Total number of edges
3. Number of vertices – 1
4. Number of edges – 1

Correct answer: Total number of edges

Q8. What is running time of Dijkstra’s algorithm using Binary min- heap method?

1. O(V)
2. O(VlogV)
3. O(E)
4. O(ElogV)

Correct answer: O(ElogV)

Q9. The running time of Bellmann Ford algorithm is lower than that of

1. True
2. False

Correct answer: False

Q10. Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non- negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V.

1. True
2. False

Correct answer: True

Q11. Dijkstra’s Algorithm is the prime example for ___________

1. Greedy algorithm
2. Branch and bound
3. Back tracking
4. Dynamic programming

Correct answer: Greedy algorithm

1. Computing the strongly connected components of a graph is a generalization of the problem to determine whether a digraph is strongly connected or not.

True

2. If u finds yourself in maze the better traversal approach will be:

BFS and DFS are valid

3. In ----------- algorithm, at any time, the subset of edges A forms

Prim’s