Scribd
Upload
169 views3 pages

DSA Third Unit MCQ

The document contains 11 multiple choice questions about graph theory concepts like adjacency matrices, minimum spanning trees, Prim's algorithm, and Kruskal's algorithm. Prim's algorithm is a greedy algorithm that constructs a minimum spanning tree by selecting edges in increasing order of weight. It initializes with a vertex and never accepts cycles. Kruskal's algorithm finds the minimum spanning tree and runs in O(E log V) time. The weight of the minimum spanning tree for the given graph using Kruskal's algorithm is 15.

Uploaded by

Mayuri Dilip Kulkarni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
169 views3 pages

DSA Third Unit MCQ

The document contains 11 multiple choice questions about graph theory concepts like adjacency matrices, minimum spanning trees, Prim's algorithm, and Kruskal's algorithm. Prim's algorithm is a greedy algorithm that constructs a minimum spanning tree by selecting edges in increasing order of weight. It initializes with a vertex and never accepts cycles. Kruskal's algorithm finds the minimum spanning tree and runs in O(E log V) time. The weight of the minimum spanning tree for the given graph using Kruskal's algorithm is 15.

Uploaded by

Mayuri Dilip Kulkarni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

1.

The number of elements in the adjacency matrix of a graph having 7 vertices is


__________
a) 7
b) 14
c) 36
d) 49
2. What would be the number of zeros in the adjacency matrix of the given graph?

a) 10
b) 6
c) 16
d) 0
3. What is the maximum number of possible non zero values in an adjacency
matrix of a simple graph with n vertices?
a) (n*(n-1))/2
b) (n*(n+1))/2
c) n*(n-1)
d) n*(n+1)
4. Which of these adjacency matrices represents a simple graph?
a) [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ]
b) [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]
c) [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ]
d) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]
5. Space complexity for an adjacency list of an undirected graph having large
values of V (vertices) and E (edges) is
a) O(E)
b) O(V*V)
c) O(E+V)
d) O(V)
6. Which of the following is true?
a) Prim’s algorithm initialises with a vertex
b) Prim’s algorithm initialises with a edge
c) Prim’s algorithm initialises with a vertex which has smallest edge
d) Prim’s algorithm initialises with a forest
7. Consider the given graph.

What is the weight of the minimum spanning tree using the Prim’s algorithm,
starting from vertex a?
a) 23
b) 28
c) 27
d) 11

8. Prim’s algorithm is a ______


a) Divide and conquer algorithm
b) Greedy algorithm
c) Dynamic Programming
d) Approximation algorithm
9. Which of the following is false about Prim’s algorithm?
a) It is a greedy algorithm
b) It constructs MST by selecting edges in increasing order of their weights
c) It never accepts cycles in the MST
d) It can be implemented using the Fibonacci heap
10. Kruskal’s algorithm is used to ______
a) find minimum spanning tree
b) find single source shortest path
c) find all pair shortest path algorithm
d) traverse the graph
11. Consider the given graph.
What is the weight of the minimum spanning tree using the Kruskal’s algorithm?
a) 24
b) 23
c) 15
d) 19
12. What is the time complexity of Kruskal’s algorithm?
a) O(log V)
b) O(E log V)
c) O(E2)
d) O(V log E)

You might also like