Quiz Space

Programming, Data Structures and Algorithms using Python · Quiz 1 · 15 Mar 2026 · January 2026 term

Question 16: Let G be a connected undirected graph with n vertices re…

Question 16

+3 marksOne correct option

Let G be a connected undirected graph with n vertices represented using an adjacency matrix. In the DFS implementation given below, assume that checking whether a vertex has already been visited takes time.

What is the tightest upper bound for the worst case time complexity of DFS?

Let G be a connected undirected graph with n vertices represented using an adjacency matrix. In the DFS implementation
  1. A

    —

  2. B

    —

  3. C

    —

  4. D

    —

Show answer

Correct answer

  • C

    —

See the whole paperTake it as a mock test

Question 16 of 17 in the IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) Quiz 1 paper sat on 15 Mar 2026, in the January 2026 term (Programming, Data Structures And Algorithms Using Python 15 Mar 26). It carries 3 marks.

More questions from this paper

  1. Q1What is , given the definition of above?
  2. Q2Consider the following implementation for selection sort: Suppose a list is used as an input parameter to the above sel…
  3. Q3Suppose each node of the linked list is an object of class Node. Variable head points to the first node of the linked l…
  4. Q4Linear probing is an open addressing scheme for resolving hash collisions in tables. Linear probing takes the original …
  5. Q5A directed acyclic graph has 6 vertices. If it is guaranteed to have a unique topological sort, what is the maximum num…
  6. Q6Consider the following functions: • • • Which of the following is/are false?
  7. Q7Consider the following implementation of Merge Sort: Which of the following is/are true about Merge Sort?
  8. Q8Which of the following statements is/are true about the Quicksort algorithm? Assume that the first element of the list …
  9. Q9Consider a singly linked list implemented using the above class. Assume that: • variable points to the first node of th…
  10. Q10Which of the following is/are possible degree sequence(s) of the vertices of a connected undirected graph with five ver…
  11. Q11Which of the following statement(s) is/are true about Breadth First Search (BFS) in an unweighted graph ?
  12. Q12You are given a non-empty list of integers sorted in ascending order. Every element in the list appears exactly twice, …
  13. Q13You are implementing binary search on a sorted list L that may contain duplicate values. You need to find the index of …
  14. Q14Let be a stack and be a queue supporting the following operations: Assume that supports the standard stack operations a…
  15. Q15For a connected undirected graph with 7 vertices, which of the following gives the correct minimum and maximum possible…
  16. Q17Select the most appropriate data structure for the following operations: