YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS
Data Structure Questions and Answers-Binary Trees using Array
Question 6 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
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?
every node stores data saying which of its children exist in the array | |
no need of any changes continue with 2w and 2w+1, if node is at i | |
keep a seperate table telling children of a node | |
use another array parallel to the array with tree |
Question 6 Explanation:
Array cannot represent arbitrary shaped trees it can only be used in case of complete trees hence option a must be done which is one of several ways to use array in such situations.
Question 7 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
What must be the missing logic in place of missing lines for finding sum of nodes of 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;) { for(j=1;j<=pow(2, currentlevel-1);j++) //present level is initialized to 1 and sum is initialized to 0 { sum=sum+a[i]; i=i+1; } //missing logic }
i=i+pow(2, currentlevel); currentlevel=currentlevel+2; j=1; | |
i=i+pow(2, currentlevel); currentlevel=currentlevel+2; j=0; | |
i=i-pow(2, currentlevel); currentlevel=currentlevel+2; j=1; | |
i=i+pow(2, currentlevel); currentlevel=currentlevel+1; j=1; |
Question 7 Explanation:
The i value must skip through all nodes in the next level and current level must be one+next level.
Question 8 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is array representation of tree is good?
yes because we are overcoming the need of pointers and so space efficiency | |
yes because array values are indexable | |
No it is not efficient in case of sparse trees and remaning cases it is fine | |
No linked list representation of tree is only fine |
Question 8 Explanation:
In case of sparse trees(where one node per level in worst cases), the array size (2h)-1 where h is height but only h indexes will be filled and (2h)-1-h nodes will be left unused leading to space wastage which was actually main theme of question.
Question 9 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
Why is heap implemented using array representations than tree(linked list) representations though both tree representations and heaps have same complexities?
for binary heap -insert: O(log n) -delete min: O(log n) for a tree -insert: O(log n) -delete: O(log n)
Then why go with array representation when both are having same values?
arrays can store trees which are complete and heaps are by it's property are complete | |
lists representation takes more memory hence memory efficiency is less and go with arrays | |
array have better caching | |
all of the mentioned |
Question 9 Explanation:
In memory the pointer address for next node may not be adjacent or nearer to each other and also array have wonderful caching power from os and manipulating pointers is a overhead.
Question 10 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed?
yes just traverse through the array and form the tree | |
No we need one more traversal to form a tree | |
No in case of sparse trees | |
None of the mentioned |
Question 10 Explanation:
We need any two traversals for tree formation but if some additional stuff or techniques are used while storing a tree in an array then one traversal can facilitate like also storing null values of a node in array.
There are 10 questions to complete.