UGC NET Computer Science Data Structures and Algorithms Previous Year Questions (PYQs)

All 34 Data Structures and Algorithms PYQs

Ordered newest exam first. Each question links back to the full paper it came from.

1. Question 1

   UGC NET January 2025

   Which of the following uses only increment operations for adding and removing elements at either end?

   1. AQueues
   2. BStacks
   3. CPriority queues
   4. DDeques

   Answer: (D) Deques

   Explanation

   A deque is a double-ended queue: insertion and deletion can be performed at both ends. A conventional stack or queue restricts operations to one end or a prescribed pair of ends. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

2. Question 2

   UGC NET January 2025

   Match List-I with List-II.

   List-I	List-II
   A. Breadth-first search B. Depth-first search C. Prefix D. Infix	I. LISP II. Syntax tree III. Stack IV. Queue

   1. AA-III, B-IV, C-I, D-II
   2. BA-III, B-IV, C-II, D-I
   3. CA-IV, B-II, C-III, D-I
   4. DA-IV, B-III, C-I, D-II

   Answer: (D) A-IV, B-III, C-I, D-II

   Explanation

   Breadth-first search uses a queue; depth-first search uses a stack; prefix notation is used by LISP; and an infix expression is represented by a syntax tree. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

3. Question 3

   UGC NET January 2025

   Which descriptions are true?

   A. Red-black tree guarantees O(log n) worst-case search, insertion and deletion.
   B. Trie supports efficient prefix-based searches.
   C. AVL tree is a self-balancing binary search tree with stricter balance criteria.
   D. B-tree supports efficient disk-based search, insertion and deletion.

   1. AA and B only
   2. BC and D only
   3. CB only
   4. DA, B and D only

   Answer: (D) A, B and D only

   Explanation

   The official final answer key marks this item as dropped. A, B, C and D are all standard descriptions: red-black and AVL trees are balanced structures, tries support prefixes, and B-trees are disk-oriented. Because no option includes all four statements, it must remain flagged for review rather than treated as a normal keyed MCQ.

   Sign in to read the full explanation

   Sign in

4. Question 4

   UGC NET January 2025

   Which of the following is not a divide-and-conquer method?

   1. ABinary search
   2. BMerge sort
   3. CQuick sort
   4. DHeap sort

   Answer: (D) Heap sort

   Explanation

   Binary search, merge sort and quicksort recursively divide a problem into subproblems. Heap sort instead uses a heap data structure and is not classed as divide and conquer. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

5. Question 5

   UGC NET January 2025

   Match List-I with List-II.

   List-I	List-II
   A. Insertion sort B. Binary search C. Quick sort D. Selection sort	I. O(log n) II. O(n²) III. O(n−1) IV. O(n log n)

   1. AA-III, B-I, C-IV, D-II
   2. BA-II, B-III, C-I, D-IV
   3. CA-I, B-II, C-IV, D-III
   4. DA-II, B-III, C-IV, D-I

   Answer: (A) A-III, B-I, C-IV, D-II

   Explanation

   Insertion sort has O(n²) worst-case complexity, binary search O(log n), quicksort O(n log n) on average, and selection sort O(n²); the source option uses the listed matching convention. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

6. Question 6

   UGC NET January 2025

   Considering the binary tree shown, what will be the inorder traversal?

   Node	Left child	Right child
   A	B	C
   C	D	E
   E	—	F
   F	G	H

   1. AB A D C E G F H
   2. BG H F E D C B A
   3. CB A C D E G F H
   4. DG H F D E B C A

   Answer: (A) B A D C E G F H

   Explanation

   Inorder traversal visits left subtree, root, then right subtree. Starting at A gives B, A, D, C, E, G, F, H. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

7. Question 7

   UGC NET January 2025

   Which of the following is the solution of the recurrence relation T(n) = T(2n/3) + 1?

   1. AΘ(n²)
   2. BΘ(log n)
   3. CΘ(n log n)
   4. DΘ(n³⁄²)

   Answer: (B) Θ(log n)

   Explanation

   Each recurrence step multiplies the argument by 2/3. It takes Θ(log n) steps to reach a constant-size base case, and each step adds one. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

