Data Structure Questions and Answers – Stack using Array

« Prev
Next »
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Stack
using Array”.

1. Which of the following real world scenarios would you associate with a stack data
structure?
a) piling up of chairs one above the other
b) people standing in a line to be serviced at a counter
c) offer services based on the priority of the customer
d) tatkal Ticket Booking in IRCTC
View Answer
Answer: a
Explanation: Stack follows Last In First Out (LIFO) policy. Piling up of chairs one above the
other is based on LIFO, people standing in a line is a queue and if the service is based on
priority, then it can be associated with a priority queue. Tatkal Ticket Booking Follows First
in First Out Policy. People who click the book now first will enter the booking page first.
2. What does the following function check for? (all necessary headers to be included and
function is called from main)

#define MAX 10
 
typedef struct stack
{
int top;
int item[MAX];
}stack;
 
int function(stack *s)
{
if(s->top == -1)
return 1;
else return 0;
}

a) full stack
b) invalid index
c) empty stack
d) infinite stack
View Answer
Answer: c
Explanation: An empty stack is represented with the top-of-the-stack(‘top’ in this case) to be
equal to -1.
3. What does ‘stack underflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception
View Answer
Answer: c
Explanation: Removing items from an empty stack is termed as stack underflow.
4. What is the output of the following program?

public class Stack

{
protected static final int CAPACITY = 100;
protected int size,top = -1;
protected Object stk[];
 
public Stack()
{
stk = new Object[CAPACITY];
}
 
public void push(Object item)
{
if(size_of_stack==size)
{
System.out.println("Stack overflow");
return;
}
else
{
top++;
stk[top]=item;
}
}
public Object pop()
{
if(top<0)
{
return -999;
}
else
{
Object ele=stk[top];
top--;
size_of_stack--;
return ele;
}
}
}
 
public class StackDemo
{
public static void main(String args[])
{
Stack myStack = new Stack();
myStack.push(10);
Object element1 = myStack.pop();
Object element2 = myStack.pop();
 System.out.println(element2);
}
}

a) stack is full
b) 20
c) 0
d) -999
View Answer
Answer: d
Explanation: The first call to pop() returns 10, whereas the second call to pop() would result
in stack underflow and the program returns -999.
5. What is the time complexity of pop() operation when the stack is implemented using an
array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
View Answer
Answer: a
Explanation: pop() accesses only one end of the structure, and hence constant time.
6. Which of the following array position will be occupied by a new element being pushed for
a stack of size N elements(capacity of stack > N)?
a) S[N-1]
b) S[N]
c) S[1]
d) S[0]
View Answer
Answer: b
Explanation: Elements are pushed at the end, hence N.
7. What happens when you pop from an empty stack while implementing using the Stack
ADT in Java?
a) Undefined error
b) Compiler displays a warning
c) EmptyStackException is thrown
d) NoStackException is thrown
View Answer
Answer: c
Explanation: The Stack ADT throws an EmptyStackException if the stack is empty and a
pop() operation is tried on it.
8. What is the functionality of the following piece of Java code?
Assume: ‘a’ is a non empty array of integers, the Stack class creates an array of specified
size and provides a top pointer indicating TOS(top of stack), push and pop have normal
meaning.

public void some_function(int[] a)

{
Stack S=new Stack(a.length);
int[] b=new int[a.length];
for(int i=0;i<a.length;i++)
{
S.push(a[i]);
}
for(int i=0;i<a.length;i++)
{
b[i]=(int)(S.pop());
}
System.out.println("output :");
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}

a) print alternate elements of array

b) duplicate the given array
c) parentheses matching
d) reverse the array
View Answer
Answer: d
Explanation: Every element from the given array ‘a’ is pushed into the stack, and then the
elements are popped out into the array ‘b’. Stack is a LIFO structure, this results in
reversing the given array.
9. Array implementation of Stack is not dynamic, which of the following statements supports
this argument?
a) space allocation for array is fixed and cannot be changed during run-time
b) user unable to give the input for stack operations
c) a runtime exception halts execution
d) improper program compilation
View Answer
Answer: a
Explanation: You cannot modify the size of an array once the memory has been allocated,
adding fewer elements than the array size would cause wastage of space, and adding more
elements than the array size at run time would cause Stack Overflow.
10. Which of the following array element will return the top-of-the-stack-element for a stack
of size N elements(capacity of stack > N)?
a) S[N-1]
b) S[N]
c) S[N-2]
d) S[N+1]
View Answer
Answer: a
Explanation: Array indexing start from 0, hence N-1 is the last index.
Data Structure Questions and Answers – Stack using Linked
List
« Prev
Next »
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Stack
using Linked List”.

