Answer the following questions with either true or false. 1. One can implement a

Question

Answer the following questions with either true or false.

1. One can implement a stack based on a linked list so that EACH INDIVIDUAL push/pop operation is time O(1)

2. One can implement a stack (of unbounded size) based on an array so that each idividual push/pop operation is time O(1)

3. One can reverse the order of the elements in a linked list in time O(n)

4. It is possible to append two linked lists in time O(1)

5. Adding an element to a heap has wort-case time complexity O(lon(n))

6. Returning the maximum element in a max-heap (but not deleting it from the heap) can be done in time O(1)

Explanation / Answer

1. True

The push/pop operation are of both O(1) in stack implementation based on LinkedList.

2.True

For push and pop operations they took only O(1) because they only operate on one end of data structure .

3. True

Reversal of linked list takes O(n) time and O(1) space complexity.

4. True

Linked list can be concatenated in time O(1) by using either single linked list or double Linked list.

5. TRUE

The required number of operations depends on number of levels that must rise to satisfy heap property So the insertion operation time complexity is O(logn) .

6.True

Because in max heap the root node will be the maximum element. So it takes O(1) time to find.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.