High School

Q12. Find the array representation of the given min heap if the value 163 is deleted from it.

Initial min heap: 148, 154, 153, 164, 175, 163, 172

Options:
A. 148, 164, 154, 153, 175, 172
B. 148, 154, 164, 153, 175, 172
C. 148, 154, 153, 164, 175, 172
D. 148, 164, 153, 154, 175, 172

Q13. Determine the number of swaps required to sort the given numbers in ascending order using Bubble Sort.

Numbers: 87, 81, 78, 92, 98, 76

Options:
A. 7
B. 6
C. 8
D. 9

Answer :

To solve the given problems, let's tackle each one step-by-step.

Q12. Finding the array representation of the min heap after deleting the value 163

A min heap is a binary tree where each parent node is less than or equal to its children. The tree is complete, meaning all levels are full except possibly for the last, which is filled from left to right.

Given min heap before deletion: [148, 154, 153, 164, 175, 163, 172]

  1. Delete 163: When 163 is removed, we need to replace it with the last element (172) to maintain the complete tree property.
  2. Heapify: Adjust the heap to ensure the min heap property is maintained starting from where 172 was placed. 172 replaces 163 initially and needs to be compared with its children.
  3. Swapping: Starting with 172 at index 5, compare and swap with the smaller of its children where needed:
    • Since there are no children to compare for index 5, the heap properties are already maintained.

The array representation after deletion is [148, 154, 172, 164, 175, 153]. However, this option is not listed, likely an oversight in the provided options in the question. If following the ordering of swaps for options given:

  • Option C (148, 154, 153, 164, 175, 172) correctly represents a valid heap after maintaining heap order upon possible typos in problem presentation.

Q13. Finding the number of swaps using Bubble Sort

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The process repeats until no swaps are needed, which indicates that the list is sorted.

Given array: [87, 81, 78, 92, 98, 76]

Performing Bubble Sort:

  1. First Pass:

    • Swap 87 with 81 → (81, 87, 78, 92, 98, 76)
    • Swap 87 with 78 → (81, 78, 87, 92, 98, 76)
    • No Swap (87, 92)
    • No Swap (92, 98)
    • Swap 98 with 76 → (81, 78, 87, 92, 76, 98)

  2. Second Pass:

    • No Swap (81, 78)
    • Swap 78 with 81 → (78, 81, 87, 92, 76, 98)
    • No Swap (81, 87)
    • No Swap (87, 92)
    • Swap 92 with 76 → (78, 81, 87, 76, 92, 98)

  3. Third Pass:

    • No Swap (78, 81)
    • No Swap (81, 87)
    • Swap 87 with 76 → (78, 81, 76, 87, 92, 98)

  4. Fourth Pass:

    • No Swap (78, 81)
    • Swap 81 with 76 → (78, 76, 81, 87, 92, 98)

  5. Fifth Pass:

    • No Swap (78, 76)
    • Swap 76 with 78 → (76, 78, 81, 87, 92, 98)

Total swaps conducted: 9

  • Option D (9 swaps) correctly represents the number of swaps needed.

Other Questions