1. What is the best case time complexity of deleting a node in a Singly Linked list?
a) O (n)
b) O (n2)
c) O (nlogn)
d) O (1)
View Answer
Answer: d
Explanation: Deletion of the head node in the linked list is taken as the best case. The
successor of the head node is changed to head and deletes the predecessor of the newly
assigned head node. This process completes in O(1) time.
2. Which of the following statements are not correct with respect to Singly Linked List(SLL)
and Doubly Linked List(DLL)?
a) Complexity of Insertion and Deletion at known position is O(n) in SLL and O(1) in DLL
b) SLL uses lesser memory per node than DLL
c) DLL has more searching power than SLL
d) Number of node fields in SLL is more than DLL
View Answer
Answer: d
Explanation: To insert and delete at known positions requires complete traversal of the list
in worst case in SLL, SLL consists of an item and a node field, while DLL has an item and
two node fields, hence SLL occupies lesser memory, DLL can be traversed both ways(left
and right), while SLL can traverse in only one direction, hence more searching power of
DLL. Node fields in SLL is 2 (data and address of next node) whereas in DLL is 3(data,
address to next node, address to previous node).
3. Given below is the Node class to perform basic list operations and a Stack class with a
no arg constructor.
Select from the options the appropriate pop() operation that can be included in the Stack
class. Also ‘first’ is the top-of-the-stack.

class Node
{
protected Node next;
protected Object ele;
Node()
{
this(null,null);
}
Node(Object e,Node n)
 {
ele=e;
next=n;
}
public void setNext(Node n)
{
next=n;
}
public void setEle(Object e)
{
ele=e;
}
public Node getNext()
{
return next;
}
public Object getEle()
{
return ele;
}
}
 
class Stack
{
Node first;
int size=0;
Stack()
{
first=null;
}
}

a)

public Object pop()

{
if(size == 0)
System.out.println("underflow");
else
{
Object o = first.getEle();
first = first.getNext();
size--;
return o;
}
}

b)

public Object pop()

{
if(size == 0)
System.out.println("underflow");
else
{
Object o = first.getEle();
 first = first.getNext().getNext();
size--;
return o;
}
}

c)

public Object pop()

{
if(size == 0)
System.out.println("underflow");
else
{
first = first.getNext();
Object o = first.getEle();
size--;
return o;
}
}

d)

public Object pop()

{
if(size == 0)
System.out.println("underflow");
else
{
first = first.getNext().getNext();
Object o = first.getEle();
size--;
return o;
}
}

View Answer
Answer: a
Explanation: pop() should return the Object pointed to by the node ‘first’. The sequence of
operations is, first, get the element stored at node ‘first’ using getEle(), and second, make
the node point to the next node using getNext().
 
 
4. What does the following function do?

public Object some_func()throws emptyStackException

{
if(isEmpty())
throw new emptyStackException("underflow");
return first.getEle();
}
a) pop
b) delete the top-of-the-stack element
c) retrieve the top-of-the-stack element
d) push operation
View Answer
Answer: c
Explanation: This code is only retrieving the top element, note that it is not equivalent to pop
operation as you are not setting the ‘next’ pointer point to the next node in sequence.
5. What is the functionality of the following piece of code?

public void display()

{
if(size == 0)
System.out.println("underflow");
else
{
Node current = first;
while(current != null)
{
System.out.println(current.getEle());
current = current.getNext();
}
}
}

a) reverse the list

b) display the list
c) display the list excluding top-of-the-stack-element
d) reverse the list excluding top-of-the-stack-element
View Answer
Answer: b
Explanation: An alias of the node ‘first’ is created which traverses through the list and
displays the elements.
6. What does ‘stack overflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception
View Answer
Answer: b
Explanation: Adding items to a full stack is termed as stack underflow.
7. Given below is the Node class to perform basic list operations and a Stack class with a
no arg constructor. Select from the options the appropriate push() operation that can be
included in the Stack class. Also ‘first’ is the top-of-the-stack.

class Node
{
protected Node next;
protected Object ele;
 Node()
{
this(null,null);
}
Node(Object e,Node n)
{
ele=e;
next=n;
}
public void setNext(Node n)
{
next=n;
}
public void setEle(Object e)
{
ele=e;
}
public Node getNext()
{
return next;
}
public Object getEle()
{
return ele;
}
}
 
