Digital Globalsoft Placement Paper - Data Structure Questions And Answers

Digital Globalsoft Previous Years Solved Sample Placement Papers

1. If the tree is not a complete binary tree, then what changes can be made for easy access of children of a node in the array?

   A) Every node stores data saying which of its children exist in the array (Ans)

   B) No need of any changes, continue with 2w and 2w+1 if the node is at i

   C) Keep a separate table telling children of a node

   D) Use another array parallel to the array with the tree

2. What must be the missing logic in place of missing lines for finding the sum of nodes of a binary tree in alternate levels?

   //e.g: consider complete binary tree: height-3, [1,2,3,4,5,6,7] - answer must be 23

   n = power(2, height) - 1; // assume input is height and a[i] contains tree elements

   for(i = 1; i <= n;)

   {

   // present level is initialized to 1 and sum is initialized to 0

   for(j = 1; j <= pow(2, currentlevel - 1); j++)

   {

   sum = sum + a[i];

   i = i + 1;

   }

   // missing logic

   }

   A) i = i + pow(2, currentlevel); currentlevel = currentlevel + 2; j = 1; (Ans)

   B) i = i + pow(2, currentlevel); currentlevel = currentlevel + 2; j = 0;

   C) i = i - pow(2, currentlevel); currentlevel = currentlevel + 2; j = 1;

   D) i = i + pow(2, currentlevel); currentlevel = currentlevel + 1; j = 1;

3. Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is array representation of a tree good?

   A) Yes, because we are overcoming the need for pointers and so space efficiency

   B) Yes, because array values are indexable

   C) No, it is not efficient in case of sparse trees, and remaining cases it is fine (Ans)

   D) No, linked list representation of tree is only fine

4. Why is the heap implemented using array representations rather than tree (linked list) representations though both have the same complexities?

   A) Arrays can store trees that are complete and heaps are not complete

   B) List representation takes more memory, hence memory efficiency is less. Go with arrays because arrays have better caching (Ans)

   C) Lists have better caching

   D) In lists, insertion and deletion are difficult

5. Can a tree stored in an array using either one of inorder, postorder, or preorder traversals be reformed?

   A) Yes, just traverse through the array and form the tree

   B) No, we need one more traversal to form a tree (Ans)

   C) No, in case of sparse trees

   D) Yes, by using both inorder and array elements