Data Structure Questions and Answers – Adjacency List

Uncategorized

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

1. 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

Explanation: A name and a connected list will be assigned to each vertex.

2. 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

Explanation: Since most of the entries in the adjacency matrix in a sparse graph are 0, the adjacency list is favoured.

3. To create an adjacency list C++’s map container can be used.
A) True
B) False

Explanation: We may map a string to a vector, where string is the name of the vertex and vector is the name of the vertices to which it is associated.

4. 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)

Explanation: The feature wins in constant time because all four steps take the same amount of time.

5. 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)

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

6. 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)

Explanation: Any vertex in an adjacency list has a linked list with the values of the edges to which it is associated.

7. For some sparse graph an adjacency list is more space efficient against an adjacency matrix.
A) True
B) False

Explanation: The space complexity of an adjacency matrix is always O(V*V), while the space complexity of an adjacency list will be O in this case (V).

8. 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)

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

9. 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

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

10. 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)

Explanation: Any vertex in an adjacency list has a linked list with the values of the edges to which it is associated.

A finite graph is represented by an adjacency list, which is a set of unordered lists. The set of neighbours of a particular vertex in the graph is defined by each unordered list within an adjacency list. This is one of the graph representations that are widely used in computer programmes. Guido van Rossum proposes using a hash table to connect each vertice in a graph with an array of adjacent vertices. A vertex can be represented by any hashable object in this representation. Edges are not explicitly represented as objects.

Leave a Reply

Your email address will not be published. Required fields are marked *