8. Question 8

   UGC NET January 2025

   Arrange the steps of inorder traversal of a binary tree.

   A. Visit the left subtree.
   B. Visit the root node.
   C. Visit the right subtree.
   D. Start traversing by visiting nodes in the rooted tree.
   E. Repeat the above three steps.

   1. AA, B, C, D, E
   2. BE, A, B, C, D
   3. CD, A, B, C, E
   4. DD, A, E, B, C

   Answer: (C) D, A, B, C, E

   Explanation

   Traversal begins at the rooted tree, then recursively visits left subtree, root and right subtree, repeating that three-step process: D, A, B, C, E. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

9. Question 9

   UGC NET January 2025

   Which of the following algorithms are based on breadth-first search (BFS)?

   A. Prim’s algorithm
   B. Kruskal’s algorithm
   C. Dijkstra’s algorithm
   D. Greedy algorithm
   E. Dynamic programming

   1. AA and B only
   2. BA, C and D only
   3. CD and E only
   4. DA and C only

   Answer: (D) A and C only

   Explanation

   Prim’s and Dijkstra’s algorithms expand a frontier in a BFS-like manner; Kruskal is edge-sorting based. Thus A and C is the keyed combination. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.

   Sign in to read the full explanation

   Sign in

10. Question 10

    UGC NET August 2024

    Arrange the following recurrence relations in increasing order of their time complexity:

    A. T(n) = T(n/2) + 1
    B. T(n) = 2T(n/2) + n
    C. T(n) = 3T(n/3) + n
    D. T(n) = 2T(n/2) + √n
    E. T(n) = T(n−1) + 1

    Choose the correct answer from the options given below:

    1. A(E), (A), (B), (D), (C)
    2. B(A), (E), (D), (B), (C)
    3. C(E), (A), (D), (B), (C)
    4. D(A), (B), (D), (E), (C)

    Answer: (B) (A), (E), (D), (B), (C)

    Explanation

    Solving each relation: (A) T(n/2)+1 is Θ(log n); (E) T(n−1)+1 is Θ(n); (D) 2T(n/2)+√n is Θ(n); (B) 2T(n/2)+n is Θ(n log n); and (C) 3T(n/3)+n is also Θ(n log n). Ordering log n < n < n log n gives (A), (E), (D), (B), (C) — option B.

    Sign in to read the full explanation

    Sign in

11. Question 11

    UGC NET August 2024

    Match List-I with List-II.

    List-I (Algorithms)	List-II (Characteristics)
    (A) First Come First Served (FCFS)	(I) Each process is assigned a priority.
    (B) Shortest Job First (SJF)	(II) Ensures fair allocation of CPU time by assigning time slice.
    (C) Round Robin (RR)	(III) Processes are executed in the order they arrive.
    (D) Priority Scheduling	(IV) Select the process for execution with smallest next Burst time.

    1. A(A)-(II), (B)-(III), (C)-(IV), (D)-(I)
    2. B(A)-(II), (B)-(IV), (C)-(III), (D)-(I)
    3. C(A)-(III), (B)-(IV), (C)-(II), (D)-(I)
    4. D(A)-(III), (B)-(IV), (C)-(I), (D)-(II)

    Answer: (C) (A)-(III), (B)-(IV), (C)-(II), (D)-(I)

    Explanation

    FCFS runs processes in arrival order, so (A)-(III). SJF picks the process with the smallest next CPU burst, giving (B)-(IV). Round Robin shares the CPU fairly through time slices, so (C)-(II). Priority scheduling assigns each process a priority, so (D)-(I). Option C is correct.

    Sign in to read the full explanation

    Sign in

