GATE CSE 1996 | Question: 1.12

Question

Consider the following statements:

1. First-in-first out types of computations are efficiently supported by STACKS.

2. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.

3. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.

4. Last-in-first-out type of computations are efficiently supported by QUEUES.

• A. $(ii)$ and $(iii)$ are true
• B. $(i)$ and $(ii)$ are true
• C. $(iii)$ and $(iv)$ are true
• D. $(ii)$ and $(iv)$ are true

Comments

Refer to chapter 3, of "Data Structures and Algorithm Analysis" by Mark Allen Weiss.

---

Correct me, views on option 3.
( as Deepak sir told list mathematically means ordered sequence of elements, like sorted digits).
What are basic operations?
Insert(x): find correct position to insert and adjust the ordering of list
Delete(x): for that we have find x then delete that key and adjust the remaining position of lists
Find(x): Finding some x in ordered list

What we have with us?
Linked List vs array

Insert(x)= Finding correct position(O(n)) + few pointer manipulation(O(1)) //LL
Insert(x)= Finding correct position(O(logn), binary search) + shifting(O(n)) // Array
Delete(x)= Same as insert  so both O(n)
Similarly Find(x)

Both similar nearly same till now, but LL are dynamic in nature whereas arrays are static
Expanding()= O(1) in LL just malloc and pointer manipulation
Expanding()=O(n) in array cause we will create new array with bigger size then shift all the elements

So LL wins?
 

 

---

@Deepak Poonia sir isn't a sequence is itself ordered i.e by the position of the elements

like for a list 5,0,9,2,1,2,4 here 5 is at position 0, 0 at position 2 and so on... this is a sequence which is ordered already.

moreover we can say about the sortedness and unsortedness of the sequence. like the sequence above is not sorted.

also, unordered sequence which we may say the above example is really a unsorted sequence, isn't it?

Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.

How one can define the basic list of operations, or what does basic really mean to be is it insertion, deletion or just a lookup on the list? I mean we can't generally say a basic operation is the one that defines so and so operation. 

For an example: I consider this set of operation to be basic set of operations: Set A = {looking 1st element of the LL, looking 2nd element of the LL, looking 3rd element of the LL, looking 4th element of the LL, ... Looking nth element of the LL} 

Clearly array will take O(1) for every element lookup and LL will gradually becomes worse going towards O(n). And this shows that for Set A the array implementation of list is better than that of a LL implementation. 

And one can't simply say we need to consider other operations as well like insert, delete etc. But I don't care about these operations I have a "Set" and that's my only definition of a basic operation. Question nowhere mentioned what basic operations are. And ofcourse baisc operation can be infinite just as my Set A grows for elements till infinity. 

In my opinion question is half/ ambiguous to interpretations.

 

Please other's don't ask me to learn more about LL operations and other things, I know each and every other operations (every standard book has that), I am just trying to make out a point here and try to think it as if a question been asked in an interview, which involves these kinds of interpretation.

Answer 1

(A). (i) and (iv) are false.

http://en.wikipedia.org/wiki/List_(abstract_data_type)#Operations

Comments

@Raj Singh 1 how will you know the size of list in advance? It will grow/shrink according to need right? Array is not useful in such case. Your comment is right but what is the use if basic work is not being done and going for optimization. :)

---

insertion in LL take O(1) while in array it takes O(n) and the crux is list dynamically change its size so LL is preferable

---

@mrinmoyh what say if we insert the node in the front which will cost you theta(1)?

 

Answer 2

Answer : (A)

Corrections :

First-in-first out types of computations are efficiently supported by QUEUES.

Last-in-first-out type of computations are efficiently supported by STACKS

Comments

First-in-first out types of computations are efficiently supported by STACKS.

https://gateoverflow.in/734/gate2001-2-16 

it is given stacks and not a single stack.

---

Hello shefali

statement is not false cause of stack/stacks , it's false because of word 'efficiently'.Stack efficiently support LIFO type of computations not FIFO.

Answer 3

A) Wrong stack is used for implementation of LIFO order

B) true provided list is dynamic in nature, for static list both will have same performance

C) can be true if we implementation circular queue using 2 pointer, else no advantage

D) false, queue is used to support FIFO

Comments

He didn't mention anywhere that link list is single link list.

total cost for which operation?

Tesla can you tell me again , why do you think option 2 is correct ?i thought you were categorizing it on the bases of Nature of lists (dynamic/static) and when list nature is static , of course link list are of no use and this make that statement false. But as i'm able to see , lists are just collection of data , when we implement them as array or link list , then we define their nature like dynamic /static.so in that way you reason in your answer is not making any sense? am i missing something ?

---

If nature of list is dynamic then no doubts Linked list is better.

Question does not say anything about nature of lined list so there is no harm in assuming it to be single linked list

On my previous comment I showed that single linked is better then array even for static list

 

So when we perfer array when we need random access to data, and when search queries are more then insertion and deletion

---

explain the concept of list for array and linkedlist

Answer 4

The first statement is true. Stacks are a type of data structure that follows the Last-in-first-out (LIFO) principle, where the last element added to the stack is the first one to be removed. This makes it efficient for performing first-in-first-out (FIFO) type of computations, such as undo/redo operations, backtracking, and recursive function calls.

The second statement is also true. Linked lists are a type of data structure where each element is a separate object with a reference to the next element. This allows for fast insertion and deletion of elements, which are commonly used operations in lists. Implementing lists on an array, on the other hand, requires shifting elements to make room for new elements or to fill gaps after deleting elements. This can be time-consuming and not efficient.

The third statement is also true. A circular array is an array that wraps around when it reaches the end, allowing for efficient use of space. Implementing a queue on a circular array allows for fast enqueue and dequeue operations, as well as efficient use of space. Implementing a queue on a linear array with two indices can lead to wasted space, as well as the need to shift elements when one end of the array becomes full.

The last statement is false. Queues are a type of data structure that follows the First-in-first-out (FIFO) principle, where the first element added to the queue is the first one to be removed. This makes it efficient for performing last-in-first-out (LIFO) type of computations, such as breadth-first traversals, scheduling, and load balancing tasks.

Answer 5

Stack operates on FIRST IN LAST OUT or LAST IN FIRST OUT principle.

Whereas Queue operates on FIRST IN FIRST OUT principle.

Therefore, statements i. and iv. are False

Hence, Correct Option is A) (ii) and (iii) are true

Answer 6

Anwser is in the uploaded image