GATE Computer Science Engineering(CSE) 2027 Test: Arrays, Stack, Queues

Last in First OUT: The last item that is inserted into a given stack is the first item to be deleted.
A stack can be implemented using minimum two queues.
Stack is a dynamic data structure. It does not have a fixed size in the memory, and hence, size of a stack increases using push() and pop() operations.

permutations which start with D:
to print D first , all a,b,c must be pushed on to stack before popping D and the only arrangement possible = D C B A
permutations start with C:
you need to push a and b from stack A to stack B , now print C
content of stack B= b a (from top to bottom)
content of stack A = d
permutations possible = 3!/2! = 3 = they are c d b a, c b d a, c b a d --> 3 permutations here
permutations starting with b :
to print b first, a will be pushed onto stack B
content of stack B= a
content of stack A= c d
you can bring these out in (3! -1) as (d a c) is not possible--> 5 possible
permutations starting with a:
fix ab
a b _ _
in this a b c d or a b dc
fix ac
a c _ _
a c b d or a c d b
fix ad
a d _ _
a d c b
total 5
total = 1+3+5+5= 14

The item can be pushed to stack and later popped and printed, or printed directly. 1, 2, 3, 4, 5 is the input then (a) is not possible because once pushed 1 is printed after 2. Similarly (c) and (d) are also not possible.

We can obtain the sequence by performing the operations in the manner given below.

The sequence obtained will be 3,4,5,2,1.

Hence, (b) is the output.

In circular doubly linked list, one does not need to traverse the whole list to find the end of the list.
The second list can be concatenated at any location. Only fixed number of pointers need to be changed. Hence can be done in O(1) time.

Operator stack is used to convert infix expression to postfix form whereas operand stack is used to convert postfix to infix notation.

If a queue contains an element Front = Rear, it can neither be NULL nor be -1.
So, option (a) and (c) are wrong.
Since, it is a circular queue and bottleneck case arises in case of two elements where Front = Rear + 1 and Front = Rear - 1, both are possible.
So, what all we can say is Front = Rear ≠ NULL if only one element is there in circular queue.

The array is stored in row-major order, that means the elements are stored in the memory row-wise. 
Suppose we have the 2D array
1 2 3
4 5 6
It will be stored in the memory as 1 2 3 4 5 6
If array is stored as column-major order then it will be stored as 1 4 2 5 3 6

Let A be a 2D array, A: array [b₁ …. u₁] [b₂ …… u₂], then 
To find the location of A[i][j] for a 2D array stored in Row-major order use the following formula:
 

Loc A[i][j] = L + [ (i - b₁) (u₂ - b₂ +1) + (j  - b₂) ] x M

L - base address of the array, i.e. address of the first element of the array

M - Memory Size, here each integer takes only 1 memory location therefore M = 1

Loc A[i][j] = 100 + [ (i - 1) (15 - 1 +1) + (j  - 1) ] x 1

                = 100 + (i - 1) 15 + j -1 = 15i + j + 84

Array is

Sum = 0 + 1 + 2 + ... + (-1) + (-2) + ... = 0.

Effect of the given 3 reversals for any k is equivalent to left rotation of the array of size n by k.

∴ n = 7, k = 2
reverse (S, 1, 2) we get [2, 1, 3, 4, 5, 6, 7]
reverse (S, 3, 7) we get [2, 1, 7, 6, 5, 4, 3]
reverse (S, 1, 7) we get [3, 4, 5, 6, 7, 1,2]