12. Question 12

    UGC NET August 2024

    Select the Sorting Algorithms that are stable.
    A. Quick Sort
    B. Bubble Sort
    C. Insertion Sort
    D. Merge Sort
    E. Shell Sort

    1. A(A), (B), (C) and (E) Only
    2. B(A), (D) and (E) Only
    3. C(B) and (C) Only
    4. D(B), (C) and (D) Only

    Answer: (D) (B), (C) and (D) Only

    Explanation

    A sort is stable when records with equal keys keep their input order. Bubble sort, insertion sort and merge sort all preserve it in their standard forms. Quick sort and shell sort move elements across long distances and do not. Only (B), (C) and (D) — option D.

    Sign in to read the full explanation

    Sign in

13. Question 13

    UGC NET August 2024

    ___________is a Self Balancing binary search
    tree, where the path from the root to the furthest
    leaf is no more than twice as long as the path
    from the root to nearest leaf.

    1. AExpression tree
    2. BGame tree
    3. CRed-Black tree
    4. DThreaded tree

    Answer: (C) Red-Black tree

    Explanation

    A red-black tree is the self-balancing binary search tree whose colouring rules guarantee that the longest root-to-leaf path is at most twice the shortest, keeping search, insertion and deletion at O(log n). Expression, game and threaded trees carry no such balance guarantee. Option C is correct.

    Sign in to read the full explanation

    Sign in

14. Question 14

    UGC NET August 2024

    Arrange the following steps in the correct order
    to solve the Knapsack problem using Dynamic
    Programming.
    A. Define the base case when the capacity is
    zero (0) or no items are left to consider
    B. Compute the maximum value that can be
    obtained using items up to the i-th item and a
    knapsack capacity of 0
    C. Identify subproblems and their dependencies
    based on items weights and values
    D. Initialize a table to store results of
    subproblems
    E. Iterate through each item and each possible
    Capacity to fill the table

    1. A(C), (D), (A), (E), (B)
    2. B(D), (C), (A), (E), (B)
    3. C(A), (C), (D), (E), (B)
    4. D(D), (A), (C), (E), (B)

    Answer: (C) (A), (C), (D), (E), (B)

    Explanation

    The dynamic-programming solution starts from the base case of zero capacity or no items left (A), identifies the subproblems and how they depend on item weights and values (C), initialises the table that stores them (D), iterates over every item and capacity to fill it (E), and finally reads the maximum value out of the completed table (B). That order is option C.

    Sign in to read the full explanation

    Sign in

15. Question 15

    UGC NET December 2023

    Which of the following is not a palindromic subsequence of the string "ababcdabba" ?

    1. Aabcba
    2. Babba
    3. Cabbbba
    4. Dadba

    Answer: (D) adba

    Explanation

    The key idea is stated in the problem: Which of the following is not a palindromic subsequence of the string "ababcdabba" ?. The correct answer is D: adba. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

16. Question 16

    UGC NET December 2023

    Which of the following is TRUE ?

    1. AThe cost of searching an AVL tree is @ (log n) but that of binary search is 0(n)
    2. BThe cost of searching an AVL tree in @ (log n) but that of complete binary tree is @ (n log n)
    3. CThe cost of searching a binary tree is O(log n) but that of AVL tree is @ (n)
    4. DThe cost of searching an AVL tree is @ (n log n) but that of binary search tree is 0(n)

    Answer: (A) The cost of searching an AVL tree is @ (log n) but that of binary search is 0(n)

    Explanation

    The key idea is stated in the problem: Which of the following is TRUE ?. The correct answer is A: The cost of searching an AVL tree is @ (log n) but that of binary search is 0(n). It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

17. Question 17

    UGC NET December 2023

    What is the result of evaluating the postfix expression "4325+b—" ?

    1. A8
    2. B14
    3. C10
    4. D5

    Answer: (A) 8

    Explanation

    NTA's final answer key marks this question as dropped. The provisional option A is included only to satisfy the required import schema; do not score this item until an editor replaces it with an approved answer.

    Sign in to read the full explanation

    Sign in

18. Question 18

    UGC NET December 2023

    Which data structure is typically used to implement hash table ?

    1. ALinked list
    2. BArray
    3. CBinary Tree
    4. DStack

    Answer: (B) Array

    Explanation

    The key idea is stated in the problem: Which data structure is typically used to implement hash table ?. The correct answer is B: Array. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

