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

Answer: c
Explanation: In an adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.
advertisement

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

Answer: a
Explanation: Space complexity for adjacency matrix is always O(V*V) while space complexity for adjacency list in this case would be O(V).

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

Answer: a
Explanation: The maximum edges a vertex can have is V-1.
advertisement
advertisement

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

Answer: a
Explanation: i) takes v+4e, ii) takes v+2e, iii) takes v+3e, iv) takes v +6e space.

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

Answer: c
Explanation: In an adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.
advertisement

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

Answer: c
Explanation: Vertex would have a name and a linked list attached to it.
advertisement

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

Answer: b
Explanation: In case of sparse graph most of the entries in the adjacency matrix would be 0, hence adjacency list would be preferred.
advertisement

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

Answer: a
Explanation: We can create a mapping from string to a vector, where string would be the name of the vertex and vector would contains the name of the vertices to which it is connected.

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

Answer: a
Explanation: The function win in the constant time as all the four step takes constant time.

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

Answer: b
Explanation: The time complexity for BFS is O(|V| + |E|) = O(n + n1.25) = O(n1.25).

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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter