Final Practice

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

Consider a binary tree T in which every node has either zero or two children. Let n be the number of nodes in T. Which one of the following is the number of nodes in T that have exactly two children?

Select all that apply to the following tree:

• Binary search tree

• Full complete binary tree

• Heap

• Proper binary tree

• Complete binary tree

What is the most accurate time complexity in the worst case scenario in terms of big-O notation for searching for an entry in a multi-way search tree with n nodes.

• O(logn)

• O(n)

• O(nlogn)

• O(1)

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:

A. Unsorted doubly linked list.

B. Sorted doubly linked list

C. Min-heap implemented using an array.

Which one of the following options gives the worst-case time complexities for the meld operation on two instances of combined size n for each of these data structures?

• A. O(1)

  B. O(n)

  C. O(n)

• A. O(1)

  B. O(n^2)

  C. O(nlogn)

• A. O(n)

  B. O(n^2)

  C. O(n)

• A. O(1)

  B. O(n)

  C. O(nlogn)

Draw the resulting (2,4) tree after removing 2 (since you can't actually draw here, simply draw your solution on scratch paper, type anything here, then check your solution with the correct answer).

Evaluate responses using AI:

OFF

Answer explanation

This is one of two possible solutions. The other solution looks similar except the node with 4 in it has 3 and the node with 1 3 in it has 1 and the node with 5 in it has 4 5

Write the code for the mergeSort(S) algorithm which takes an vector S of integers and returns a sorted vector Q. Assume the merge(S₁, S₂, S) method (which takes two sorted vectors S₁ and S₂ and returns a merged sorted vector S) is already implemented and you can just use it.

Evaluate responses using AI:

OFF

Answer explanation

Vector mergeSort(S) {

if (S.size() <= 1) return S;

Vector S1, S2;

Vector::Iterator p = S.begin();

for (int i = 0; i < S.size()/2; i++)

S1.insertBack(*p++);

for (int i = n/2; i < n; i++)

S2.insertBack(*p++);

mergeSort(S1);

mergeSort(S2);

merge(S1, S2, S);

return S;

}