GRAPHS

Question 1:

What is a graph in data structures?

a) A linear data structure

b) A hierarchical data structure
c) A non-linear data structure
d) A sequential data structure

Answer: c) A non-linear data structure

Question 2:

Which of the following is not a type of graph?

a) Directed graph
b) Undirected graph
c) Cyclic graph
d) Weighted graph

Answer: c) Cyclic graph

Question 3:

In a directed graph, an edge from vertex A to vertex B means:

a) There is a one-way connection from A to B

b) There is a one-way connection from B to A
c) There is a two-way connection between A and B
d) There is no connection between A and B
Answer: a) There is a one-way connection from A to

Question 4:

What is the degree of a vertex in an undirected graph?

a) The number of edges connected to the vertex

b) The sum of weights of edges connected to the vertex
c) The distance from the vertex to the farthest vertex in the graph
d) The number of vertices connected to the vertex

Answer: a) The number of edges connected to the vertex

Question 5:

Which of the following algorithms is used for traversing a graph in a systematic way?

a) Dijkstra's algorithm
b) Breadth-first search (BFS)
c) Depth-first search (DFS)
d) Prim's algorithm

Answer: b) Breadth-first search (BFS)

Question 6:

What is the time complexity of depth-first search (DFS) in a graph with V vertices and E edges?

a) O(V)
b) O(E)
c) O(V + E)
d) O(log V)

Answer: c) O(V + E)

Question 7:

Which of the following is used to detect cycles in a graph?

a) Dijkstra's algorithm
b) Topological sort
c) Kruskal's algorithm
d) Cycle detection algorithm

Answer: d) Cycle detection algorithm

Question 8:

What is the purpose of Kruskal's algorithm in graph theory?

a) Shortest path finding

b) Minimum spanning tree
c) Maximum flow problem
d) Topological sorting

Answer: b) Minimum spanning tree

Question 9:

What is the Bellman-Ford algorithm used for in graph theory?

a) Shortest path finding

b) Minimum spanning tree
c) Maximum flow problem
d) Topological sorting

Answer: a) Shortest path finding

Question 10:

Which data structure is typically used to implement a priority queue in Dijkstra's algorithm?

a) Stack
b) Queue
c) Binary heap
d) Linked list

Answer: c) Binary heap

Question 11:

What is the adjacency matrix used for in graph representation?

a) To represent directed edges

b) To store information about connected vertices
c) To calculate the degree of a vertex
d) To perform topological sorting

Answer: b) To store information about connected vertices

Question 12:

Which of the following is not a standard graph traversal algorithm?

a) Dijkstra's algorithm
b) Bellman-Ford algorithm
c) Kruskal's algorithm
d) Prim's algorithm

Answer: a) Dijkstra's algorithm

Question 13:

What is the maximum number of edges in a complete graph with n vertices?

a) n
b) n(n-1)/2
c) 2n
d) 2^(n-1)

Answer: b) n(n-1)/2

Question 14:

In graph terminology, what is a cut vertex?

a) A vertex with the highest degree

b) A vertex whose removal increases the number of connected components
c) A vertex with the lowest degree
d) A vertex connected to all other vertices

Answer: b) A vertex whose removal increases the number of connected components

Question 15:

Which of the following is a popular algorithm for finding strongly connected components in a directed graph?

a) Dijkstra's algorithm
b) Kosaraju's algorithm
c) Floyd-Warshall algorithm
d) Johnson's algorithm

Answer: b) Kosaraju's algorithm

Question 16:

What is the primary purpose of Floyd-Warshall algorithm in graph theory?

a) Shortest path finding

b) Minimum spanning tree
c) All pairs shortest paths
d) Topological sorting

Answer: c) All pairs shortest paths

Question 17:

Which data structure is commonly used to implement depth-first search (DFS) in graph traversal?

a) Stack
b) Queue
c) Linked list
d) Priority queue

Answer: a) Stack

Quetion 18:

What is the time complexity of finding the shortest path using Bellman-Ford algorithm in a graph with V vertices and E edges?

a) O(V)
b) O(E)
c) O(V + E)
d) O(V * E)

Answer: c) O(V + E)

Question 19:

In a weighted graph, what does the weight of an edge represent?

a) The length of the edge

b) The cost of traversing the edge
c) The number of vertices connected by the edge
d) The priority of the edge