class Stack
{
Node first;
int size=0;
Stack()
{
first=null;
}
}

a)

public void push(Object item)

{
Node temp = new Node(item,first);
first = temp;
size++;
}

b)

public void push(Object item)

{
Node temp = new Node(item,first);
first = temp.getNext();
size++;
}

c)
public void push(Object item)
{
Node temp = new Node();
first = temp.getNext();
first.setItem(item);
size++;
}

d)

public void push(Object item)

{
Node temp = new Node();
first = temp.getNext.getNext();
first.setItem(item);
size++;
}

View Answer
Answer: a
Explanation: To push an element into the stack, first create a new node with the next pointer
point to the current top-of-the-stack node, then make this node as top-of-the-stack by
assigning it to ‘first’.
 
 
8. Consider these functions:
push() : push an element into the stack
pop() : pop the top-of-the-stack element
top() : returns the item stored in top-of-the-stack-node
What will be the output after performing these sequence of operations

push(20);
push(4);
top();
pop();
pop();
pop();
push(5);
top();

a) 20
b) 4
c) stack underflow
d) 5
View Answer
Answer: d
Explanation: 20 and 4 which were pushed are popped by the two pop() statements, the
recent push() is 5, hence top() returns 5.
9. Which of the following data structures can be used for parentheses matching?
a) n-ary tree
b) queue
c) priority queue
d) stack
View Answer
Answer: d
Explanation: For every opening brace, push it into the stack, and for every closing brace,
pop it off the stack. Do not take action for any other character. In the end, if the stack is
empty, then the input has balanced parentheses.
10. Minimum number of queues to implement stack is ___________
a) 3
b) 4
c) 1
d) 2
View Answer
Answer: c
Explanation: Use one queue and one counter to count the number of elements in the
queue.

Data Structure Questions and Answers – Queue using Array

« Prev
Next »
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on
“Queue using Array”.

1. Which of the following properties is associated with a queue?

a) First In Last Out
b) First In First Out
c) Last In First Out
d) Last In Last Out
View Answer
Answer: b
Explanation: Queue follows First In First Out structure.
2. In a circular queue, how do you increment the rear end of the queue?
a) rear++
b) (rear+1) % CAPACITY
c) (rear % CAPACITY)+1
d) rear–
View Answer
Answer: b
Explanation: Ensures rear takes the values from 0 to (CAPACITY-1).
3. What is the term for inserting into a full queue known as?
a) overflow
b) underflow
c) null pointer exception
d) program won’t be compiled
View Answer
Answer: a
Explanation: Just as stack, inserting into a full queue is termed overflow.
4. What is the time complexity of enqueue operation?
a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)
View Answer
Answer: d
Explanation: Enqueue operation is at the rear end, it takes O(1) time to insert a new item
into the queue.
5. What does the following Java code do?

public Object function()

{
if(isEmpty())
return -999;
else
{
Object high;
high = q[front];
return high;
}
}

a) Dequeue
b) Enqueue
c) Return the front element
d) Return the last element
View Answer
Answer: c
Explanation: q[front] gives the element at the front of the queue, since we are not moving
the ‘front’ to the next element,
it is not a dequeue operation.
6. What is the need for a circular queue?
a) effective usage of memory
b) easier computations
c) to delete elements based on priority
d) implement LIFO principle in queues
View Answer
Answer: a
Explanation: In a linear queue, dequeue operation causes the starting elements of the array
to be empty, and there is no way you can use that space, while in a circular queue, you can
effectively use that space. Priority queue is used to delete the elements based on their
priority. Higher priority elements will be deleted first whereas lower priority elements will be
deleted next. Queue data structure always follows FIFO principle.
7. Which of the following represents a dequeue operation? (count is the number of elements
in the queue)
a)

public Object dequeue()

{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%CAPACITY;
count--;
return ele;
}
}

b)

public Object dequeue()

{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
front = (front+1)%CAPACITY;
q[front] = null;
count--;
return ele;
}
}

c)

public Object dequeue()

{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
front = (front+1)%CAPACITY;
 Object ele = q[front];
q[front] = null;
count--;
return ele;
}
}

d)

public Object dequeue()

{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%CAPACITY;
return ele;
count--;
}
}

View Answer
Answer: a
Explanation: Dequeue removes the first element from the queue, ‘front’ points to the front
end of the queue and returns the first element.
 
 
8. Which of the following best describes the growth of a linear queue at runtime? (Q is the
original queue, size() returns the number of elements in the queue)
a)

