1. Resolving collisions by using buckets that are linked chains is called a.. se
ID: 3843204 • Letter: 1
Question
1. Resolving collisions by using buckets that are linked chains is called a.. separate chaining b, bucket chaining c. st resolution d. joint chaining 2. The most efficient approach to dealing with a gap left in an array after removing an entry from a bag is to a. replace the entry being removed with the last entry in the array and replace the last entry with null b. replace the entry being removed with the first entry in the array and replace the first entry with null c. shift subsequent entries and replace the duplicate reference to the last entry with null d. replace the entry being removed with null 3. Which of the following is an advantage of using an array to implement the ADT bag? a. adding an entry to a bag is fast b. removing a particular entry requires time to locate the entry c. increasing the size of the array requires time to copy its entries d. the client has control over the size of the bag 4. Which of these statements about binary search is true? a. Searching a sorted array is O( n). b. Searching an unsorted array is O(log n). c. Searching a sorted linked list is as efficient as searching a sorted array. d. on each pass half the remaining elements in the list are eliminated 5. The method for removing an item from the front of a queue is called dequeue b. enqueue c. get Front d. none of the above 6. Given a linked list containing the following values: first-> 5-> 10. 15 20 null, which of the following best describes what needs to happen when 10 is deleted from the list? a. The node containing 5 must be changed to point to the node which contains 15. Then the node containing 10 can be deleted.
Explanation / Answer
Answer:
1.Resolving collisions by using buckets that are linked chains is called a) separate chaining.
2.The most efficient approach to dealing with a gap left in an array after removing an entry from a bag is to a) replace the entry being removed with the last entry in the array and replace the last entry with null. [This answer is very subjective and it may vary from situation to situation. It depends upon the programming structure, requirement of the user and the number of elements you are dealing with. So, in a general sense, this approach is efficient whereas in some cases it may vary. Suppose, the number of elements in the array is small and the order of entry of the elements is very important, so in that case, shifting all the elements would not be huge in cost, then one can go for other options like shifting subsequent entries and put null to the last bag etc…]
3.An advantage of using an array to implement the ADT bag-a) adding an entry to a bag is fast. [ Adding an element just after the last entry of that array does not hamper the current sequence or position of existing elements, so this choice is advantageous.]
4.Statements about binary search:
a) searching a sorted array is O(n)------this is false as it is O(log n);
b) searching an unsorted array is O(log n)------this is false because binary search is always performed upon sorted sequence. So, at first we have to sort that array then only we can perform binary search upon it.
If we perform merge sort and then apply binary search, the complexity would be O(n log n).
c)searching a sorted linked list is as efficient as searching a sorted array-------this is false because link list traversal is O(N) whereas array traversal is O(1). That is the main reason for getting slower performance in case of binary search on a sorted linked list.
d)on each pass half the remaining elements in the list are eliminated--------- This is true; Because binary search method executes upon a sorted sequence by constantly dividing the search interval in half.
5.The method of removing an item from the front of the queue is called a) dequeue. [Dequeue function gives the front element of a queue and delete it from the queue.]
6.Given a linked list containing the values first->5->10->15->20->null, when 10 is deleted from the list what happens is: a) the node containing 5 must be changed to point to the node which contains 15. Then the node containing 10 can be deleted. [Because if we delete the node which contains 10 first, then rest of the list’s link will be deleted. So first we have to save the rest of the list’s link and attach that link with the node which is previous to 10(i.e. 5 here), and then only we can delete 10.]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.