GATE CSE
Data Structures
Stacks and Queues
Previous Years Questions

## Marks 1

Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in the figure). The only operations allowed on thes...
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is COR...
The result evaluating the postfix expression $$10\,\,5\, + 60$$ $$\,\,6/\, * \,8\, -$$ is
A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and ...
The best data structure to check whether an arithmetic expression has balanced parentheses is a
Which of the following is essential for converting an infix expression to the postfix form efficiently?
Consider the following statements: (i) First-in-first out types of computations are efficiently supported by STACKS. (ii) Implementing LISTS on link...

## Marks 2

Consider the following sequence of operations on an empty stack. push(54); push(52); pop(); push(55); push(62); s = pop(); Consider the following se...
Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP ins...
Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations ar...
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are: i. isEmpty (Q) — returns true ...
The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * - Note that ^ is the exponentiation ...
Consider the following C program: #include #define EOF -1 void push (int); /* push the argument on the stack */ int pop (void); /* pop t...
An implementation of a queue Q, using two stacks S1 and S2, is given below: void insert(Q, X){ push(S1, X); } void delete(Q){ if(stack - empty(S1)...
The following function computes the value of mCn correctly for all legal values m and n (m≥1,n≥0 and m>n) int func(int m, int n) { if (E) ...
Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, -. Th...
A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in the same order onto a stack, b...
Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop ope...
Compute the post fix equivalent of the following expression. 3 * log(x+1) - a/2
What value would the following function return for the input x = 95? function fun (x:integer):integer; Begin If x > 100 then fun : x –...
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key...
The postfix expression for the infix expression A + B * (C + D) / F + D * E is:
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4...
The following sequence of operations is performed on stack: PUSH (10),PUSH (20),POP,PUSH (10),PUSH (20),POP,POP,POP,PUSH (20),POP The sequence of th...
EXAM MAP
Joint Entrance Examination