GATE CSE 2009 | Searching and Sorting Question 19 | Algorithms

PREVIOUS NEXT

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

$$\left\{25,12,16,13,10,8,14\right\}$$

$$\left\{25,14,13,16,10,8,12\right\}$$

$$\left\{25,14,16,13,10,8,12\right\}$$

$$\left\{25,14,12,13,10,8,16\right\}$$

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