Data Structure
Q151.
Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if the keys 661, 182, 24 and 103 are inserted in that order?Q152.
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is\begin{array}{|l|l|} \hline 0 & \text { S7 } \\ \hline 1 & \text { S1 } \\ \hline 2 & \\ \hline 3 & \text { S4 } \\ \hline 4 & \text { S2 } \\ \hline 5 & \text { } \\ \hline 6 & \text { S5 } \\ \hline 7 & \\ \hline 8 & \text { S6 } \\ \hline 9 & \text { S3 } \\ \hline \end{array}Q153.
An advantage of chained hash table (external hashing) over the open addressing scheme isQ154.
Consider the following statements: I. The smallest element in a max-heap is always at a leaf node. II. The second largest element in a max-heap is always a child of the root node. III. A max-heap can be constructed from a binary search tree in \Theta (n) time. IV. A binary search tree can be constructed from a max-heap in \Theta (n) time. Which of the above statements is/are TRUE?Q155.
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 ___________.Q156.
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations. When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?Q157.
Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap?Q158.
Given a binary-max heap. The elements are stored in an arrays as 25,14,16,13,10,8,12. What is the content of the array after two delete operations?Q159.
Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?Q160.
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node.Assume that the heap is implemented in an array and i refers to the i-th index of thearray.If the heap tree has depth d (number of edges on the path from the root to the farthest leaf),the n what is the time complexity to re-fix the heap efficiently after the removal of the element?