1. What is a dequeue?
a) A queue with insert/delete defined for both front and rear ends of the queue
b) A queue implemented with a doubly linked list
c) A queue implemented with both singly and doubly linked lists
d) A queue with insert/delete defined for front side of the queue
Answer: a
Explanation: A deque (double-ended queue) is a data structure that allows insertion and deletion of elements from both the front and rear ends. Unlike a regular queue, which follows FIFO (First In, First Out) and allows operations only at the front for dequeueing and at the rear for enqueueing, a deque allows more flexibility in managing elements.
2. Select the function which performs insertion at the front end of the dequeue?
a)
public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
temp.setNext(trail);
head.setNext(temp);
}
else
{
Node cur = head.getNext();
temp.setNext(cur);
head.setNext(temp);
}
size++;
}
b)
public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
temp.setNext(trail);
head.setNext(trail);
}
else
{
Node cur = head.getNext();
temp.setNext(cur);
head.setNext(temp);
}
size++;
}
c)
public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
Node cur = head.getNext();
temp.setNext(cur);
head.setNext(temp);
}
else
{
temp.setNext(trail);
head.setNext(temp);
}
size++;
}
d)
public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
Node cur = head.getNext();
temp.setNext(cur);
cur.setNext(temp);
}
else
{
head.setNext(trail);
trail.setNext(temp);
}
size++;
}
Answer: a
Explanation: To insert a new node at the front of a linked list, first create the new node. If the list is empty, the head pointer should point to this new node. If the list is not empty, the head pointer should be updated to point to the new node, and the new node’s next pointer should point to the current first node (i.e., the existing head). This operation effectively adds the new node to the front of the list.
3. What is the functionality of the following piece of code?
public void function(Object item)
{
Node temp=new Node(item,trail);
if(isEmpty())
{
head.setNext(temp);
temp.setNext(trail);
}
else
{
Node cur=head.getNext();
while(cur.getNext()!=trail)
{
cur=cur.getNext();
}
cur.setNext(temp);
}
size++;
}
a) Insert at the front end of the dequeue
b) Insert at the rear end of the dequeue
c) Fetch the element at the rear end of the dequeue
d) Fetch the element at the front end of the dequeue
Answer: b
Explanation: To insert a new node at the end of the linked list, first check if the list is empty. If it is, the new node’s next pointer will point to trail, and the head will point to this new node. If the list is not empty, traverse to the last node, update the last node’s next pointer to point to the new node, and set the new node’s next pointer to trail. This ensures the new node is inserted at the end of the list.
4. What are the applications of dequeue?
a) A-Steal job scheduling algorithm
b) Can be used as both stack and queue
c) To find the maximum of all sub arrays of size k
d) All of the mentioned
Answer: d
Explanation: A deque (double-ended queue) allows insertion and deletion from both ends—front and rear. This flexibility makes it useful for implementing various data structures such as:
- Stack: By inserting and deleting from one end.
- Queue: By inserting at one end and deleting from the other end.
- Priority Queue: By manipulating the ends based on priority.
Thus, all the mentioned data structures can be implemented using a deque, which makes it versatile for different scenarios.
5. Which of the following can be used to delete an element from the front end of the queue?
a)
public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp;
Object e = temp.getEle();
head.setNext(cur);
size--;
return e;
}
}
b)
public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp.getNext();
Object e = temp.getEle();
head.setNext(cur);
size--;
return e;
}
}
c)
public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp.getNext();
Object e = temp.getEle();
head.setNext(temp);
size--;
return e;
}
}
d)
public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp.getNext();
Object e = temp.getEle();
temp.setNext(cur);
size--;
return e;
}
}
Answer: b
Explanation: To delete the first element of a singly linked list, we use two pointers: one pointer (temp) points to the first element, and the other pointer (cur) points to the second element. By changing the head to point to the second element (cur), the first element is effectively removed from the list. The temp pointer will no longer be referenced, so it becomes eligible for garbage collection. This operation takes constant time, O(1).
6. Which of the following can be used to delete an element from the rear end of the queue?
a)
public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp;
while(temp.getNext() != trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}
b)
public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = head;
while(temp != trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}
c)
public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = head;
while(temp.getNext()!=trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}
d)
public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = head;
while(temp.getNext()!=trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
temp.setNext(trail);
size--;
return e;
}
}
Answer: c
Explanation: To delete the last node in a singly linked list, traverse to the end of the list using a pointer temp and a trailing pointer cur that follows temp. When temp reaches the last node, set cur.next to null, effectively removing the reference to the last node. This makes the last node eligible for garbage collection. This operation requires traversing the entire list, so its time complexity is O(n).
7. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: c
Explanation: In a singly linked list, to delete the last node, you first need to traverse the entire list to find the second-to-last node. Once you reach the second-to-last node, you can set its next pointer to null, removing the reference to the last node. This requires iterating through the list, making the time complexity O(n), where n is the number of nodes in the list.
8. After performing these set of operations, what does the final list look contain?
InsertFront(10); InsertFront(20); InsertRear(30); DeleteFront(); InsertRear(40); InsertRear(10); DeleteRear(); InsertRear(15); display();
a) 10 30 10 15
b) 20 30 40 15
c) 20 30 40 10
d) 10 30 40 15
Answer: d
Explanation: Let’s carefully trace the sequence of operations:
- Insert 10: The list becomes
10. - Insert 20: The list becomes
20 -> 10. - Insert 30: The list becomes
20 -> 10 -> 30. - Delete 20: The first element (20) is removed. The list becomes
10 -> 30. - Insert 40: The list becomes
10 -> 30 -> 40. - Insert 10 again: The list becomes
10 -> 30 -> 40 -> 10. - Delete 30: The element 30 is removed. The list becomes
10 -> 40 -> 10. - Insert 15: The list becomes
10 -> 40 -> 10 -> 15.
Thus, the final list after these operations is 10 -> 30 -> 40 -> 15, corresponding to option d.