Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Adjacency List

1 - Question

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: In an adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.

2 - Question

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

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 - Question

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.

4 - Question

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.

5 - Question

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: In an adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.

6 - Question

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;
}

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

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

7 - Question

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: In case of sparse graph most of the entries in the adjacency matrix would be 0, hence adjacency list would be preferred.

8 - Question

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

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 - Question

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 ;
vector<int> weight;

{
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 function win in the constant time as all the four step takes constant time.

10 - Question

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)