Dark Mode

1 vote

Which of the following is false?

- Arrays are better than linked lists for sorting due to better data locality.
- Asymptotic time complxity for FindMax is same on an unsorted array as that on a singly linked list.
- A doubly linked list takes at least twice the storage as of a singly linked list.
- Given a fixed maximum size, a circular queue is preferrable to a normal queue

0 votes

Arrays are stored contiguously in memory, that's why pointer arithmetic works on them. They sure have better data locality in the spatial context, compared to Linked Lists — whose each node can be far apart in memory. **Option A is True**.

**Option B is also True**. For any unsorted sequence, we have to traverse it all the way to the end in the worst case to find anything.

**Option C is False**. A Doubly Linked List only has twice the number of pointers than Singly Linked Lists. The data content is same.

**Option D is True**. Consider the FIFO Page Replacement algorithm. If we have 4 processes, for a circular queue we only need 4 slots, because as and when the previous slots get cleared, they can be reused. But in a normal queue, we won't use the previous slots that are now cleared, we'd keep incrementing "rear" to add more elements.