How are shortest path algorithms tested in GATE Data Structure?

GATE tests Dijkstra's algorithm (non-negative weights), Bellman-Ford (negative weights), and Floyd-Warshall (all pairs). Questions focus on time complexity, correctness conditions, and step-by-step execution.

What is topological sort and when is it asked in GATE CS?

Topological sort orders vertices of a DAG such that all directed edges go from earlier to later vertices. GATE tests its existence conditions, DFS-based implementation, and application in scheduling problems.

What is amortized analysis in Data Structures for GATE?

Amortized analysis averages the time per operation over a sequence of operations. GATE tests aggregate, accounting, and potential methods for dynamic arrays, splay trees, and binomial heaps.

How should I prepare Data Structures for GATE CS exam?

Focus on trees (BST, AVL, heap, B+), graphs (BFS, DFS, MST, shortest path), hashing, and linked lists. Practice all previous year questions on ExamPrev with video solutions and aim for conceptual clarity over rote learning.

CS/IT Gate Subject

Aptitude and Reasoning
Engineering Mathematics
C Programming
Data Structure
Design Algorithm Analysis
Operating System
Computer Network
Digital Logic Design
Compiler Design
Database Management System
Theory of Computation

Data Structure GATE previous year questions with answer

1 2 3 4 5 6

Ques 66 Gate 2015 Set-1

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

63 and 6, respectively

64 and 5, respectively

32 and 6, respectively

31 and 5, respectively

(Tree ) is the correct answer.

PROCESSED

Ques 67 Gate 2015 Set-1

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Θ(logn) for both insertion and deletion

Θ(n) for both insertion and deletion

Θ(n) for insertion and Θ(logn) for deletion

Θ(logn) for insertion and Θ(n) for deletion

(Binary Search Tree) is the correct answer.

PROCESSED

Ques 68 Gate 2015 Set-1

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9, 18, 20, 25

I and IV only

II and III only

II and IV only

II only

(Tree Traversal) is the correct answer.

PROCESSED

Ques 69 Gate 2014 Set-1

Consider a rooted Binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having having exactly 4 nodes O(n^a Logn^b). Then the value of a + 10b is ________

(a) is the correct answer.

Ques 70 Gate 2014 Set-1

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G?
Assume that the graph is represented using adjacency matrix.

θ (n)

θ (n+m)

θ(n²)

θ(m²)

(Graph Theory) is the correct answer.

The question asks for the tightest upper bound for Depth First Search (DFS) when the graph is represented using an adjacency matrix.
Analyze the Options:
A) θ(n): DFS visits all n vertices, but with an adjacency matrix, we must check all possible vertices in each row. Therefore, θ(n) is not sufficient.
B) θ(n + m): This is the typical DFS complexity when an adjacency list is used. It is not the complexity for an adjacency matrix.
C) θ(n²): In an adjacency matrix, each vertex has a row containing n entries. DFS may need to examine all n entries for each of the n vertices. Therefore, the total running time is θ(n × n) = θ(n²).
Example: If a graph has 5 vertices, the adjacency matrix has 5 × 5 = 25 entries. DFS may need to check all 25 entries to determine which vertices are connected.
D) θ(m²): The running time of DFS with an adjacency matrix depends on the number of vertices, not the square of the number of edges.
Correct Answer: C) θ(n²)

Ques 71 Gate 2014 Set-1

Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?

G₁ = (V,E₁) where E₁={(u,v)∣(u,v)∉E}

G₂ = (V,E₂) where E₂={(u,v)∣(v,u)∈E}

G₃ = (V,E₃) where E₃={(u,v)∣ there is a path of length ≤2 from u to v in E}

G₄= (V₄,E) where V₄ is the set of vertices in G which are not isolated

(a) is the correct answer.

Definition of Strongly Connected Component:
A strongly connected component (SCC) of a directed graph is a maximal set of vertices such that every vertex is reachable from every other vertex in the set.

Option A: G₁ is the complement of G.
The edges of G are removed and new edges are introduced, which can change the reachability between vertices. Therefore, the SCCs may change.

Option B: G₂ is the transpose of G, where every edge (u,v) in G becomes (v,u).
If there is a path from u to v in G, reversing all its edges gives a path from v to u in G₂. Thus, if u and v are mutually reachable in G, they are also mutually reachable in G₂, and vice versa.
Therefore, G and its transpose have exactly the same SCCs.

Option C: G₃ adds edges for paths of length 2. Adding such shortcut edges does not change reachability, because every new edge already corresponds to a path in G. Hence, C also preserves the SCCs.

Option D: G₄ removes isolated vertices. An isolated vertex itself forms an SCC, so removing it changes the set of SCCs.

Conclusion:
The standard and intended answer is:

Answer: (B) G₂ = (V,E₂) where E₂ = {(u,v) | (v,u) ∈ E}

1 2 3 4 5 6

Total Unique Visitors

Loading......

CS/IT Gate Subject

Data Structure GATE previous year questions with answer

Question Options

Sign in to ExamPrev