1
GATE CSE 2023
MCQ (Single Correct Answer)
+2
-0.67

Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation EXTRACT-MAX(A) extracts and deletes the maximum element from A. The operation INSERT(A, key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.

When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?

A
Both EXTRACT-MAX(A) and INSERT(A, key) run in $$O(1)$$.
B
Both EXTRACT-MAX(A) and INSERT(A, key) run in $$O(\log(n))$$.
C
EXTRACT-MAX(A) runs in $$O(1)$$ whereas INSERT(A, key) runs in $$O(n)$$.
D
EXTRACT-MAX(A) runs in $$O(1)$$ whereas INSERT(A, key) runs in $$O(\log(n))$$.
2
GATE CSE 2023
MCQ (Single Correct Answer)
+2
-0.67

Consider the C function foo and the binary tree shown.

GATE CSE 2023 Data Structures - Trees Question 10 English
typedef struct node {
    int val;
    struct node *left, *right;
} node;
int foo(node *p) {
    int retval;
    if (p == NULL)
        return 0;
    else {
        retval = p->val + foo(p->left) + foo(p->right);
        printf("%d ", retval);
        return retval;
    }
}

When foo is called with a pointer to the root node of the given binary tree, what will it print?

A
3 8 5 13 11 10
B
3 5 8 10 11 13
C
3 8 16 13 24 50
D
3 16 8 50 24 13
3
GATE CSE 2020
Numerical
+2
-0
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
Your input ____
4
GATE CSE 2020
MCQ (Single Correct Answer)
+2
-0.67
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the number of reported elements is k.
A
$$\Theta \left( {\log n} \right)$$
B
$$\Theta \left( {\log n + k} \right)$$
C
$$\Theta \left( {k\log n} \right)$$
D
$$\Theta \left( {n\log k} \right)$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP