Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Queue using Array

1 - Question

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

Explanation: Queue follows First In First Out structure.

2 - Question

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–

Explanation: Ensures rear takes the values from 0 to (CAPACITY-1).

3 - Question

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

Explanation: Just as stack, inserting into a full queue is termed overflow.

4 - Question

What is the time complexity of enqueue operation?
a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)

Explanation: Enqueue operation is at the rear end, it takes O(1) time to insert a new item into the queue.

5 - Question

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

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 - Question

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

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 - Question

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--;
}
}```

Explanation: Dequeue removes the first element from the queue, ‘front’ points to the front end of the queue and returns the first element.

8 - Question

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;
}```

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 - Question

What is the space complexity of a linear queue having n elements?
a) O(n)
b) O(nlogn)
c) O(logn)
d) O(1)

Explanation: Because there are n elements.

10 - Question

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