Answer: b) The cost of traversing the edge

Question 20:

Which of the following statements is true about an acyclic graph?

a) It has no vertices
b) It has no edges
c) It has no cycles
d) It has no weights

Answer: c) It has no cycles

Question 21:

What is the in-degree of a vertex in a directed graph?

a) The number of edges connected to the vertex

b) The sum of weights of edges connected to the vertex
c) The number of vertices connected to the vertex
d) The number of edges pointing towards the vertex

Answer: d) The number of edges pointing towards the vertex

Question 22:

Which algorithm is suitable for finding the shortest path in a graph with positive edge weights?

a) Dijkstra's algorithm
b) Bellman-Ford algorithm
c) Prim's algorithm
d) Kruskal's algorithm

Answer: a) Dijkstra's algorithm

Question 23:

What is the minimum number of edges required to create a connected graph with n vertices?

a) n-1
b) n
c) n+1
d) 2n

Answer: a) n-1

Question 24:

In a topological sort of a directed acyclic graph (DAG), which vertex has no incoming edges?

a) Source vertex
b) Sink vertex
c) Cut vertex
d) Articulation point

Answer: a) Source vertex

Question 25:

Which of the following is a greedy algorithm used for finding the minimum spanning tree of a graph?

a) Dijkstra's algorithm
b) Bellman-Ford algorithm
c) Kruskal's algorithm
d) Floyd-Warshall algorithm

Answer: c) Kruskal's algorithm

Question 26:

What is the purpose of Johnson's algorithm in graph theory?

a) Shortest path finding

b) Minimum spanning tree
c) All pairs shortest paths
d) Topological sorting

Answer: c) All pairs shortest paths

Question 27:

Which of the following is an application of graph algorithms?

a) Sorting elements in an array

b) Searching for an element in a linked list
c) Finding the shortest route on a map
d) Storing data in a database

Answer: c) Finding the shortest route on a map

Question 28:

What does the term "bipartite graph" mean in graph theory?

a) A graph with two vertices

b) A graph with two edges
c) A graph with two connected components
d) A graph whose vertices can be divided into two disjoint sets

Answer: d) A graph whose vertices can be divided into two disjoint sets

Question 29:

Which of the following statements is true about Eulerian graphs?

a) They have no cycles

b) They have exactly one cycle
c) They have exactly two cycles
d) They have a cycle that visits every edge exactly once

Answer: d) They have a cycle that visits every edge exactly once

Question 30:

What is the time complexity of Kruskal's algorithm for finding the minimum spanning tree in a graph with V vertices and E
edges?

a) O(V)
b) O(E)
c) O(V log V)
d) O(E log E)

Answer: d) O(E log E)

Breadth-First Search (BFS) MCQs:

1. What data structure is typically used in BFS for keeping track of visited vertices?
a) Stack
b) Queue
c) Array
d) Linked List
Answer: b) Queue
2. In BFS, which vertex is visited first?
a) The one with the highest degree
b) The one with the lowest degree
c) The one that was visited last
d) The one that was discovered first
 Answer: d) The one that was discovered first
3. What is the time complexity of BFS in an adjacency matrix representation with V vertices and E edges?
a) O(V)
b) O(E)
c) O(V + E)
d) O(log V)
Answer: c) O(V + E)
4. In BFS, which of the following data structures is used for queuing vertices?
a) Stack
b) Queue
c) Priority Queue
d) List
Answer: b) Queue
5. BFS can be used to find the shortest path in an unweighted graph between two vertices.
a) True
b) False
Answer: a) True

Depth-First Search (DFS) MCQs:

6. In DFS, which data structure is typically used for keeping track of visited vertices?
a) Stack
b) Queue
c) Array
d) Linked List
Answer: a) Stack
7. In DFS, which vertex is visited first?
a) The one with the highest degree
b) The one with the lowest degree
c) The one that was visited last
d) The one that was discovered first
Answer: d) The one that was discovered first
8. What is the time complexity of DFS in an adjacency list representation with V vertices and E edges?
a) O(V)
b) O(E)
c) O(V + E)
d) O(log V)
Answer: a) O(V)
9. In DFS, which of the following data structures is used for maintaining the order of vertices?
a) Stack
b) Queue
c) Priority Queue
d) List
Answer: a) Stack
10. DFS is always guaranteed to find the shortest path between two vertices in a graph.
a) True
b) False
Answer: b) False
11. In DFS, what does it mean if a vertex is marked as "gray" during the traversal?
a) The vertex is yet to be discovered.
b) The vertex has been visited but not fully processed.
c) The vertex has been fully processed.
d) The vertex is not reachable from the starting vertex.
Answer: b) The vertex has been visited but not fully processed.
12. DFS can be used to detect cycles in a graph.
a) True
b) False
Answer: a) True
Dijkstra ALGORITHM
Question 1: What is Dijkstra's algorithm used for? a) Sorting arrays b) Finding the shortest paths in a graph c) Searching in a linked list
d) Sorting linked lists

