in DS
364 views
1 vote
1 vote

Which of the following is false?

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

2 Answers

1 vote
1 vote
Option C, as DLL is not atleast twice but it is less than twice the storage required by single linked list.
edited by
by

4 Comments

any Explanation why D is true
0
0
yes, it is the same concept.
0
0
0 votes
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.

Answer:

Related questions