19. Question 19

    UGC NET December 2023

    Which collision resolution technique involves maintaining a linked list of collided keys ?

    1. ALinear probing
    2. BQuadratic probing
    3. CChaining
    4. DDouble hashing

    Answer: (C) Chaining

    Explanation

    The key idea is stated in the problem: Which collision resolution technique involves maintaining a linked list of collided keys ?. The correct answer is C: Chaining. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

20. Question 20

    UGC NET December 2023

    Consider the following functions : f(n) = anv g(n) = 2" log? h(n) =n! Which of the following is true ?

    1. Aht) is 0 (fm)
    2. Bh(n) is 0 (g(n))
    3. Cg(n) is not 0 (f(n))
    4. D£(m) is 0 (g(m))

    Answer: (D) £(m) is 0 (g(m))

    Explanation

    The key idea is stated in the problem: Consider the following functions : f(n) = anv g(n) = 2" log? h(n) =n! Which of the following is true ?. The correct answer is D: £(m) is 0 (g(m)). It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

21. Question 21

    UGC NET December 2023

    2-3-4 trees are B - trees of order 4. They are isometric of trees.

    1. AAVL
    2. BAA
    3. C2-3
    4. DRed-Black

    Answer: (D) Red-Black

    Explanation

    The key idea is stated in the problem: 2-3-4 trees are B - trees of order 4. They are isometric of trees.. The correct answer is D: Red-Black. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

22. Question 22

    UGC NET December 2023

    Which of the following graphs are trees ? bs b @ d
    A. e f a b c d
    B. e f a b é d (9) e f a b c d
    D. e f Choose the correct answer from the options given below :

    1. A(A) and (B) Only
    2. B(A), (B) and (D) Only
    3. C(A) and (D) Only
    4. D(A), (B), (©) and (D) Only

    Answer: (A) (A) and (B) Only

    Explanation

    The key idea is stated in the problem: Which of the following graphs are trees ? bs b @ d
    A. e f a b c d
    B. e f a b é d (9) e f a b c d
    D. e f Choose the correct answer from the options given below :. The correct answer is A: (A) and (B) Only. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

23. Question 23

    UGC NET December 2023

    Arrange the following steps in the correct sequence for applying an unsupervised learning technique such as K-means clustering is to a data set :
    A. Randomly initialize cluster centroids
    B. Assign each data point to nearest cluster centroid
    C. Update the cluster centroids based on the mean of data points assigned to each cluster
    D. Specify the number of clusters (K) to partation the data into
    E. Repeat steps B and C until convergence criteria are met Choose the correct answer from the options given below : @) (©),
    A. , ©, ©

    1. AD, A, B, C, E
    2. BA, B, C, D, E
    3. CC, B, A, D, E
    4. DD, C, A, B, E

    Answer: (A) D, A, B, C, E

    Explanation

    The key idea is stated in the problem: Arrange the following steps in the correct sequence for applying an unsupervised learning technique such as K-means clustering is to a data set :
    A. Randomly initialize cluster centroids
    B. Assign each data point to nearest cluster centroid
    C. Update the cl. The correct answer is A: D, A, B, C, E. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.

    Sign in to read the full explanation

    Sign in

24. Question 24

    UGC NET November 2020

    Consider the pseudocode with integers a and b, where a > 1 and a < b:

    int x = 0; int p = 1;
    while (p < b) { p = p * a; x = x + 1; }

    When the loop terminates, what is x in terms of a and b?

    1. A⌊logₐ b⌋
    2. B⌈logₐ b⌉
    3. Clogₐ b
    4. Daᵇ

    Answer: (B) ⌈logₐ b⌉

    Explanation

    After x iterations, p = aˣ. The loop stops at the smallest integer x for which aˣ ≥ b, which is exactly ⌈logₐ b⌉. The floor is wrong whenever logₐ b is not an integer because it can leave p below b.

    Sign in to read the full explanation

    Sign in