Answer: b) Finding the shortest paths in a graph

Question 2: Which type of graph does Dijkstra's algorithm work on? a) Directed acyclic graph b) Undirected graph c) Weighted graph
with non-negative edge weights d) Bipartite graph

Answer: c) Weighted graph with non-negative edge weights

Question 3: What is the main goal of Dijkstra's algorithm? a) Finding the longest path in a graph b) Finding the minimum spanning tree
c) Finding the most connected vertex d) Finding the shortest paths from a source vertex to all other vertices

Answer: d) Finding the shortest paths from a source vertex to all other vertices

Question 4: In Dijkstra's algorithm, how are the shortest distances initialized? a) All distances set to 1 b) The source distance set to 0,
others to ∞ c) Randomly assigned distances d) All distances set to ∞

Answer: b) The source distance set to 0, others to ∞

Question 5: Which data structure is commonly used to implement the priority queue in Dijkstra's algorithm? a) Stack b) Queue c) Min-
heap d) Linked list

Answer: c) Min-heap

Question 6: What happens if a shorter path to a vertex is discovered in Dijkstra's algorithm? a) The longer path is retained b) The
shorter path is ignored c) The shorter path is updated d) The algorithm terminates

Answer: c) The shorter path is updated

Question 7: In Dijkstra's algorithm, what does the term "greedy" refer to? a) The algorithm makes locally optimal choices at each step
b) The algorithm considers all possible paths before choosing c) The algorithm only considers the longest paths d) The algorithm
randomly selects paths

Answer: a) The algorithm makes locally optimal choices at each step

Question 8: What is the time complexity of Dijkstra's algorithm in the worst case? a) O(V) b) O(E) c) O(V + E) d) O(V log V)

Answer: c) O(V + E)

Question 9: What type of graphs can Dijkstra's algorithm handle efficiently? a) Directed graphs with cycles b) Undirected graphs with
negative weights c) Weighted graphs with negative weights d) Directed acyclic graphs

Answer: d) Directed acyclic graphs

Question 10: What does Dijkstra's algorithm guarantee about the paths it finds? a) Longest paths b) Random paths c) Shortest paths d)
Paths with negative weights

Answer: c) Shortest paths

Question 11: In Dijkstra's algorithm, what is the purpose of the predecessor array (p[v])? a) To store the vertex colors b) To store the
shortest distances c) To reconstruct the shortest paths d) To store the weights of edges

Answer: c) To reconstruct the shortest paths

Question 12: What happens if a graph in Dijkstra's algorithm contains negative edge weights? a) The algorithm works correctly b) The
algorithm may produce incorrect results c) The algorithm terminates early d) The algorithm gives an error

Answer: b) The algorithm may produce incorrect results

Prims algorithm
Question 1: What is Prim's algorithm used for?

a) Shortest Path
b) Minimum Spanning Tree
c) Sorting
d) Graph Traversal

Answer: b) Minimum Spanning Tree

Question 2: Prim's algorithm starts with:

a) Random node
b) Node with the highest degree
c) Node with the lowest degree
d) Node with the lowest weight

Answer: a) Random node

Question 3: Which of the following data structures is typically used to implement Prim's algorithm?

a) Stack
b) Queue
c) Priority Queue
d) Linked List

Answer: c) Priority Queue

Question 4: In Prim's algorithm, what does the term "cut" refer to?

a) Removing a vertex from the graph

b) Dividing the graph into connected components
c) Disconnecting a vertex from the spanning tree
d) Reducing the weight of an edge to zero

Answer: c) Disconnecting a vertex from the spanning tree

Question 5: What is the time complexity of Prim's algorithm using a binary heap priority queue for a graph with �V vertices and �E
edges?

