Practice Test Geeks(GATE) Graduate Aptitude Test in Engineering Practice Test
← All GATE Flashcard Decks

Algorithms and Data Structures Flashcards

7 cards from real GATE practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.

Read the first 7 Algorithms and Data Structures flashcards as text

  1. What is the amortized time complexity of a single push or pop operation on a dynamic array that doubles in size when full?

    Answer: O(1)

    Doubling doubles the capacity but the total copying cost over all insertions sums to O(n), so by the aggregate method each operation costs O(1) amortized.

  2. In an AVL tree, what is the maximum number of rotations required to restore the AVL balance property after a single insertion?

    Answer: 1

    After insertion, only the deepest unbalanced ancestor needs a single or double rotation; once fixed, all ancestors above it automatically regain balance.

  3. What is the amortized time complexity per operation of Union-Find with both path compression and union by rank?

    Answer: O(α(n))

    With path compression and union by rank, the amortized cost per operation is O(α(n)), the inverse Ackermann function, which is less than 5 for any input encountered in practice.

  4. In a hash table using chaining with n keys stored in m slots under simple uniform hashing, the expected time for a successful search is:

    Answer: O(1 + n/m)

    The expected chain length is the load factor α = n/m, so a successful search costs O(1) for hashing plus O(1 + α) = O(1 + n/m) for traversal.

  5. What is the time complexity of building a binary max-heap from an unsorted array of n elements using the linear-time build-heap procedure?

    Answer: O(n)

    Build-heap calls sift-down on n/2 internal nodes; since most are near the leaves, the total work sums to O(n) by the geometric series argument.

  6. Which of the following problems can be solved in polynomial time and is therefore in class P (not NP-complete)?

    Answer: Minimum Spanning Tree

    Minimum Spanning Tree is solvable in polynomial time by Kruskal's or Prim's algorithm, whereas 3-SAT, Hamiltonian Cycle, and Vertex Cover are all NP-complete.

  7. What is the space complexity of Depth-First Search (DFS) on a graph with V vertices and E edges?

    Answer: O(V)

    DFS maintains a recursion stack (or explicit stack) whose depth is at most V in the worst case (e.g., a path graph), so the space complexity is O(V), not O(V + E).