In a directaddress table or hash table satellite data is ext

In a direct-address table or hash table, “satellite data” is extra data that is stored along with the key. For example, in the video, “Joe” and “Jill” would be satellite data, where 385 and 741 would be the keys. A bit vector is an array of bits (0s and 1s). A bit vector of length m takes much less space than an array of m pointers. Describe how to use a bit vector to represent a dynamic set of distinct elements with no satellite data. Dictionary operations Insert, Delete, and Search should run in O(1) time.

Solution

Ans: According to prompt we need an extra stack, which is used to store pointers to elements in a large array, while the elements of the large array are the subscripts of the corresponding stack.

When inserted into an array we initialize the address of the array and initialize the elements of the large array into the corresponding top pointer.

When performing a lookup operation, we first look up the value in array by direct addressing and then determine whether the array element is a valid index of the stack. If it is legal then the search is successful otherwise the dictionary has no elements and returns NULL.

When the delete operation is performed, the void is created in the stack after the element is deleted. We can fill the void created by stacking the top of the stack and its corresponding large array, and then execute the stack.