a) O(V)
b) O(E)
c) O(V log V)
d) O(E log V)

Answer: d) O(E log V)

Question 6: In Prim's algorithm, how is the next edge added to the minimum spanning tree?

a) Randomly
b) By selecting the edge with the lowest weight
c) By selecting the edge with the highest weight
d) By selecting the edge with the maximum degree

Answer: b) By selecting the edge with the lowest weight

Question 7: What does the term "greedy" in Prim's algorithm refer to?

a) Always choosing the largest edge

b) Always choosing the smallest edge
c) Choosing edges randomly
d) Choosing edges based on their degrees

Answer: b) Always choosing the smallest edge

Question 8: Prim's algorithm guarantees:

a) Shortest path between two vertices
b) Maximum spanning tree
c) Minimum spanning tree
d) Eulerian path

Answer: c) Minimum spanning tree

Question 9: Which property ensures that Prim's algorithm produces a correct minimum spanning tree?

a) Triangle Inequality
b) Cut Property
c) Euler's Formula
d) De Bruijn sequence

Answer: b) Cut Property

Question 10: If a graph has V vertices, the minimum number of edges needed to form a minimum spanning tree is:

a) V
b)V−1
c) 2V−2
d) 2V

Answer: b) V−1

Question 11: Which data structure is suitable for efficiently extracting the minimum-weight edge in each iteration of Prim's algorithm?

a) Stack
b) Queue
c) Priority Queue
d) Linked List
Answer: c) Priority Queue

Question 12: In Prim's algorithm, what happens if two edges have the same minimum weight?

a) Both edges are included in the spanning tree

b) Either edge can be chosen arbitrarily
c) The algorithm terminates
d) The first edge encountered is chosen

Answer: b) Either edge can be chosen arbitrarily

Question 13: What is the main advantage of Prim's algorithm over Kruskal's algorithm?

a) Simplicity
b) Guaranteed correctness
c) Faster runtime
d) Applicability to disconnected graphs

Answer: d) Applicability to disconnected graphs

Question 14: Which step is essential in the initialization phase of Prim's algorithm?

a) Initializing all vertices with the same key value

b) Marking all vertices as visited
c) Choosing a random vertex as the starting point
d) Setting the key of the starting vertex to zero

Answer: d) Setting the key of the starting vertex to zero

Question 15: What is the significance of the "Cut Property" in Prim's algorithm?

a) It ensures the correctness of the minimum spanning tree

b) It determines the order of edge selection
c) It is irrelevant to the algorithm's behavior
d) It represents the graph's cut nodes

Answer: a) It ensures the correctness of the minimum spanning tree

Question 16: Which of the following statements is true about Prim's algorithm?

a) It is a depth-first search algorithm

b) It always produces a unique minimum spanning tree
c) It is only applicable to connected graphs
d) It requires the graph to be directed

Answer: b) It always produces a unique minimum spanning tree

Question 17: In Prim's algorithm, when does the algorithm terminate?

a) When all vertices are visited

b) When the priority queue is empty
c) When the graph contains a cycle
d) When the maximum weight edge is reached

Answer: b) When the priority queue is empty

Question 18: What is the primary goal of Prim's algorithm?

a) Maximizing the total weight of the edges

b) Minimizing the total weight of the edges
c) Ensuring a Eulerian path
d) Finding the shortest path between two vertices

Answer: b) Minimizing the total weight of the edges

Question 19: In Prim's algorithm, what does the key of a vertex represent?

a) The degree of the vertex

b) The weight of the minimum edge connecting to the tree
c) The number of neighbors of the vertex
d) The order of the vertex in the traversal

Answer: b) The weight of the minimum edge connecting to the tree

Question 20: Which scenario is a disadvantage of using Prim's algorithm?

a) The graph contains negative-weight edges

b) The graph is dense
c) The graph is fully connected
d) The graph is disconnected

Answer: d) The graph is disconnected

Kruskul Algorithm
Question 1: What is Kruskal's algorithm used for?

a) Shortest Path
b) Minimum Spanning Tree
c) Sorting
d) Graph Traversal

Answer: b) Minimum Spanning Tree

Question 2: Kruskal's algorithm starts with:

a) Random node
b) Node with the highest degree
c) Node with the lowest degree
d) Node with the lowest weight

Answer: a) Random node

