Explore topic-wise InterviewSolutions in .

The CORRECT answer is (a) Because of its time complexity O(N)

The explanation is: To perform Queue operations such as enQueue and deQueue there is a need of EMPTYING all the elements of a current stack and pushing elements into the NEXT stack and vice versa. Therfore it has a time complexity of O(n) and the need of extra stack as well, may not be FEASIBLE for a large dataset.

Right option is (c) O(n)

The explanation is: In the WORST CASE, you MIGHT have to TRAVERSE the ENTIRE list.

The correct answer is (d) EASY to DELETE elements in any case

For explanation: In worst case, the entire QUEUE has to be searched for the element having the HIGHEST priority. This will take more time than usual. So deletion of elements is not an ADVANTAGE.

The CORRECT ANSWER is (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

The best explanation: It can be done by both the METHODS.

Correct OPTION is (a) Underflow

Explanation: To CHECK WHETHER there is element in the LIST or not.

The CORRECT answer is (b) Overflow

Explanation: To CHECK WHETHER there is space in the queue or not.

Correct ANSWER is (a) At the head of link list

Easy explanation - SINCE QUEUE follows FIFO so NEW element deleted from first.

The CORRECT choice is (a) AVAIL

The BEST I can explain: All the NODES are collected in AVAIL list.

Correct choice is (c) Both FRONT and rear pointer

To EXPLAIN: SINCE its the STARTING of queue, so both values are changed.

Right option is (C) At the tail of the LINK list

The explanation is: SINCE QUEUE FOLLOWS FIFO so new element inserted at last.

Correct choice is (c) 1

Easy EXPLANATION - Use ONE queue and one counter to COUNT the number of ELEMENTS in the queue.

Right CHOICE is (c) EMPTYSTACKEXCEPTION is thrown

For EXPLANATION: The Stack ADT THROWS an EmptyStackException if the stack is empty and a pop() operation is tried on it.

Right ANSWER is (B) S[N]

Explanation: ELEMENTS are pushed at the end, HENCE N.

The correct answer is (a) O(1)

The BEST I can explain: pop() accesses only one END of the structure, and HENCE CONSTANT time.

Correct option is (a) piling up of chairs one above the other

Best explanation: Stack follows Last In First Out (LIFO) POLICY. Piling up of chairs one above the other is based on LIFO, people standing in a line is a queue and if the service is based on priority, then it can be associated with a priority queue. Tatkal Ticket Booking Follows First in First Out Policy. People who CLICK the book now first will enter the booking page first.

Correct choice is (b) Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one NODE at a time

Best EXPLANATION: Advance the pointers in such a WAY that the fast pointer advances two nodes at a time and slow pointer advances one node at a time and check to see if at any given instant of time if the fast pointer points to slow pointer or if the fast pointer’s ‘next’ points to the slow pointer. This is applicable for smaller LISTS.

Right choice is (c) Delete the last element of the list

Explanation: Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer.

Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the GIVEN linked list. The head pointer was changed to a newly created node.

Deletion of the last element requires a pointer to the previous node of last, which can only be OBTAINED by traversing the list. This requires the length of the linked list.

Adding a NEW element at the END of the list can be done in O (1) by changing the pointer of the last node to the newly created node and last is changed to a newly created node.

Correct OPTION is (a) POSSIBLE if X is not last node

The best EXPLANATION: FOLLOWING are simple steps.

The correct option is (d) Merge Sort

Best EXPLANATION: Both Merge sort and Insertion sort can be used for linked lists. The SLOW random-access PERFORMANCE of a linked list makes other algorithms (such as quicksort) perform poorly, and others (such as HEAPSORT) completely impossible. Since worst CASE time complexity of Merge Sort is O(nLogn) and Insertion sort is O(n^2), merge sort is preferred.

The correct answer is (c) SPACE Utilization and COMPUTATIONAL Time

Easy EXPLANATION - LINKED lists saves both space and time.

Correct answer is (c) DATA and LINK

Best explanation: A LINKED list is a collection of objects linked together by references from an object to ANOTHER object. By convention these objects are names as nodes. Linked list consists of nodes where each node contains one or more data fields and a reference(link) to the next node.

Right option is (d) Array implementation of linked LIST

To explain: Arrays PROVIDE random access to elements by providing the index VALUE within square brackets. In the linked list, we need to traverse through each element until we reach the nth position. Time taken to access an element represented in arrays is less than the singly, doubly and circular linked LISTS. Thus, array implementation is USED to access the item at the position n.

The correct ANSWER is (c) CIRCULAR doubly linked LIST

Best explanation: We can easily concatenate two LISTS in O (1) time using singly or doubly linked list, provided that we have a pointer to the last node at least one of the lists. But in case of circular doubly linked lists, we will break the link in both the lists and hook them together. Thus circular doubly linked list concatenates two lists in O (1) time.

Right OPTION is (a) O(1)

For explanation: A new node is created with the required ELEMENT. The pointer of the new node points the node to which the HEAD node of the linked list is also pointing. The head node pointer is changed and it points to the new node which we created earlier. The ENTIRE process completes in O (1) time. Thus the asymptotic time complexity to insert an element in the second position of the linked list is O (1).

Correct ANSWER is (B) O(n)

For explanation: If the required ELEMENT is in the last POSITION, we need to traverse the ENTIRE linked list. This will take O (n) time to search the element.

The correct OPTION is (a) O(1)

To explain: To add an element at the front of the LINKED list, we will CREATE a new node which holds the data to be added to the linked list and pointer which points to head POSITION in the linked list. The entire thing happens within O (1) time. Thus the asymptotic time complexity is O (1).

Right choice is (C) θ(n)

Best explanation: In CASE of a linked LIST having n elements, we need to travel through every node of the list to add the element at the end of the list. Thus asymptotic time COMPLEXITY is θ(n).

Right OPTION is (C) Pointer to NODE

The best I can explain: Each node in a linked list CONTAINS DATA and a pointer (reference) to the next node. Second field contains pointer to node.

The correct option is (a) Linked list

The BEST explanation: In Linked list each node has its own data and the address of NEXT node. These nodes are linked by USING pointers. Node list is an object that consists of a list of all nodes in a document with in a PARTICULAR SELECTED set of nodes.

The CORRECT choice is (B) Single ended queue

To EXPLAIN: Queue always has TWO ends. So, single ended queue is not the type of queue.

Correct choice is (c) Simulation of LIMITED RESOURCE allocation

The explanation is: Simulation of recursion uses stack data structure. Simulation of arbitrary linked lists uses linked lists. Simulation of resource allocation uses queue as first entered data needs to be GIVEN first PRIORITY during resource allocation. Simulation of heap SORT uses heap data structure.

Correct ANSWER is (a) Rear = MAX_SIZE – 1

Easy explanation - When Rear = MAX_SIZE – 1, there will be no space LEFT for the elements to be added in QUEUE. Thus queue BECOMES full.

Correct answer is (C) Dequeue

The best I can EXPLAIN: In dequeuer, we can INSERT or delete elements from both the ends. In queue, we will follow first in first out principle for insertion and deletion of elements. Element with LEAST priority will be DELETED in a priority queue.

Right answer is (a) ABCD

The BEST I can explain: Queue FOLLOWS FIFO approach. i.e. First in First Out Approach. So, the order of removal elements are ABCD.

The CORRECT choice is (a) Ring BUFFER

Explanation: Circular Queue is also called as Ring Buffer. Circular Queue is a linear data STRUCTURE in which last position is connected BACK to the first position to make a circle. It forms a ring structure.

Right CHOICE is (c) Queue

Best explanation: In Breadth First Search TRAVERSAL, BFS, starting vertex is first TAKEN and adjacent vertices which are UNVISITED are also taken. Again, the first vertex which was added as an unvisited adjacent vertex list will be considered to add further unvisited vertices of the graph. To get the first unvisited vertex we need to follows First In First Out PRINCIPLE. Queue uses FIFO principle.

The correct option is (a) Queue

For explanation: Linear LIST of ELEMENTS in which deletion is done at front SIDE and INSERTION at rear side is called Queue. In stack we will delete the LAST entered element first.

The correct choice is (c) Postfix Expression

The EXPLANATION is: The expression in which OPERATOR succeeds its operands is called postfix expression. The expression in which operator precedes the operands is called prefix expression. If an operator is present between two operands, then it is called INFIX EXPRESSIONS.