ELEVATE SKILLS!
Enquiry FormRSSBRPSCUniversity of RajasthanRTU KotaCareers@SA
ELEVATE SKILLS!

CS Free MCQ Bank

Access a comprehensive computer science MCQ bank for free, featuring hundreds of questions with detailed solutions. Strengthen concepts, practice effectively, and prepare confidently for exams, quizzes, and competitive tests.

  • Home
  • CS MCQs
  • DSA
  • Suraku Academy | DSA - Graphs Solved MCQs & PYQs Bank

Q: 1 If a graph has 31 edges and each vertex of the graph has degree atleast 3, then maximum number of possible vertices in the graph is

  1. 19

  2. 20

  3. 21

  4. 22

[ Option B ]

We use the Handshaking Theorem, which states that the sum of the degrees of all vertices in an undirected graph equals twice the number of edges:
Sum of degrees of all vertices=2×Number of edges
Here, E=31. So,
Sum of degrees = Sum of degrees=2×31=62
The given condition is that each vertex has degree at least 3. Now, let the number of vertices be n. Then, Sum of degrees ≥ 3n. We already know the exact sum is 62, so, 3n ≤ 62.
Finally solve for n, n ≤ 62/3 = 20.66. Since the number of vertices must be an integer, the maximum possible number of vertices is 20.

Q: 2 Consider an undirected un-weighted graph G. Let a breadth first traversal of G be done starting from a node r. let d(r,u) and d(r,v) be the length of the shortest path from r to u and v respectively in G. if u is visited before v during the breadth first traversal, which of the following statement is correct?

  1. D(r,u) < d(r,v)

  2. D (r,u) > d(r,v)

  3. D(r,u) <=d(r,v)

  4. None of the above

[ Option C ]

Q: 3 A simple graph has

  1. Both parallel edges and self-loops

  2. Self-loops but not parallel edge

  3. Parallel edges but no self-loop

  4. Neither parallel edge nor self-loop

[ Option D ]

A Simple Graph is a type of graph that does not contain any parallel edges (multiple edges) or self-loops (an edge from a vertex to itself). Each edge in a simple graph connects two distinct vertices, and there can be at most one edge between any pair of vertices.

Q: 4 Which of the following is true for adjacency matrix representation of a graph with n vertices?

  1. Space complexity is O(n)

  2. Can not be used for directed graph

  3. Space complexity is O(n2)

  4. Can not be used for weighted graphs

[ Option C ]

In an adjacency matrix, we represent a graph using a two-dimensional array of size n×n, where n is the number of vertices. Each row and column correspond to a vertex, and the value stored in a cell tells us whether an edge exists between two vertices.

If the graph is weighted, the cell stores the weight instead of just 0 or 1. Since the matrix always needs space for n2 entries, the space complexity is O(n2). This representation can be used for directed or undirected graphs as well as weighted or unweighted graphs.

The only drawback is that it uses more memory for sparse graphs, but it provides quick access to check if an edge exists between two vertices.

Q: 5 Which of the following is not true about a complete graph with n vertices?

  1. Each vertex has degree n-1

  2. It contains no cycle

  3. It is connected

  4. It has n(n-1)/2 edges

[ Option B ]

In graph theory, a Complete Graph is a simple graph in which every pair of distinct vertices is connected by an edge.

  • A complete graph is highly connected and contains cycles.
  • Every vertex is connected to all other n−1 vertices, so its degree is n−1.
  • The total number of edges in a simple complete graph is given by (n(n−1))/2.

Q: 6 Which of the following is NOT a graph traversal algorithm?

  1. Greedy

  2. Divide and Conquer

  3. Dynamic Programming

  4. None of the above

[ Option D ]

Graph traversal algorithms are specifically methods used to visit all nodes of a graph, such as:

  • DFS (Depth First Search) Using Stack.
  • BFS (Breadth First Search) Using Queue.

Q: 7 Study the following statements:
Statements: 
I-  A cycle is an open walk with no repeated vertex.
II-  A circuit is a closed walk with no repeated edge.
Which of the following is correct?

  1. Only Statement I is true.

  2. Only Statement II is true.

  3. Both Statement I and II are true.

  4. Neither Statement I nor II is true.

[ Option B ]

A Walk in a graph is a sequence of vertices and edges where each edge connects the previous vertex to the next one. It can repeat vertices or edges, there is no restriction.

  • Open Walk, a walk is said to be open if it starts and ends at different vertices.
  • Closed Walk, a walk is closed if it starts and ends at the same vertex.

In graph theory, a Cycle is a closed walk, meaning it starts and ends at the same vertex, and no other vertices or edges are repeated except the first and last vertex being the same.
A Circuit is indeed a closed walk (starts and ends at the same vertex) where no edge is repeated. Vertices may repeat, but edges do not.

Thank You for Reading!

Thank you so much for taking the time to read my Computer Science MCQs section carefully. Your support and interest mean a lot, and I truly appreciate you being part of this journey. Stay connected for more insights and updates! If you'd like to explore more tutorials and insights, check out my YouTube channel.

Don’t forget to subscribe and stay connected for future updates.