Data Structure Questions and Answers – Adjacency List

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Adjacency List”.

1. 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)
View Answer

2. For some sparse graph an adjacency list is more space efficient against an adjacency matrix.
a) True
b) False
View Answer

3. Time complexity to find if there is an edge between 2 particular vertices is _________
a) O(V)
b) O(E)
c) O(1)
d) O(V+E)
View Answer

4. For the given conditions, which of the following is in the correct order of increasing space requirement?
i) Undirected, no weight
ii) Directed, no weight
iii) Directed, weighted
iv) Undirected, weighted
a) ii iii i iv
b) i iii ii iv
c) iv iii i ii
d) i ii iii iv
View Answer

5. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________
a) O(V)
b) O(E*E)
c) O(E)
d) O(E+V)
View Answer

6. Complete the given snippet of code for the adjacency list representation of a weighted directed graph.

	class neighbor
        {
		int vertex, weight;
		____ next;
	}
 
	class vertex
        {
		string name;
		_____ adjlist;
	}
 
	vertex adjlists[101];

a) vertex, vertex
b) neighbor, vertex
c) neighbor, neighbor
d) vertex, neighbor
View Answer

7. In which case adjacency list is preferred in front of an adjacency matrix?
a) Dense graph
b) Sparse graph
c) Adjacency list is always preferred
d) Complete graph
View Answer

8. To create an adjacency list C++’s map container can be used.
a) True
b) False
View Answer

9. What would be the time complexity of the following function which adds an edge between two vertices i and j, with some weight ‘weigh’ to the graph having V vertices?

vector<int> adjacent[15] ;
vector<int> weight[15]; 
 
void addEdge(int i,int j,int weigh) 
{	 
	adjacent[a].push_back(i); 
	adjacent[b].push_back(j); 
	weight[a].push_back(weigh); 
	weight[b].push_back(weigh); 
}

a) O(1)
b) O(V)
c) O(V*V)
d) O(log V)
View Answer

10. What would be the time complexity of the BFS traversal of a graph with n vertices and n^1.25 edges?
a) O(n)
b) O(n^1.25)
c) O(n^2.25)
d) O(n*n)
View Answer

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.