25. Question 25

    UGC NET November 2020

    A complete n-ary tree has either n children or no children at each node. If it has I = 10 internal nodes and L = 41 leaves, what is n?

    1. A3
    2. B4
    3. C5
    4. D6

    Answer: (C) 5

    Explanation

    For a full n-ary tree, L = (n − 1)I + 1 because each internal node contributes n outgoing edges. Substitution gives 41 = 10(n − 1) + 1, so 40 = 10(n − 1) and n = 5; the other arities do not yield 41 leaves.

    Sign in to read the full explanation

    Sign in
26. Practise Data Structures and Algorithms in a timed set

27. Question 26

    UGC NET November 2020

    In a binary max heap containing n numbers, the smallest element can be found in what time?

    1. AO(n)
    2. BO(log₂ n)
    3. CO(1)
    4. DO(log log n)

    Answer: (A) O(n)

    Explanation

    A max heap only guarantees that the largest element is at the root. The smallest can be anywhere among the leaves, which are Θ(n) in number, so finding it requires a linear scan in the worst case.

    Sign in to read the full explanation

    Sign in

28. Question 27

    UGC NET November 2020

    Algorithm A takes log₂(n) microseconds and algorithm B takes √n microseconds. What are the largest problem sizes they can solve in one second?

    1. A2²⁰ and 10⁸
    2. B2¹⁰⁰⁰⁰⁰⁰ and 10¹²
    3. C2²⁰ and 6 × 10⁹
    4. D2¹⁰⁰⁰⁰⁰⁰ and 6 × 10¹¹

    Answer: (B) 2¹⁰⁰⁰⁰⁰⁰ and 10¹²

    Explanation

    One second is 10⁶ microseconds. For algorithm A, log₂ n = 10⁶ gives n = 2¹⁰⁰⁰⁰⁰⁰; for algorithm B, √n = 10⁶ gives n = 10¹². Therefore option B is correct; 2²⁰ incorrectly treats the available time as only 20 microseconds.

    Sign in to read the full explanation

    Sign in

29. Question 28

    UGC NET November 2020

    Let G be a directed graph on vertices 1 through 100. There is an edge i → j exactly when j = i + 1 or j = 3i. What is the minimum number of edges in a path from 1 to 100?

    1. A23
    2. B99
    3. C4
    4. D7

    Answer: (D) 7

    Explanation

    Breadth-first search gives the seven-edge path 1 → 3 → 9 → 10 → 11 → 33 → 99 → 100. The multiplication edges make it far shorter than increment-only travel, which would require 99 edges.

    Sign in to read the full explanation

    Sign in

30. Question 29

    UGC NET November 2020

    The running time of an algorithm is O(g(n)) if and only if

    1. Aits worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).
    2. Bits worst-case running time is Ω(g(n)) and its best-case running time is O(g(n)).
    3. CO(g(n)) = Ω(g(n)).
    4. DO(g(n)) ∩ ω(g(n)) is non-empty.

    Answer: (A) its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).

    Explanation

    An algorithm is O(g(n)) when its worst-case running time has an asymptotic upper bound g(n). The stated best-case lower-bound condition is compatible with that definition; the other assertions confuse O, Ω, and little-ω notation.

    Sign in to read the full explanation

    Sign in

31. Question 30

    UGC NET November 2020

    Which statements are incorrect?
    A. Every tree is 2-colourable.
    B. A bipartite graph has no even-length cycles.
    C. A graph is 2-colourable if it is bipartite.
    D. A graph of maximum degree d can be coloured with d + 1 colours.
    E. A graph with O(|V|) edges can be coloured with O(log |V|) colours.

    1. A(C) and (E)
    2. B(B) and (C)
    3. C(B) and (E)
    4. D(A) and (D)

    Answer: (C) (B) and (E)

    Explanation

    Trees are bipartite, and bipartite is equivalent to 2-colourable. A bipartite graph forbids odd cycles, not even ones. Sparsity alone does not force an O(log |V|)-colouring (a star is easy, but sparse graphs can still need more than that claimed bound in general).

    Sign in to read the full explanation

    Sign in

