1. Array implementation of Stack is not dynamic, which of the following statements supports this argument?
a) space allocation for array is fixed and cannot be changed during run-time
b) user unable to give the input for stack operations
c) a runtime exception halts execution
d) improper program compilation
Explanation: You cannot modify the size of an array once the memory has been allocated, adding fewer elements than the array size would cause wastage of space, and adding more elements than the array size at run time would cause Stack Overflow.
2. 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)
Explanation: Deletion of the head node in the linked list is taken as the best case. The successor of the head node is changed to head and deletes the predecessor of the newly assigned head node. This process completes in O(1) time.
3. 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
Explanation: To insert and delete at known positions requires complete traversal of the list in worst case in SLL, SLL consists of an item and a node field, while DLL has an item and two node fields, hence SLL occupies lesser memory, DLL can be traversed both ways(left and right), while SLL can traverse in only one direction, hence more searching power of DLL. Node fields in SLL is 2 (data and address of next node) whereas in DLL is 3(data, address to next node, address to previous node).
4. 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
Explanation: Adding items to a full stack is termed as stack overflow.
5. Which of the following data structures can be used for parentheses matching?
a) n-ary tree
b) queue
c) priority queue
d) stack
Explanation: For every opening brace, push it into the stack, and for every closing brace, pop it off the stack. Do not take action for any other character. In the end, if the stack is empty, then the input has balanced parentheses.
6. Minimum number of queues to implement stack is ___________
a) 3
b) 4
c) 1
d) 2
Explanation: Use one queue and one counter to count the number of elements in the queue.
7. 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.
8. 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).
9. 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.
10. 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.