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
Answer: d
Explanation: The worst-case scenario in a queue typically happens when elements need to be shifted, especially in non-circular implementations. Thus, operations like enqueue, dequeue, and front can all have O(n) time complexity in such 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
Answer: c
Explanation: A queue follows the FIFO (First In, First Out) principle, meaning that new elements are inserted at the rear and removed from the front. Thus, the most recent element is always at the rear.
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
Answer: b
Explanation: In a queue, which follows the FIFO (First In, First Out) principle, new elements are always inserted at the rear (last) of the queue, not the front. This ensures that elements are processed in the order they are added.
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
Answer: c
Explanation: When the queue is initially empty, both the front and rear pointers need to be updated to point to the newly inserted element. Therefore, both values are changed at the start.
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
Answer: a
Explanation: In the context of memory management or node reuse, all the nodes that are freed or no longer in use are collected in an “AVAIL” list. This list stores nodes that can be reused when needed, helping to efficiently manage memory by reusing previously allocated nodes.
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
Answer: a
Explanation: In a queue, the FIFO (First In, First Out) principle is followed. This means that the element which was added first will be the first to be removed. Therefore, when a dequeue operation is performed, the element at the front of the queue is deleted.
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
Answer: a
Explanation: In a queue, the front pointer indicates the position of the element that was first inserted and is the next one to be deleted. Therefore, elements are dequeued from the front, making the front pointer represent the nodes being removed.
8. The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
Answer: b
Explanation: The isFull() function is used to check whether there is space available in the queue. It returns true if the queue is full, meaning no more elements can be added, and false if there is space to enqueue new elements.
9. The essential condition which is checked before deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
Answer: a
Explanation: The isEmpty() function is used to check if the queue contains any elements. It returns true if the queue is empty, meaning there are no elements to dequeue, and false if the queue has one or more elements.
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
Answer: a
Explanation: The operation can be performed by both methods, depending on the implementation of the queue. You can use either an array-based queue or a linked list-based queue to implement the enqueue and dequeue operations. Both data structures support these operations, though the details of the implementation differ.