Reliance Jio Data Structure Quiz-1

Key Differences Between Array and Linked List
1. An array is the data structure that contains a collection of similar type data elements whereas the Linked list is considered as non-primitive data structure contains a collection of unordered linked elements known as nodes.
2. In the array the elements belong to indexes, i.e., if you want to get into the fourth element you have to write the variable name with its index or location within the square bracket.
3. In a linked list though, you have to start from the head and work your way through until you get to the fourth element.
4. Accessing an element in an array is fast, while Linked list takes linear time, so it is quite a bit slower.
5. Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.

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.

In the worst case, the element to be searched has to be compared with all elements of linked list.

For getting intersection of L1 and L2, search for each element of L1 in L2 and print the elements we find in L2. There can be many ways for getting union of L1 and L2. One of them is as follows a) Print all the nodes of L1 and print only those which are not present in L2. b) Print nodes of L2. All of these methods will require more operations than intersection as we have to process intersection node plus other nodes.

Currently there is no PrepInsta Explanation. Did you know?

You can also submit your own version of explanations under user explanation section and also view other submitted explanations by other users.

To keep the Last In First Out order, a stack can be implemented using linked list in two ways: a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from beginning. b) In push operation, if new nodes are inserted at the end of linked list, then in pop operation, nodes must be removed from end.

If we are to use space efficiently then size of the any stack can be more than MAXSIZE/2. Both stacks will grow from both ends and if any of the stack top reaches near to the other top then stacks are full. So the condition will be top1 = top2 -1 (given that top1 < top2)

Any expression can be converted into Postfix or Prefix form.
Prefix and postfix evaluation can be done using a single stack.
For example : Expression '10 2 8 * + 3 -' is given. PUSH 10 in the stack. PUSH 2 in the stack. PUSH 8 in the stack. When operator '*' occurs, POP 2 and 8 from the stack. PUSH 2 * 8 = 16 in the stack. When operator '+' occurs, POP 16 and 10 from the stack. PUSH 10 * 16 = 26 in the stack. PUSH 3 in the stack. When operator '-' occurs, POP 26 and 3 from the stack. PUSH 26 - 3 = 23 in the stack. So, 23 is the answer obtained using single stack.

A queue can be implemented using two stacks.

If the queue is implemented with a linked list, keeping track of a front pointer, Only rear pointer s will change during an insertion into an non-empty queue. Queue data structure can be used to implement least recently used (LRU) page fault algorithm and Quick short algorithm. Only option (C) is not correct.

An array of size 50 looks the best option to store number of students for each score. We need to store frequencies of scores above 50. We can ignore scores below 50 and to index the scores above 50, we can subtract 50 from the score value/

The worst case time complexity for deleting an element from array can become O(n).

Here we can use the partition algorithm of quick sort for segregation and answer will be N-1.
Choose the first element as pivot whatever may be its sign we don’t care and keep an extra index at pivot position .

In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node other node b in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed in an O(1) operation one may determine that node c is reachable from node a.

In an undirected graph, there can be maximum n(n-1)/2 edges. We can choose to have (or not have) any of the n(n-1)/2 edges. So, total number of undirected graphs with n vertices is 2^(n(n-1)/2).

The order of inorder traversal is LEFT ROOT RIGHT The order of preorder traversal is ROOT LEFT RIGHT The order of postorder traversal is LEFT RIGHT ROOT In all three traversals, LEFT is traversed before RIGHT

Below is the given tree.

                              a

                           /    \

                        /          \

                      b             c

                   /   \          /   \

                 /       \      /       \

               d         e    f          g

Breadth first search visits all the neighbors first and then deepens into each neighbor one by one. The level order traversal of the tree also visits nodes on the current level and then goes to the next level.

We can write the prefix form of the expression as: (a + (b − c))* ((d − e) / (f + g − h)) = (a + (- b c)) * ((- d e) / ( + f g - h)) = (+ a - b c) * ((- d e) / (- + f g h) = (+ a - b c) * (/ - d e - + f g h) = * + a - b c / - d e - + f g h