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).

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.

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;

}