List of top Data Science and Artificial Intelligence Questions on Data Structures and Algorithms asked in GATE DA

Consider that the quick sort algorithm is used to sort an array of \(n\) distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray.
Let \(T(n)\) denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray.
Which of the following recurrence relations correctly represents \(T(n)\) in this scenario?
You are given the following Pre-order and In-order traversals of a Binary Tree \(T\) with nodes E, F, G, P, Q, R, S.

Pre-order: P Q S E R F G
In-order: S Q E P F R G

Which of the following statements is/are true about the Binary Tree \(T\)?
Let \(A\) be a sorted array containing 1000 distinct integers. You perform a recursive binary search on \(A\) to find an element \(y\). Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than \(y\).

The maximum number of comparisons that may have to be performed if \(y\) is not an element of \(A\) is __________. (Answer in integer)
Consider a directed graph \(G = (V, E)\), where \(V\) is the finite set of vertices and \(E\) is the set of directed edges between the vertices. \(G\) may contain cycles but there is no self-loop. Further, \(G\) may not be strongly connected.
Let \(G^R\) be the graph obtained by reversing the directions of all the edges in \(G\) without changing the set of vertices.
Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex \(v\) of a graph visits only the reachable vertices from \(v\) in that graph.
Which of the following statements must always be true, regardless of the structure of \(G\)?
Consider the problem of sorting the given array in ascending order:

\(P = [1, 2, 3, 5, 4]\)

Consider two sorting algorithms Bubble Sort (BS) and Insertion Sort (IS).

Let \(N_1\) be the total number of comparisons done by BS on the elements of \(P\) and \(N_2\) be the total number of comparisons done by IS on the elements of \(P\).

Which of the following options is/are correct?