Heaps

⏱️

15 questions · 23 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.

Q1NAT1 markIndex

In a 1-based heap, the parent of index 45 is:

Numerical answer: ________

Q2MCQ1 markShape

Which of these is always a max-heap?

• (A) any BST stored level by level
• (B) an array sorted in decreasing order
• (C) any complete binary tree
• (D) an array sorted in increasing order

Q3NAT1 markLeaves

How many leaves does a heap of 50 keys have?

Numerical answer: ________

Q4MCQ2 marksValidity

Which is a max-heap?

• (A) 25 14 12 13 10 8 16
• (B) 25 14 16 13 10 8 12
• (C) 25 12 16 13 10 8 14
• (D) 25 14 13 16 10 8 12

Q5MCQ2 marksInsert

Insert 95 into 100 80 90 50 60 70 40 30 20. The resulting array is:

• (A) 100 95 90 50 60 70 40 30 20 80
• (B) 100 95 90 50 80 70 40 30 20 60
• (C) 100 80 90 50 95 70 40 30 20 60
• (D) 100 90 95 50 60 70 40 30 20 80

Q6NAT2 marksDelete

Delete the maximum from 100 80 90 50 60 70 40 30 20. Which key ends at index 5?

Numerical answer: ________

Q7NAT1 markComparisons

Maximum comparisons for one insertion into a heap of 1000 keys?

Numerical answer: ________

Q8MCQ2 marksOutput

What is the last line printed?

int h[20], n = 0;                       /* max-heap in h[0..n-1] */

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void insert(int x)                       /* sift-up */
{
    int i = n++;
    h[i] = x;
    while (i > 0 && h[(i - 1) / 2] < h[i]) {
        swap(&h[i], &h[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

void siftDown(int i)
{
    int l, r, big;
    for (;;) {
        l = 2 * i + 1;
        r = l + 1;
        big = i;
        if (l < n && h[l] > h[big]) big = l;
        if (r < n && h[r] > h[big]) big = r;
        if (big == i) return;
        swap(&h[i], &h[big]);
        i = big;
    }
}

int deleteMax(void)
{
    int top = h[0];
    h[0] = h[--n];                       /* last element to the root */
    siftDown(0);
    return top;
}

void show(void) { int i; for (i = 0; i < n; i++) printf("%d ", h[i]); printf("\n"); }

int main(void)
{
    int a[] = {40, 80, 35, 90, 45, 50, 70}, i;
    for (i = 0; i < 7; i++) insert(a[i]);
    show();
    printf("removed %d\n", deleteMax());
    show();
    return 0;
}

• (A) 80 50 70 40 45 35
• (B) 80 45 70 40 50 35
• (C) 90 80 70 40 45 35 50
• (D) 80 70 50 40 45 35

Q9MCQ1 markBuild

The cost of bottom-up build-heap on n keys is:

• (A) Θ(n log n)
• (B) Θ(n²)
• (C) Θ(n)
• (D) Θ(log n)

Q10NAT2 marksBuild

Bottom-up build-max-heap on 40 80 35 90 45 50 70. What key is at index 3?

Numerical answer: ________

Q11MSQ1 markHeap sort

Which are true of heap sort on n keys?

• (A) in place
• (B) uses build-heap first
• (C) Θ(n log n) worst case
• (D) stable

Q12NAT2 marksCount

Number of distinct max-heaps on 7 distinct keys?

Numerical answer: ________

Q13NAT2 marksTernary

In a 0-based 4-ary heap, what are the indices of the children of index 2? Give the first child’s index.

Numerical answer: ________

Q14MCQ1 markMinimum

Finding the minimum key in a max-heap of n keys takes:

• (A) Θ(1)
• (B) Θ(n)
• (C) Θ(n log n)
• (D) Θ(log n)

Q15MCQ2 marksMerge

Two max-heaps of n keys each are merged into one heap. Best time?

• (A) O(n)
• (B) O(n log n)
• (C) O(n²)
• (D) O(log n)

90 80 70 40 45 35 50 
removed 90
80 50 70 40 45 35