Question 3: Which of the following data structures is typically used to implement Kruskal's algorithm?

a) Stack
b) Queue
c) Priority Queue
d) Disjoint Set (Union-Find)

Answer: d) Disjoint Set (Union-Find)

Question 4: In Kruskal's algorithm, what does the term "cut" refer to?

a) Removing a vertex from the graph

b) Dividing the graph into connected components
c) Disconnecting a vertex from the spanning tree
d) Reducing the weight of an edge to zero

Answer: b) Dividing the graph into connected components

Question 5: What is the time complexity of Kruskal's algorithm using a disjoint set data structure for a graph with �V vertices and �E
edges?

a) O(V)
b) O(E)
c) O(E log V)
d) O(V log V)

Answer: c) O(E log V)

Question 6: In Kruskal's algorithm, how is the next edge added to the minimum spanning tree?
a) Randomly
b) By selecting the edge with the lowest weight
c) By selecting the edge with the highest weight
d) By selecting the edge with the maximum degree

Answer: b) By selecting the edge with the lowest weight

Question 7: What does the term "greedy" in Kruskal's algorithm refer to?

a) Always choosing the largest edge

b) Always choosing the smallest edge
c) Choosing edges randomly
d) Choosing edges based on their degrees

Answer: b) Always choosing the smallest edge

Question 8: Kruskal's algorithm guarantees:

a) Shortest path between two vertices

b) Maximum spanning tree
c) Minimum spanning tree
d) Eulerian path

Answer: c) Minimum spanning tree

Question 9: Which property ensures that Kruskal's algorithm produces a correct minimum spanning tree?

a) Triangle Inequality
b) Cut Property
c) Euler's Formula
d) De Bruijn sequence

Answer: a) Triangle Inequality

Question 10: If a graph has �V vertices, the minimum number of edges needed to form a minimum spanning tree is:

a) �V
b) �−1V−1
c) 2�−22V−2
d) 2�2V

Answer: b) �−1V−1

Question 11: Which data structure is suitable for efficiently checking whether adding an edge creates a cycle in Kruskal's algorithm?

a) Stack
b) Queue
c) Priority Queue
d) Disjoint Set (Union-Find)

Answer: d) Disjoint Set (Union-Find)

Question 12: In Kruskal's algorithm, what happens if two edges have the same minimum weight?

a) Both edges are included in the spanning tree

b) Either edge can be chosen arbitrarily
c) The algorithm terminates
d) The first edge encountered is chosen

Answer: b) Either edge can be chosen arbitrarily

Question 13: What is the main advantage of Kruskal's algorithm over Prim's algorithm?

a) Simplicity
b) Guaranteed correctness
c) Faster runtime
d) Applicability to disconnected graphs
Answer: d) Applicability to disconnected graphs

Question 14: Which step is essential in the initialization phase of Kruskal's algorithm?

a) Initializing all vertices with the same key value

b) Marking all vertices as visited
c) Choosing a random vertex as the starting point
d) Creating a disjoint set for each vertex

Answer: d) Creating a disjoint set for each vertex

Question 15: What is the significance of the "Cut Property" in Kruskal's algorithm?

a) It ensures the correctness of the minimum spanning tree

b) It determines the order of edge selection
c) It is irrelevant to the algorithm's behavior
d) It represents the graph's cut nodes

Answer: a) It ensures the correctness of the minimum spanning tree

Question 16: Which of the following statements is true about Kruskal's algorithm?

a) It is a depth-first search algorithm

b) It always produces a unique minimum spanning tree
c) It is only applicable to connected graphs
d) It requires the graph to be directed

Answer: b) It always produces a unique minimum spanning tre

Question 17: In Kruskal's algorithm, when does the algorithm terminate?

a) When all vertices are visited

b) When the priority queue is empty
c) When the graph contains a cycle
d) When the maximum weight edge is reached

Answer: b) When the priority queue is empt

Question 18: What is the primary goal of Kruskal's algorithm?

a) Maximizing the total weight of the edges

b) Minimizing the total weight of the edges
c) Ensuring an Eulerian path
d) Finding the shortest path between two vertices

Answer: b) Minimizing the total weight of the edges

Question 19: In Kruskal's algorithm, what does the rank of a set represent?

a) The degree of the vertex

b) The weight of the minimum edge connecting to the tree
c) The number of neighbors of the vertex
d) The order of the vertex in the traversal

