Quiz Space

Programming, Data Structures and Algorithms using Python · End Term · 21 Dec 2025 · September 2025 term

Question 21: In the Floyd–Warshall algorithm, which of the following …

Question 21

+4 marksOne or more correct options

In the Floyd–Warshall algorithm, which of the following are true?

Select all that apply.

  1. A

    It uses dynamic programming.

  2. B

    It can detect negative cycles.

  3. C

    It maintains a predecessor matrix for path reconstruction (when implemented with one).

  4. D

    It cannot be applied to undirected graphs.

Show answer

Correct answers

  • A

    It uses dynamic programming.

  • B

    It can detect negative cycles.

  • C

    It maintains a predecessor matrix for path reconstruction (when implemented with one).

See the whole paperTake it as a mock test

Question 21 of 50 in the IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) End Term paper sat on 21 Dec 2025, in the September 2025 term (Programming, Data Structures And Algorithms Using Python 18 Dec 25). It carries 4 marks.

More questions from this paper

  1. Q1Here is a function to return the count of odd numbers in the list. There is a logical error in this function. Select th…
  2. Q2Here is a function to return the count of even numbers in the list. There is a logical error in this function. Select t…
  3. Q3Match the correct asymptotic complexity for each function.
  4. Q4Match the correct asymptotic complexity for each function.
  5. Q5Consider the below function for selection sort algorithm. Assume that the list L=[25, 17, 20, 10, 15] is passed to the …
  6. Q6Consider the below function for selection sort algorithm. Assume that the list L=[15, 12, 18, 13, 11] is passed to the …
  7. Q7Which of the following scenarios is an example where linear search is more practical or efficient than the binary searc…
  8. Q8Which of the following scenarios is an example where linear search is more practical or efficient than binary search?
  9. Q9Consider the following class Node: Consider an implementation of a linked list where each node is created using the giv…
  10. Q10Suppose we are sorting a list of eight integers using quicksort, and we have just finished the first partitioning. The …
  11. Q11If you have an empty stack and you perform the following sequence of operations: What is the value of the top element o…
  12. Q12Consider the following class Node: Consider an implementation of a linked list where each node is created using the giv…
  13. Q13A directed graph G has 7 vertices. What is the maximum number of edges in G?
  14. Q14If you have an empty stack and you perform the following sequence of operations: What is the value of the top element o…
  15. Q15Consider the following DAG. How many valid topological sorts exist?
  16. Q16There are 8 systems (0,..,7) connected in network as shown in the figure given below. Which edge should we add to the n…
  17. Q17There are 7 systems (0,..,6) connected in a network as shown in the figure given below. Which of the following system (…
  18. Q18Consider the following DAG. How many valid topological sorts exist?
  19. Q19Consider a directed graph given below:\ Vertices: {0,1,2,3}\ Edge weights: (0, 1) = 1 (0, 2) = 4 (1, 2) = 2 (1, 3) = 6 …
  20. Q20Figure question
  21. Q22Consider the following graph. What is the shortest distance from node 0 to node 5?
  22. Q23Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 2, 5, 7, 9, 12, 14. The maximum p…
  23. Q24Suppose we run the Bellman-Ford algorithm on a graph with non-negative edges. Then compared to Dijkstra's algorithm, th…
  24. Q25Consider a binary tree with 21 nodes, where the number of nodes with two children is 9. The number of nodes with one ch…
  25. Q26Figure question
  26. Q27Consider the following max-heap. Which of the following cannot be the last element inserted into the heap?
  27. Q28Consider a binary tree with 15 nodes, where the number of nodes with two children is 6. The number of nodes with one ch…
  28. Q29If we perform the following operations in the given order on the min-heap [12, 25, 18, 40, 35, 30, 28, 50, 45] then the…
  29. Q30If we perform the following operations in the given order on the max-heap [89, 62, 31, 45, 51, 29, 30, 42, 34] then the…
  30. Q31What is the maximum number of nodes in an AVL tree of height 9? Consider that the height of the empty tree is 0.
  31. Q32What is the minimum number of nodes in an AVL tree of height 7? Consider that the height of the empty tree is 0.
  32. Q33Figure question
  33. Q34Figure question
  34. Q35For which of the following coin denominations does the Greedy strategy of choosing the largest coin that does not excee…
  35. Q36For which of the following coin denominations does the Greedy strategy of choosing the largest coin that does not excee…
  36. Q37In a list L, two elements L[i] and L[j] form an inversion if L[i] > L[j] and i \< j . The total number of inversions fo…
  37. Q38In a list L, two elements L[i] and L[j] form a significant inversion if L[i] > 2 L[j] and i \< j . The total number of …
  38. Q39Figure question
  39. Q40Figure question
  40. Q41Consider the following function MoM. What median value will be returned by the given MoM function for the following lis…
  41. Q42Consider the following function MoM.
  42. Q43Consider the function mystery() that takes strings X and Y as input. What will mystery('ABCDFGH','ACDFHBG') return? LCS…
  43. Q44Consider the function mystery() that takes strings X and Y as input. What will mystery('XYITCRT','WTXITRY') return? LCS…
  44. Q45Consider the following grid.
  45. Q46Consider the following grid.
  46. Q47Figure question
  47. Q48Figure question
  48. Q49Figure question
  49. Q50Figure question