資料結構與演算法

(10 points) Consider a hash function $h$ that maps numerous keys into an array $A$, indexed from 0 to $n-1$. The concern is that excessive collisions arising from the hashed keys can potentially cause inefficiency within the hash table. The following pseudocode, while not complete, implements a function that utilizes the divide-and-conquer strategy to identify the case where strictly more than half of the keys share the same hash value. The function takes the hash function $h$ and the subarray $A$ with the index range from $low$ to $high$ as input and returns the majority hash value shared by over $\lfloor (high - low + 1)/2 \rfloor$ keys. If the keys stored in the subarray $A[low..high]$ do not have such a majority hash value, the function returns $-1$.

1: function FindMajorityHashValue(h, A, low, high)
2:     if low = high then return h(A[low]) end if
3:     mid ← ⌊(low + high)/2⌋
4:     leftMajority  ← FindMajorityHashValue(h, A, low, mid)
5:     rightMajority ← FindMajorityHashValue(h, A, mid + 1, high)
6:     leftCount  ← CountElement(A, low, high, leftMajority)
7:     rightCount ← CountElement(A, low, high, rightMajority)
8:     [ ... ]
9: end function

In the pseudocode, $\text{CountElement}(A, low, high, val)$ calculates and returns the count of keys in the subarray $A[low..high]$ whose hashed values are equal to the given $val$. Please select the correct description(s) below.