Answer: b) The weight of the minimum edge connecting to the tree

Question 20: Which scenario is a disadvantage of using Kruskal's algorithm?

a) The graph contains negative-weight edges

b) The graph is dense
c) The graph is fully connected
d) The graph is disconnected

Answer: d) The graph is disconnected

Binary Search Trees (BST):

Question 1: What is the time complexity of searching for an element in a balanced Binary Search Tree (BST)? a) O(1) b) O(log n) c) O(n)
d) O(n log n)

Answer: b) O(log n)

Question 2: In a Binary Search Tree (BST), what is the time complexity of inserting a new element? a) O(1) b) O(log n) c) O(n) d) O(n log
n)

Answer: b) O(log n)

Question 3: In a Binary Search Tree (BST), what is the time complexity of deleting a node with two children? a) O(1) b) O(log n) c) O(n)
d) O(n log n)

Answer: b) O(log n)

Question 4: What is the primary advantage of using a Self-Balancing Binary Search Tree (e.g., AVL tree) over a regular BST? a) Simplicity
b) Faster search operations c) Efficient memory usage d) Maintains balance, ensuring O(log n) height

Answer: d) Maintains balance, ensuring O(log n) height

Question 5: In a Binary Search Tree (BST), what is the maximum number of comparisons needed to search for an element? a) Height of
the tree b) Twice the height of the tree c) Logarithm of the number of nodes d) The number of nodes in the tree

Answer: a) Height of the tree

AVL Trees:

Question 6: What is the minimum height of an AVL tree with n nodes? a) log n b) n/2 c) log(n+1) - 1 d) n

Answer: a) log n
Question 7: In an AVL tree, what is the time complexity of finding the minimum element? a) O(1) b) O(log n) c) O(n) d) O(n log n)

Answer: b) O(log n)

Question 8: In AVL trees, rotations are performed to maintain: a) Maximum height b) Minimum height c) Binary search property d)
Balance property

Answer: d) Balance property

Question 9: In AVL trees, which rotation is performed to balance the tree when a left child has a right child? a) Left-Left rotation b)
Right-Right rotation c) Left-Right rotation d) Right-Left rotation

Answer: c) Left-Right rotation

Question 10: The AVL tree is named after its inventors Adelson-Velsky and Landis. a) True b) False

Answer: a) True

Complete Binary Trees:

Question 11: In a complete binary tree, the last level is filled from: a) Left to right b) Right to left c) Randomly d) Center to outward

Answer: a) Left to right

Question 12: What is the relationship between the number of nodes in the last level and the total number of nodes in a complete
binary tree? a) Half the total number b) One-third of the total number c) At least one-fourth of the total number d) Nearly half, with a
few nodes less

Answer: d) Nearly half, with a few nodes less

Question 13: In a complete binary tree, what is the index of the parent of a node at index i? a) 2i b) i/2 c) i+1 d) 2i+1

Answer: b) i/2

Question 14: The height of a complete binary tree with n nodes is: a) O(n) b) O(log n) c) O(n log n) d) O(1)

Answer: b) O(log n)

Question 15: In a complete binary tree, what is the maximum number of nodes at level k? a) 2^k b) 2^(k+1) - 1 c) k d) k^2

Answer: a) 2^k

1. Which of the following statements for a simple graph is correct?

A. Every path is a trail
B. Every trail is a path
C. Every trail is a path as well as every path is a trail
D. None of the mentioned
View Answer
Ans : A
Explanation: In a walk if the vertices are distinct it is called a path, whereas if the edges are distinct it is called a trail.

2. 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)
View Answer
Ans : C
Explanation: Out of n*n possible values for a simple graph the diagonal values will always be zero.

3. Which of the following is an advantage of adjacency list representation over adjacency matrix representation
of a graph?
A. In adjacency list representation, space is saved for sparse graphs.
B. DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in
adjacency matrix representation. Here is V and E are number of vertices and edges respectively.
C. Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
D. All of the above
View Answer
Ans : D

Explanation: No explanation.

4.A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
A. 15
B. 3
C. 1
D. 11
View Answer
Ans : B

Explanation: By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.

5.On which of the following statements does the time complexity of checking if an edge exists between two
particular vertices is not, depends?
A. Depends on the number of edges
B. Depends on the number of vertices
 C. Is independent of both the number of edges and vertices
