Data Structure and Algorithm Analysis Set 8

Data Structure and Algorithm Analysis

Questions 71 to 80

71.
The Following is a binary tree. Answer questions (11 – 13) considering the below given tree.

The In-order traversal of the above tree is
 (a) H D E B F I J G C A (b) D H B E A F C I G J (c) A B D H E C F G I J (d) H D B E A F C I G J (e) D H B E A I G J F C.
72.
The Pre-order traversal for the tree in question -11 is
 (a) A B D H E C F G J I (b) A B D E H C F G I J (c) D H B E A F C I G J (d) A B D H E C F G I J (e) H D E B F I J G C A.
73.
The Post-order traversal for the tree in question -11 is
 (a) H D E B I J G F C A (b) D H B E A F C I G J (c) H D E B F I J G C A (d) H D E B F I J G A C (e) A B D H E C F G I J.
74.
There are four trees named A, B, C and D having 8, 15, 13, 14 nodes in them respectively. Which of them could have formed a full binary tree?
 (a) A (b) B (c) C (d) D (e) No any tree can be a full binary tree.
75.
In the given binary tree if the nodes are stored in an array, then where the node 4 can be stored?

 (a) At location 6 (b) At location 5 (c) At location 4 (d) At location 3 (e) Can’t be stored at any location.
76.
Of the following tree structure, which is efficient, considering space and time complexities?
 (a) Incomplete Binary Tree (b) Complete Binary Tree (c) Full Binary Tree (d) Binary Search Tree (e) AVL Tree.
77.
Consider the following two statements and choose the correct option:
I.     According to Access strategies Linked List is a linear one.
II.     According to Storage Linked List is a Non-linear one.
 (a) (I) is true but (II) is false (b) (I) is false but (II) is true (c) Both (I) and (II) are true (d) Both (I) and (II) are false (e) Can’t be determined.
78.
Which of the following are differences between structures and arrays?
 (a) Structures and arrays use different operators to access their elements (b) Structures are not limited to containing variables of a single data type (c) Structures can contain elements that are pointers but arrays not (d) Structures are passed by value while arrays are passed by reference (e) Structures and arrays contains the different elements.
79.
Which of the following pairs of statements are identical?
 (a) (*ptr) àelement AND ptr.element (b) *ptr.element AND ptràelement (c) *ptràelement AND ptr.element (d) *(ptr.element) AND ptràelement (e) (*ptr).element AND ptràelement.
80.
A "stack" is also known as what?
 (a) A FIFO (b) A Queue (c) A LIFO (d) A Linked List (e) A FOLI.

71.
Reason : Because the rules for traversing the binary tree in In-order are:
i.            Traverse the left sub tree in In-order
ii.     Traverse the root
iii.    Traverse the right sub tree in In-order
72.
Reason : Because the rules for traversing the binary tree in Pre-order are:
i.            Traverse the root
ii.     Traverse the left sub tree in Pre-order
iii.    Traverse the right sub tree in Pre-order
73.
Reason : Because the rules for traversing the binary tree in Post-order are:
i.            Traverse the left sub tree in Post-order
ii.     Traverse the right sub tree in Post-order
iii.    Traverse the root
74.
Reason : In general there are 2n-1 nodes in a full binary tree.
By the method of elimination: Full binary trees contain odd number of nodes. So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13 nodes you can form a complete binary tree but not a full binary tree. So the correct answer is 15.
75.
Reason : At location  6
 1 2 3 - - 4 - - 5 Root 1 LC1 2 RC1 3 LC2 4 RC2 5 LC3 6 RC3 7 LC4 8 RC4 9
where LCn means Left Child of node ‘n’ and RCn means Right Child  of node ‘n’. Top row represents the node values and bottom row represents the positions.
76.
Reason : Complete Binary Tree.
By the method of elimination: Full binary tree loses its nature when operations of insertions and deletions are done. For incomplete binary trees, extra storage is required and overhead of NULL node checking takes place. So complete binary tree is the better one since the property of complete binary tree is maintained even after operations like additions and deletions are done on it
77.
Reason : As the linked list nodes do not have any index and hence they must be accessed in linear order always. Also they are stored in discrete locations and not in contiguous memory locations.
78.
Reason : As this is the most suitable option when compared to the other options. Also option c, e are wrong.
79.
Reason : As both the operators [à and (*). ] are used to access the members of the structure through pointers. All the other options have the syntax errors.
80.
Reason : As the Stack behaves in Last In First Out manner.

71.
Reason : Because the rules for traversing the binary tree in In-order are:
i.            Traverse the left sub tree in In-order
ii.     Traverse the root
iii.    Traverse the right sub tree in In-order
72.
Reason : Because the rules for traversing the binary tree in Pre-order are:
i.            Traverse the root
ii.     Traverse the left sub tree in Pre-order
iii.    Traverse the right sub tree in Pre-order
73.
Reason : Because the rules for traversing the binary tree in Post-order are:
i.            Traverse the left sub tree in Post-order
ii.     Traverse the right sub tree in Post-order
iii.    Traverse the root
74.
Reason : In general there are 2n-1 nodes in a full binary tree.
By the method of elimination: Full binary trees contain odd number of nodes. So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13 nodes you can form a complete binary tree but not a full binary tree. So the correct answer is 15.
75.
Reason : At location  6
 1 2 3 - - 4 - - 5 Root 1 LC1 2 RC1 3 LC2 4 RC2 5 LC3 6 RC3 7 LC4 8 RC4 9
where LCn means Left Child of node ‘n’ and RCn means Right Child  of node ‘n’. Top row represents the node values and bottom row represents the positions.
76.
Reason : Complete Binary Tree.
By the method of elimination: Full binary tree loses its nature when operations of insertions and deletions are done. For incomplete binary trees, extra storage is required and overhead of NULL node checking takes place. So complete binary tree is the better one since the property of complete binary tree is maintained even after operations like additions and deletions are done on it
77.
Reason : As the linked list nodes do not have any index and hence they must be accessed in linear order always. Also they are stored in discrete locations and not in contiguous memory locations.
78.
Reason : As this is the most suitable option when compared to the other options. Also option c, e are wrong.
79.
Reason : As both the operators [à and (*). ] are used to access the members of the structure through pointers. All the other options have the syntax errors.
80.