Test: Queues & Stacks - Computer Science Engineering (CSE) MCQ
25 Questions MCQ Test - Test: Queues & Stacks
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ( n refers to the number of items in the queue)?
Consider the following statements:
i. First-in-first-out types of computations are efficiently supported by STACKS.
ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
iv. Last-in-first-out type of computations are efficiently supported by QUEUES.
ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
iv. Last-in-first-out type of computations are efficiently supported by QUEUES.
| 1 Crore+ students have signed up on EduRev. Have you? Download the App |
What is the minimum number of stacks of size required to implement a queue of size ?
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(S2)) then
if (stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
let n insert and m(≤ n)delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
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 if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:
void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
i = delete(Q);
f(Q);
insert(Q, i);
}
}
What operation is performed by the above function f ?
Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
MultiDequeue(Q){
m = k
while (Q is not empty) and (m > 0) {
Dequeue(Q)
m = m – 1
}
}
What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time?
(I) Next pointer of front node points to the rear node.
(II) Next pointer of rear node points to the front node.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
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
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,5 in that order?
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented as INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in
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 operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m ≥1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is
A single array A[1 .. MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array.
Variables top1 and top 2 (top < top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is
Assume that the operators +, , X are left associative and is right associative. The order of precedence (from highest to lowest) is , X, +, -. The postfix expression corresponding to the infix expression 
is
The best data structure to check whether an arithmetic expression has balanced parentheses is a
A program attempts to generate as many permutations as possible of the string, 'abcd' by pushing the characters in the same order onto a stack, but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program?
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)?
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 operator. The top two elements of the stack after the first * is evaluated are
Consider the following C program:
#include <stdio.h>
#define EOF -1
void push (int); /* push the argument on the stack */
int pop (void); /* pop the top of the stack */
void flagError ();
int main ()
{ int c, m, n, r;
while ((c = getchar ()) != EOF)
{ if (isdigit (c) )
push (c);
else if ((c == '+') || (c == '*'))
{ m = pop ();
n = pop ();
r = (c == '+') ? n + m : n*m;
push (r);
}
else if (c != ' ')
flagError ();
}
printf("% c", pop ());
}
What is the output of the program for the following input?
5 2 * 3 3 2 + * +
Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE (with respect to this modified stack)?
The result evaluating the postfix expression 10 5 + 60 6 / * 8 - is
We have an implementation that supports the following operations on a stack (in the instructions below, is the name of the stack).
isempty (s) : returns if is empty, and otherwise.
top (s) : returns the top element of the stack, but does not pop the stack; returns if the stack is empty.
push (s,x) : places on top of the stack.
pop(s) : pops the stack; does nothing if is empty.
Consider the following code:
pop_ray_pop(x):
s=empty
for i=1 to length(x):
if (x[i] == '('):
push(s, x[i])
else:
while (top(s)=='('):
pop(s)
end while
push(s, ')')
end if
end for
while not isempty(s):
print top(s)
pop(s)
end while
What is the output of this program when
pop_ray_pop("(((()((())((((")
is executed?
Consider the following pseudocode that uses a stack
declate a stack of characters
while (there are more characters in the word to read)
{
read a character
push the character on the stack
}
while ( the stack is not empty)
{
pop a chatacher off the stack
write the character to the screen
}
Q.
What is output for input "geeksquiz"?
Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced:
declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')' and the stack is not empty )
pop a character off the stack
else
print "unbalanced" and exit
}
print "balanced"
Q.
which of these unbalanced sequences does the above code think is balanced?
Top Courses for Computer Science Engineering (CSE)
Important Questions for Queues & Stacks
Queues & Stacks MCQs with Answers
Online Tests for Queues & Stacks
|
© EduRev
|
Education Revolution
|
Follow Us
|
