823 views
1 votes
1 votes

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

2 Answers

1 votes
1 votes
Option C, as DLL is not atleast twice but it is less than twice the storage required by single linked list.
edited by
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

0 votes
0 votes
2 answers
1
Arjun asked Oct 10, 2016
523 views
Consider the following declaration of a two dimensional array in C:char a[1000][40];Assuming that the main memory is byte addressable and that the array is stored startin...
4 votes
4 votes
1 answer
3
Arjun asked Oct 10, 2016
729 views
In a Network where bytes are continuously being transferred, it is required to identify the most frequently transferred byte. What would be an appropriate data structure ...
2 votes
2 votes
2 answers
4
Arjun asked Oct 10, 2016
702 views
What would be an appropraite data structure to represent family hierarchy where each node is an individual and there in no requirement to keep "married to" relationship?B...