D. It depends on both the number of edges and vertices
View Answer
Ans : C
Explanation:To check if there is an edge between to vertices i and j, it is enough to see if the value of A[i][j] is 1 or 0, here A is the
adjacency matrix.

6. The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing
order. Which of the following sequences can not be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
A. I and II
B. III and IV
C. IV only
D. II and IV
View Answer
Ans : D

Explanation: No explanation

7. What is the maximum number of edges in a bipartite graph having 10 vertices?

A. 24
B. 21
C. 25
D. 16
View Answer
Ans : C
Explanation: Let one set have n vertices another set would contain 10-n vertices.
Total number of edges would be n*(10-n), differentiating with respect to n, would yield the answer.
8. Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?
A. 3, Infinite, 4
B. 4, 3, Infinite
C. 4, Infinite, infinite
D. 4, Infinite, Infinite
View Answer
Ans : D
Explanation: MultiGraphs and PseudoGraphs may have infinite number of edges, while 4 possible simple graphs exist.

9.The most efficient algorithm for finding the number of connected components in an undirected graph on n
vertices and m edges has time complexity.
(A) \theta(n)
(B) \theta(m)
(C) \theta(m + n)
(D) \theta(mn)
A. A
B. B
C. C
D. D
View Answer
Ans : C

Explanation: Connected components can be found in O(m + n) using Tarjan's algorithm. Once we have connected components, we can
count them.

10. What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a
Directed Acyclic Word Graph, given S2 is greater than S1?
A. O(S1)
B. O(S2)
C. O(S1+S2)
D. O(1)
View Answer
Ans : A

Explanation:For each check of a word of length S1, we need to follow at most S1 edges.

11. What is the number of edges present in a complete graph having n vertices?
A. (n*(n+1))/2
B. (n*(n-1))/2
C. n
D. Information given is insufficient
View Answer
Ans : B
Explanation: Number of ways in which every vertex can be connected to each other is nC2.

12. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
A. True
B. False
View Answer
Ans : B
Explanation: The sum of the degrees of the vertices is equal to twice the number of edges.

13. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G)
is ___________
A. (n*n-n-2*m)/2
B. (n*n+n+2*m)/2
C. (n*n-n-2*m)/2
D. (n*n-n+2*m)/2
View Answer
Ans : A
Explanation: The union of G and G’ would be a complete graph so, the number of edges in G’= number of edges in the complete form of
G(nC2)-edges in G(m).
14. Which of the following properties does a simple graph not hold?
A. Must be connected
B. Must be unweighted
C. Must have no loops or multiple edges
D. All of the mentioned
View Answer
Ans : A
Explanation: A simple graph maybe connected or disconnected.

15. Which of the following is true?

A. A graph may contain no edges and many vertices
B. A graph may contain many edges and no vertices
C. A graph may contain no edges and no vertices
D. None of the mentioned
View Answer
Ans : B
Explanation: A graph must contain at least one vertex.

16. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the
following statements is true?
A. v=e
B. v = e+1
C. v + 1 = e
D. None of the mentioned
View Answer
Ans : B
Explanation: For any connected graph with no cycles the equation holds true.

17. for which of the following combinations of the degrees of vertices would the connected graph be eulerian?
A. 1,2,3
B. 2,3,4
 C. 2,4,5
D. 1,3,5
View Answer
Ans : A
Explanation: A graph is eulerian if either all of its vertices are even or if only two of its vertices are odd.

18. A graph with all vertices having equal degree is known as a __________
A. Multi Graph
B. Regular Graph
C. Simple Graph
D. Complete Graph
View Answer
Ans : B
Explanation: The given statement is the definition of regular graphs.Explanation: The given statement is the definition of regular graphs.

19. Which of the following ways can be used to represent a graph?

A. Adjacency List and Adjacency Matrix
B. Incidence Matrix
C. Adjacency List, Adjacency Matrix as well as Incidence Matrix
D. None of the mentioned
View Answer
Ans :C

Explanation: The 3 listed methods can be used, the choice depends on the ease of use.

20. The time complexity to calculate the number of edges in a graph whose information in stored in form of an
adjacency matrix is ____________
A. O(V)
B. O(E2)
C. O(E)
D. O(V2)
View Answer
Ans : D

Explanation: As V entries are 0, a total of V2-V entries are to be examined.