gs gs121 Binary Trees - Binary Trees using Array - Quiz No.1
gs gs121 Data Structures and Algorithms Quiz
This quiz belongs to book/course code gs gs121 Data Structures and Algorithms of gs organization. We have 169 quizzes available related to the book/course Data Structures and Algorithms. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Binary Trees. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: How many children does a binary tree have?
2
any number of children
0 or 1 or 2
0 or 1
Question 2: What is/are the disadvantages of implementing tree using normal arrays?
difficulty in knowing children nodes of a node
difficult in finding the parent of a node
have to know the maximum number of nodes possible before creation of trees
difficult to implement
Question 4: What are the children for node ‘w’ of a complete-binary tree in an array representation?
2w and 2w+1
2+w and 2-w
w+1/2 and w/2
w-1/2 and w+1/2
Question 5: What is the parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0?
floor(w-1/2)
ceil(w-1/2)
w-1/2
w/2
Question 6: 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 7: 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;) { //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 } 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 8: 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 9: 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 not complete
lists representation takes more memory hence memory efficiency is less and go with arrays and arrays have better caching
lists have better caching
In lists insertion and deletion is difficult
Question 10: 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
Yes by using both inorder and array elements
Online Quizzes of gs121 Data Structures and Algorithms
Binary Trees - Binary Search Tree - Quiz No.1
gs gs121
Data Structures and Algorithms Online Quizzes
Binary Trees - Binary Search Tree - Quiz No.2
gs gs121
Data Structures and Algorithms Online Quizzes
Binary Trees - Preorder Traversal - Quiz No.1
gs gs121
Data Structures and Algorithms Online Quizzes