private void expand()

{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
front = 0;
rear = size()-1;
}

b)

private void expand()

{
 int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
}

c)

private void expand()

{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i];
}
Q = newQ;
front = 0;
rear = size()-1;
}

d)

private void expand()

{
int length = size();
int[] newQ = new int[length*2];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
}

View Answer
Answer: a
Explanation: A common technique to expand the size of array at run time is simply to
double the size. Create a new array of double the previous size and copy all the elements,
after copying do not forget to assign front = 0 and rear = size()-1, as these are necessary to
maintain the decorum of the queue operations.
 
 
9. What is the space complexity of a linear queue having n elements?
a) O(n)
b) O(nlogn)
c) O(logn)
d) O(1)
View Answer
Answer: a
Explanation: Because there are n elements.
10. What is the output of the following Java code?

public class CircularQueue

{
protected static final int CAPACITY = 100;
protected int size,front,rear;
protected Object q[];
int count = 0;
 
public CircularQueue()
{
this(CAPACITY);
}
public CircularQueue (int n)
{
size = n;
front = 0;
rear = 0;
q = new Object[size];
}
 
 
public void enqueue(Object item)
{
if(count == size)
{
System.out.println("Queue overflow");
return;
}
else
{
q[rear] = item;
rear = (rear+1)%size;
count++;
}
}
public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%size;
count--;
return ele;
}
}
public Object frontElement()
 {
if(count == 0)
return -999;
else
{
Object high;
high = q[front];
return high;
}
}
public Object rearElement()
{
if(count == 0)
return -999;
else
{
Object low;
rear = (rear-1)%size;
low = q[rear];
rear = (rear+1)%size;
return low;
}
}
}
public class CircularQueueDemo
{
public static void main(String args[])
{
Object var;
CircularQueue myQ = new CircularQueue();
myQ.enqueue(10);
myQ.enqueue(3);
var = myQ.rearElement();
myQ.dequeue();
myQ.enqueue(6);
var = mQ.frontElement();
System.out.println(var+" "+var);
}
}

a) 3 3
b) 3 6
c) 6 6
d) 10 6
View Answer
Answer: a
Explanation: First enqueue 10 and 3 into the queue, followed by a dequeue(removes 10),
followed by an enqueue(6), At this point, 3 is at the front end of the queue and 6 at the rear
end, hence a call to frontElement() will return 3 which is displayed twice.
 Data Structure Questions and Answers – Queue using
Linked List
« Prev
Next »
This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on
“Queue using Linked List”.

1. In linked list implementation of queue, if only front pointer is maintained, which of the
following operation take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both Insertion and To empty a queue
View Answer
Answer: d
Explanation: Since front pointer is used for deletion, so worst time for the other two cases.
2. In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) At any position in the linked list
View Answer
Answer: c
Explanation: Since queue follows FIFO so new element inserted at last.
3. In linked list implementation of a queue, front and rear pointers are tracked. Which of
these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
View Answer
Answer: b
Explanation: Since queue follows FIFO so new element inserted at last.
4. In linked list implementation of a queue, front and rear pointers are tracked. Which of
these pointers will change during an insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
View Answer
Answer: c
Explanation: Since its the starting of queue, so both values are changed.
5. In case of insertion into a linked queue, a node borrowed from the __________ list is
inserted in the queue.
a) AVAIL
b) FRONT
c) REAR
d) NULL
View Answer
Answer: a
Explanation: All the nodes are collected in AVAIL list.
6. In linked list implementation of a queue, from where is the item deleted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) Node before the tail
View Answer
Answer: a
Explanation: Since queue follows FIFO so new element deleted from first.
7. In linked list implementation of a queue, the important condition for a queue to be empty
is?
a) FRONT is null
b) REAR is null
c) LINK is empty
d) FRONT==REAR-1
View Answer
Answer: a
Explanation: Because front represents the deleted nodes.
8. The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
View Answer
Answer: b
Explanation: To check whether there is space in the queue or not.
9. The essential condition which is checked before deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
View Answer
Answer: a
Explanation: To check whether there is element in the list or not.
10. Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop
operation, nodes must be removed from end
b) In push operation, if new nodes are inserted at the beginning, then in pop operation,
nodes must be removed from the beginning
c) In push operation, if new nodes are inserted at the end, then in pop operation, nodes
must be removed from end
d) In push operation, if new nodes are inserted at the end, then in pop operation, nodes
must be removed from beginning
View Answer
Answer: a
Explanation: It can be done by both the methods.