Queues-and-Stacks

Question 1

A queue Q containing n items and an empty stack S are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the top of the stack, and the order of all other items is preserved. Show how this can be done in O(n) time using only a constant amount of additional storage. Note that the only operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.

A
Theory Explanation.
Question 2

A stack is used to pass parameters to procedures in a procedure call.
(a) If a procedure P has two parameters as described in procedure definition:

    procedure P (var x :integer; y: integer); 
    and if P is called by ; P(a,b) 

State precisely in a sentence what is pushed on stack for parameters a and b.

(b) In the generated code for the body of procedure P, how will the addressing of formal parameters x and y differ?

A
Theory Explanation.
Question 3
Consider the following sequence of operations on an empty stack.
          push(54); push(52); pop(); push(55); push(62); s=pop();
Consider the following sequence of operations on an empty queue.
          enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();
The value of s + q is ________
A
86
Question 3 Explanation: 

push(54) ⇒ 54

push(52)=> 54, 52(top)

pop() ⇒ 54 (top)

push(55)==> 54, 55(top)

push(62) ⇒ 54,55,62(top)

s=pop() ⇒ 62 will store into the variable s then s=62

 

enqueue(21) ⇒     (front) 21(rear)

enqueue(24) ⇒   (Front)21, 24(rear)

dequeue()==> (front) 24(rear)

enqueue(28) ===> (front) 24,28 (rear)

enqueue(32)====>(front) 24,28,32 (rear)

q=dequeue() ⇒ value 24 will store into the variable “q”

q=24

 

S+q =62+24 =86

Question 4

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 integers i. 

If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?

A
6
B
4
C
3
D
2
Question 4 Explanation: 
2, -3, 2, -1, 2
f(Ø)=0 and f(push(S,i) = max(f(S),0) + i;
Initially stack is empty and for empty stack 0 is given.
f(push(0,2)) = max(f(Ø),0) + 2 = max(Ø,0) + 2 = 2
f(push(2,-3)) = max(2,0) + (-3) = 2 - 3 = -1
f(push(-1,2)) = max(-1,0) + 2 = 0 + 2 = 2
f(push(2,-1)) = max(2,0)+ (-1) = 2 - 1 = 1
f(push(1,2)) = max(1,0) + 2 = 1 + 2 = 3
So, 3 will be the answer.
∴ Option C is correct.
Question 5

Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.

The maximum possible number of iterations of the while loop in the algorithm is _________.

A
256
B
257
C
258
D
259
Question 5 Explanation: 
The maximum possible number of iterations of the while loop in this algorithm is:
Try to solve it for 3 numbers [1. 2, 3].
Step 1: Initially Queue contains 3 elements so after 5 while loop iterations queue contains 3, 2 and stack contains 1.
Step 2: Now after 3 more while loop iterations, Queue contains 3 and stack contains 1, 2 (TOS = 2).
Step 3: After 1 more while loop iteration, push 3 onto the stack so queue is empty and stack contains 1, 2, 3 {top = 3}.
So, total number of iterations will be 5 + 3 + 1 = 9
i.e., for 3 it is 9 iterations (3*3)
for 4 it is 16 iterations (4*4)
Given: 16 numbers, so 16 * 16 = 256
Question 6
Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following operations are performed on a stack S and a queue Q, both of which are initially empty.
I: push the elements of a from a0 to a5 in that order into S.
II: enqueue the elements of a from a0 to a5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S.
VIII: Repeat operation
VII three times. IX: pop an element from S. X: pop an element from S.
The top element of S after executing the above operations is _____?
A
8
Question 6 Explanation: 
Given the sequence “a” of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2.
I: push the elements from a0 to a5 in that order into S.

II: enqueue the elements of a from a0 to a5 in that order into Q.

III: pop an element from S.

IV: dequeue an element from Q.

V: pop an element from S.

VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S.
Element “7” is deleted and inserted into stack “S”

VIII: Repeat operation VII three times.
After performing the VIII operation , the elements of stack are as shown below

IX: pop an element from S.

X: pop an element from S

The top element of S after executing the above operations is 8.
Question 7
Which one of the following is a Meldable priority queue?
A
Leftist Heap
B
Binary Heap
C
AVL trees
D
Red – Black trees
Question 7 Explanation: 
The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us to enqueue or dequeue items in O ( log n ).
Question 8
The following sequence of operations is performed on a stack:
PUSH ( 10 ). PUSH ( 20 ). POP. PUSH ( 10 ). PUSH ( 20 ). POP.  POP. POP. PUSH ( 20 ). POP 
The sequence of values popped out is
A
20, 10, 20, 10, 20
B
20, 20, 10, 10, 20
C
10, 20, 20, 10, 20
D
20, 20, 10, 20, 10
Question 8 Explanation: 
⇒ Push(10)

⇒ Push(20)

⇒ Pop 20

⇒ Push(10)

⇒ Push(20)

⇒ Pop 20

⇒ Pop 10

⇒ Pop 10

⇒ Push(20)

⇒ Pop 20
Question 9
BFS uses the following data structure to hold nodes that are waiting to be processed
A
Queue
B
Stack
C
File
D
All the above
Question 9 Explanation: 
BFS uses Queue data structure. DFS uses Stack data structure.
Question 10
The data structure that is used to implement recursion is
A
Stack
B
Binary Tree
C
Queue
D
All of the above
Question 10 Explanation: 
Stack data structure is used to implement recursion.
Question 11
The infix form of prefix expression *+abc is
A
a+b*c
B
(a+b)*c
C
a* (b+c)
D
None of the above
Question 11 Explanation: 

Now by traversing the tree we get the infix expression as, (a+b)*c
Question 12
Which of the following data structures allows both addition and deletion of items from either end?
A
Double Ended Queue
B
Queue
C
Priority Queue
D
Stack
Question 12 Explanation: 
Double Ended Queue: It is abbreviated to deque and it is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a head-tail linked list
Stack: Stack is an abstract data type that serves as a collection of elements, with two principal operations:
->push, which adds an element to the collection, and
->pop, which removes the most recently added element that was not yet removed.
Both PUSH and POP operations are done from a single end.The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out).
Queue: a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and removal from the other end of the sequence. It allows addition and deletion of items from fixed different ends.
Question 13
A stack is implemented with an array of ‘A [0...N-1]’ and a variable ‘pos’. The push and pop
operations are defined by the following code.
push(x)
A[pos] x
pos pos+1
end push
pop()
pospos+1
Return A[pos]
end pop
Which of the following will initialize an empty stack with capacity N for the above implementation?
A
pos ← -1
B
pos ← 0
C
pos ← 1
D
pos ←N-1
Question 13 Explanation: 
If you check push function, for every push we are decrementing pos by one.
Now if you imagine an array of length N-1, for every push the empty indices are getting decremented.
To explain in detail,
consider an empty array, so number of empty indices are N-1 ......(1)
When we push one element into it, the empty indices will reduce by 1 (i.e. decreented.)
Hence, From equation 1 we can say that pos is initialised to N-1
Question 14
At a given moment a queue contains stored in it. If the capacity of the queue is 6 then which of the following sequence of operations results in a modified queue contents?
A
delete a, b; and insert e,a,f;
B
insert e,a,f and delete a,b
C
insert e, delete b and insert f
D
insert e,f, move a to place it between e and f, then delete b
Question 15
What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume that all insertions can be accommodated.
A
θ(1) , θ(n)
B
θ(n) , θ(1)
C
θ(1) , θ(1)
D
θ(n) , θ(n)
Question 15 Explanation: 
Insertion will remain the same for best,average and worst case time complexities. It will take a constant amount of time only.
Extract-Min will take θ(n) time for above conditions. The array is unsorted there is naturally no better algorithm than just linear search. Worst case performance for linear search is Θ(n)
Question 16

