1. Which of the following properties is associated with a queue?
a) First In Last Out
b) First In First Out and Last in Last Out
c) Last In First Out
d) Last In Last Out Only
Answer: b
Explanation: A queue follows the First In First Out (FIFO) structure, meaning the first element inserted will be the first one to be removed. This is different from Last In Last Out (LIFO), which is the characteristic of a stack. Therefore, FIFO is not the same as LIFO.
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–
Answer: b
Explanation: In a circular queue, the rear pointer is managed in such a way that it loops back to the beginning once it reaches the maximum capacity. This ensures that the rear takes values from 0 to (CAPACITY – 1), making efficient use of the available space in the queue and preventing overflow when there is free space at the front of the queue.
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
Answer: a
Explanation: Just like in a stack, when you try to insert an element into a queue that is already full, it is termed overflow. This occurs when there is no available space to add more elements to the queue, and it exceeds the maximum capacity.
4. What is the time complexity of enqueue operation?
a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)
Answer: d
Explanation: The enqueue operation in a queue adds an element at the rear end. This operation takes O(1) time because it involves directly inserting the new element at the end without needing to shift other elements, making it a constant time operation.
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
Answer: c
Explanation: The operation q[front] accesses the element at the front of the queue without removing it. Since we are not moving the front pointer to the next element, it does not perform a dequeue operation, it merely retrieves the value at the front of the queue.
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
Answer: a
Explanation: In a linear queue, after performing a dequeue operation, the space at the front of the queue becomes unused, leading to inefficient space utilization. In contrast, a circular queue reuses this space by allowing the rear to wrap around to the beginning once space becomes available, making it more efficient. A priority queue, however, is not related to circular or linear queues; it deletes elements based on their priority, with higher priority elements being removed first. A regular queue always follows the FIFO (First In, First Out) 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--;
}
}
Answer: a
Explanation: The dequeue operation removes the element at the front of the queue. In a queue, the front pointer references the first element. When dequeue is called, the element at front is removed, and the front pointer is updated to the next element, maintaining the FIFO (First In, First Out) principle. This ensures that elements are processed in the order they were added to the queue.
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;
}
Answer: a
Explanation: A common technique to expand the size of a queue when it becomes full is to double the size of the array. This involves creating a new array with double the previous size and copying all the elements from the old array to the new one. After copying, it’s important to reset the front pointer to 0 and adjust the rear pointer to size() - 1 to maintain the correct positions for future enqueue and dequeue operations. This resizing technique ensures that the queue can handle more elements as needed.
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)
Answer: a
Explanation: The space complexity of a linear queue is determined by the amount of space required to store the elements. Since the queue holds n elements, the space complexity is proportional to the number of elements, which is O(n). This includes the space used by the input elements stored in the queue. The space complexity does not account for auxiliary space or other operational factors beyond the storage of elements in the queue.
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
Answer: a
Explanation:
The sequence of operations is as follows:
- Enqueue(10): Adds 10 to the queue.
- Enqueue(3): Adds 3 to the queue.
- Dequeue(): Removes 10 from the queue, so 3 is now at the front.
- Enqueue(6): Adds 6 to the queue, making it the rear element.
After these operations, the queue looks like: [3, 6]. Calling frontElement() will return 3, which is the current front of the queue. Since frontElement() is called twice, it will print 3 both times.