CS502 Final Term MCQs by VU Topper RM

Q1. Vu-Topper RM (1 marks)

______________ Algorithm allows negative weights edges and no negative cost cycles. A. Brute-force technique

B. Bellman-Ford Page 159

C. Dijkstra’s D. Print

Q2. Vu-Topper RM (1 marks)

In Prim's algorithm, we start with the _______ vertex r; it can be any vertex.

A. Root Page 149

B. Pivot C. Leaf D. Negative

Q3. Vu-Topper RM (1 marks)

Overall Running time of Prim's algorithm is _______. A. Θ(ElogE) B. Θ(ElogV)

C. Θ((V+E)logV) Page 152

D. Θ((V+E)logE)

Q4. Vu-Topper RM (1 marks)

Problems such as the shortest route between cities can be solved efficiently by modeling the road map as a______________. A. Tree B. Stack

C. Graph Google

D. Linked list

Q5. Vu-Topper RM (1 marks)

In Kruskal's algorithm, the next edge is added to viable set A, if its adding does not induce a/an __________ . A. Tree B. Edge

C. Cycle Page 147

D. Vertex

Q6. Vu-Topper RM (1 marks)

Bellman-Ford algorithm is used to solve ____________ problems. A. Flow of networking B. All pair shortest path

C. Single source shortest path Google

D. Double source shortest path

Q7. Vu-Topper RM (1 marks)

In Prim's algorithm, If the color of a vertex is __________,then it is in S otherwise not. A. Blue B. Gray

C. Black Page 151

D. White

Q8. Vu-Topper RM (1 marks)

Keeping in mind the shortest-path, if given scenarios occur in computer networks like the internet where data packets have to be routed. The vertices are_________and Edges are _____________which may be wired or wireless. A. Internet, routers B. Routers, internet C. Communication links, routers

D. Routers, communication links Page 153

Q9. Vu-Topper RM (1 marks)

Dijkstra’s algorithm : A. Has greedy approach to find all shortest paths B. Has both greedy and Dynamic approach to find all shortest paths C. Has greedy approach to compute single source shortest paths to all other vertices Page 154 D. Has both greedy and dynamic approach to compute single source shortest paths to all other vertices.

Q10. Vu-Topper RM (1 marks)

In Dijkstra’s algorithm, initially the estimated value from source vertex to any vertex v is: A. One (1) B. Zero (0)

C. Infinity (∞) Page 154

D. Minus one (-1)

Q11. Vu-Topper RM (1 marks)

From the given option’s which one is correct regarding the time complexity of Dijkstra’s algorithm: A. O(N)

B. O(N^2) Google

C. O(N^3) D. O(log N)

Q12. Vu-Topper RM (1 marks)

In Bellman-Ford Algorithm, relaxation applies to ____________ of the graph.

A. Every edge Page 159

B. Every Vertices C. Only First edge D. Only First Vertices

Q13. Vu-Topper RM (1 marks)

The key[u] is the weight of the __________ going from u to any vertex in S. A. Edge B. lighter edge

C. lightest edge Page 151

D. heavier edge

Q14. Vu-Topper RM (1 marks)

In Bellman-Ford Algorithm, path consists of at most _________ edges.

A. V-1 Page 160

B. E+1