If (rear == maxsize - 1) rear=0; else rear = rear + 1; is required in

A
circular queue
B
linear queue
C
stack
D
deque
Question 16 Explanation: 
Because If (rear == maxsize - 1) rear=0, is used in a circular queue because after maxsize-1 the index will be 0.
Question 17

The data structure required for breadth first traversal on a graph is

A
queue
B
stack
C
array
D
tree
Question 17 Explanation: 
The data structure required for breadth first traversal on a graph is Queue.
The data structure required for depth first traversal on a graph is Stack.
Question 18

Depth first search graph search algorithm uses ____ data structure for its implementation.

A
Stack
B
Tree
C
Dequeue
D
Queue
Question 18 Explanation: 
Depth first search algorithm uses stack data structure for its implementation.
Whereas Breadth first search algorithm uses queue data structure for its implementation.
Question 19

For implementation of recursion system uses ____ data structure.

A
Linked list
B
Deque
C
Stack
D
Queue
Question 19 Explanation: 
Stack. Because of its LIFO (Last In First Out) property it remembers its 'caller' so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.
Question 20

Queue structure is used in ____

A
Polynomial addition
B
Recursion
C
Depth First search algorithm
D
Breadth First search algorithm
Question 20 Explanation: 
Polynomial addition uses array or linked list data structure.
Recursion uses stack data structure.
Depth first search algorithm uses stack data structure.
Breadth first search algorithm uses queue data structure.
Question 21

____ is First in last out kind of data structure.

A
Stack
B
Array
C
Deque
D
Queue
Question 21 Explanation: 
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
Question 22

With respect to deque which of the following is true?

A
Insertion is done from front end
B
Insertion and deletion can be done at front and rear ends
C
Deletion is done from rear end
D
Insertion is done only from rear end
There are 22 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access