GATE CSE 2009 | Searching and Sorting Question 22 | Algorithms

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

Consider a binary max-heap implemented using an array. What is the content of the array {25, 14, 16, 13, 10, 8, 12} after two delete operations?

{14, 13, 12, 10, 8}

{14, 12, 13, 8, 10}

{14, 13, 8, 12, 10}

{14, 13, 12, 8 10}

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

$$\Theta(\log n)$$

$$\Theta(n)$$

$$\Theta(n\log n)$$

$$\Theta(n^2)$$

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

$$\Theta(\log_2n)$$

$$\Theta(\log_2\log_2n)$$

$$\Theta(n)$$

$$\Theta(n\log_2n)$$

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Given two arrays of numbers a₁,......,a_n and b₁,......, b_n where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that a_i+a_i+1......a_j = b_i+b_i+1......b_j or report that there is not such span,

Takes O(3ⁿ) and $$\Omega(2^{n})$$ time if hashing is permitted

Takes O(n³) and $$\Omega(n^{2.5})$$ time in the key comparison model

Takes θ(n) time and space

Takes $$O(\sqrt n)$$ time only if the sum of the 2n elements is an even number

PREVIOUS NEXT