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)
Answer: d
Explanation: Deleting the head node of a linked list is considered the best case in terms of time complexity because it involves constant-time operations. When the head node is deleted, the head pointer is updated to point to the next node in the list, and the predecessor of the newly assigned head is removed. No traversal of the list is required, as only the reference of the head node is changed and the node is deallocated. Hence, the time complexity of this operation is O(1).
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
Answer: d
Explanation: In a Singly Linked List (SLL), each node contains two fields: the data and the address of the next node. This allows traversal in only one direction (from head to tail). On the other hand, a Doubly Linked List (DLL) has three fields in each node: the data, the address of the next node, and the address of the previous node. This additional pointer in DLL allows traversal in both directions (left and right), making it more flexible and powerful for certain operations like bidirectional searching and easier deletion of nodes when the previous node is known.
However, DLL nodes require more memory (due to the extra pointer), and insertion/deletion at known positions may still require traversal in the worst case. Thus, DLL offers more search power due to its bidirectional traversal, but it also consumes more memory compared to SLL.
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;
}
}
Answer: a
Explanation: The pop() operation in a stack is responsible for removing and returning the element at the top of the stack. To implement pop(), the sequence of operations is as follows:
Get the element stored at the node pointed to by the first node using getEle(). This retrieves the data of the topmost node.
Update the stack by making the first node point to the next node using getNext(). This removes the top node from the stack and makes the next node the new top. This ensures that the stack follows the Last In, First Out (LIFO) principle, where the most recently added element is the first to be removed.
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
Answer: c
Explanation: The provided code only retrieves the top element of the stack, but it does not perform the full pop operation. In a typical pop() operation, the stack element at the top must not only be retrieved but also removed by updating the next pointer of the current top node to point to the next node. However, in the given code, it seems that only the data at the top of the stack is being accessed without modifying the next pointer or removing the top element from the stack, making it incomplete. Therefore, the code only returns the top element but doesn’t update the stack, which is not equivalent to a pop operation.
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
Answer: b
Explanation: An alias of the ‘first’ node is created to traverse the list and display each element without modifying the stack. This allows the stack elements to be printed in sequence.
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
Answer: b
Explanation: Stack underflow occurs when an attempt is made to remove an item from an empty stack, not when trying to add an item to a full stack. If you try to pop an item from an empty stack, it results in underflow, indicating that the stack is empty and no elements are available to be removed.
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++;
}
Answer: a
Explanation: To push an element onto the stack, a new node is created. The next pointer of this new node is set to point to the current top-of-the-stack (i.e., the node referred to by ‘first’). Then, the new node becomes the new top of the stack by assigning it to ‘first’. This ensures the stack follows the Last In, First Out (LIFO) principle.
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(); push(5); top();
a) 20
b) 4
c) stack underflow
d) 5
Answer: d
Explanation: The pop() operations remove the elements 20 and 4 from the stack. The last element pushed onto the stack is 5. Therefore, when top() is called, it returns 5, as it is the current top element of the stack.
9. Which of the following data structures can be used for parentheses matching?
a) n-ary tree
b) queue
c) priority queue
d) stack
Answer: d
Explanation: For every opening brace (‘{‘, ‘[‘, ‘(‘), push it onto the stack. For every closing brace (‘}’, ‘]’, ‘)’), pop the matching opening brace from the stack. If at the end the stack is empty, it means all parentheses were properly matched and the input has balanced parentheses. If the stack is not empty, there are unmatched parentheses.
10. Minimum number of queues to implement stack is ___________
a) 3
b) 4
c) 1
d) 2
Answer: c
Explanation: To count the number of elements in a queue, you can use a single queue and a counter variable. Each time an element is enqueued, increment the counter, and each time an element is dequeued, decrement the counter. This allows you to efficiently track the number of elements in the queue without needing additional data structures.