6.In the remove method, setting the last entry of the array to null 7.The most e
ID: 3677389 • Letter: 6
Question
6.In the remove method, setting the last entry of the array to null
7.The most efficient approach to deal with a gap left in an array after removing an entry from a bag is
8.If an array bag contains the entries “lions”, “elephants”, “otters”, “bears”, “tigers”, “lemurs” and a call to the remove method with the entry “bears” is made, what does the array look like after remove?
9.What is an advantage of using a chain for a Bag ADT?
10.Which code correctly adds the first entry to an empty bag?
11.Where is a new node added to a linked list?
12.If the following nodes are added in order, what does the resultant chain look like?
“L”, “A”, “R”, “X”, “J”
13.The remove method for a given entry returns
14.What is the Big-O time complexity for an algorithm to display the nth integer in an array of integers and why?
Explanation / Answer
Most of the questions are incomplete and cannot be answered without making few assumption and few questions can be answered clearly.
Point no 6. Is it asking to show how to remove lst item from an array. In that case first obtain the length of the array and then remove the element. In java the size of array can be obtained by length property of array e:g if a[] is an array then length is a.length and to remove last item set a[length-1]= null. (Because array index starts with 0 thus length-1 will give the last item).
7. Usually the simplest approach is to set the value to null but if efficiency is required then the best approach is to copy the non null contents of array to another array. This approach is efficient as far as space is concerned but not in terms of time complexity and computation. Another approach is to shift all the elements of array so that null entry comes at the end of the array. But the problem with this approach is that the size of array doesnt change and it still contains null values and it has overhead of shifting the elements.
8. The point is a bit confusing. It depends how the remove method is implemented as I discussed above in point 7.
9. An array has a fixed size, and so it can either become full or have several unused elements. Bag ADT uses memory only as needed for a new entry and returns the unneeded memory to the system after an entry is removed. By linking data, this avoids moving data when adding or removing bag entries. These features make this way of implementing a bag an important alternative to array-based approaches.
10. Here is a piece of code to add new element to bag
public boolean add(T newEntry)
{
boolean result = true;
if (isFull())
{
result = false;
}
else
{ // assertion: result is true here
bag[numberOfEntries] = newEntry;
numberOfEntries++;
} // end if
return result;
}
11. New node can be added anywhere in the list, in beginning, middle, or end of the list.
12. Usually the elements are added in order of their entry so the chain will look like as the elements were entered. “L”, “A”, “R”, “X”, “J”
13. Remove returns the removed element from the bag and if no such entry exists, it returns null.
14. The Big-O time complexity will be O(1) because the index is known as n and the element can be acessed directly from the array and there is no need to traverse the array. e:g if the value of n is 2 that is display the second element of the array , this can be done in single statement by accessing the array at index 1 "a[1]" which gives the second element of the array.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.