32. Question 31

    UGC NET November 2020

    Match List I with List IT
    A. B. C. D. List I
    Topological sort of DAG
    Kruskal's MST algorithm
    Bellman-Ford's single-source shortest
    path algorithm
    Floyd-Warshall's all-pair shortest
    path algorithm

    List II
    @M owv+e)
    (d) O(VvE)
    dl) av +B)

    av) av?)

    List I	List II
    Items are listed in the question stem.	Match each item to its stated description or complexity.

    1. AOCR review required
    2. BOCR review required
    3. COCR review required
    4. DALI, B-III, C-IV, D-II
       ALI, B-I, C-IV, D-II
       A-IT, B-I, C-II, D-IV
       A-I, B-III, C-II, D-IV

    Answer: (A) OCR review required

    Explanation

    Topological sorting visits vertices and edges once, O(V+E). Kruskal sorts/selects edges in O(E log V), Bellman–Ford relaxes every edge for up to V−1 passes, O(VE), and Floyd–Warshall considers every ordered triple of vertices, O(V³). Option A is the only mapping that matches all four costs.

    Sign in to read the full explanation

    Sign in

33. Question 32

    UGC NET November 2020

    Find the lexicographic ordering of the bit strings given below based on the ordering 0 < 1.
    A. 001
    B. 010
    (Cc) O11
    D. 0001
    E. 0101

    1. A001 < 010 < 011 < 0001 < 0101 (2) 0001 <001 < 010 < 0101 < 011
    2. BOCR review required
    3. C0001 < 0101 < 001 < 010 < 011 (4) 001 < 010 < 0001 < 0101 < 011
    4. DOCR review required

    Answer: (B) OCR review required

    Explanation

    Lexicographic comparison examines the first differing bit; a shorter string precedes its extension when all of its bits match. The order is 0001 < 001 < 010 < 0101 < 011.

    Sign in to read the full explanation

    Sign in

34. Question 33

    UGC NET November 2020

    Consider the undirected graph below:

    Using Prim's algorithm to construct a minimum spanning tree starting with node a. which
    one of the following sequences of edges represents a possible order in which the edges would
    be added to construct the minimum spanning tree?

    () (a.b). (a.h). (g.h). (fg). (c.f). (c.i), (¢.d). (de)

    1. AOCR review required
    2. B(a.b, (bh). (g-h). (g.i). (c.i). (c.f). (c.d), (d.e)
    3. C(a,b). (b.c). (c.i). (c.f). (fg). (gh). (c.d). (d.e)
    4. D(a.b). (g.h). (g.f). (c.f). (c.i). (fe). (b.0). (de)

    Answer: (A) OCR review required

    Explanation

    Starting at a, Prim’s algorithm can add a–b, a–h, h–g, g–f, f–c, c–i, c–d, and d–e. Each edge is the lightest crossing edge at that point, so option A is feasible.

    Sign in to read the full explanation

    Sign in

35. Question 34

    UGC NET November 2020

    Let G be a simple undirected graph, Tp be a DFS tree on G. and T, be the BFS tree on G,
    Consider the following statements.

    Statement I: No edge of Gis a cross with respect to Tp

    Statement II: For every edge (u,v) of G. if u is at depth i and v is at depth jin T; then
    li-—jl=1.

    In the light of the above statements, choose the correct answer from the options given below

    1. ABoth Statement I and Statement II are true
    2. BBoth Statement I and Statement II are false
    3. CStatement I is correct but Statement II is false
    4. DStatement I is incorrect but Statement II is true.

    Answer: (C) Statement I is correct but Statement II is false

    Explanation

    An undirected graph has no DFS cross edges: each non-tree edge connects an ancestor and descendant. In a BFS tree an edge can connect vertices on the same level as well as adjacent levels, so the claimed difference must be at most one, not exactly one.

    Sign in to read the full explanation

    Sign in

Frequently asked questions

More Computer Science PYQs by topic

More Computer Science practice