Data Structure GATE Practice Questions are explained in this tutorial.
Data Structure is one of the core subject of Computer Science. Data Structure is an important subject for programming. Computer Science Engineering Student study this subject in third semester.
Data structure is also a scoring subject for GATE exam. Problems based on Tree, Binary Search Tree, Hashing, Stack , Sorting, Graph from data structure are generally asked in GATE exam.
In this tutorial we have provided some Important question from Data Structure on GATE exam pattern.
Students or GATE Aspirants are suggested to attempt these questions.
Table of Contents
Data Structure GATE Practice Questions
Data Structure GATE Practice Questions are explained in this section.
Let’s Practice these questions
Q1. Consider the following tree
If the post-order traversal gives ab-cd*+ then the label of the nodes 1, 2, 3,…..will be:
(a) +, -, *, a, b, c, d (b) a, -, b, +, c, *, d
(c) a, b, c, d, -, *, + (d) -, a, b, +, *, c, d
Solution: Option (a)
Q2. Consider the following tree
If this tree is used for sorting, then a new number 8 should be placed as:
(a) left child of the node labeled 30
(b) right child of the node labeled 5
(c) right child of the node labeled 30
(d) left child of the node labeled 10
Solution: Option (d)
Q3. How many of possible ordered trees with 3 nodes A, B, C will be formed ?
(a) 16 (b) 12
(c) 6 (d) 10
Solution: Option (b)
Explanation:
Tree maybe of depth 2 or 1. If depth is 2, we have 6 possible trees. This is because one of the 3 nodes A, B, C may be the root and the next level may be one of the remaining 2 nodes.
If the depth is 1, the root maybe one of the 3 nodes A, B, C. Corresponding to a root, say A, 2 trees are possible as this.
This gives us 6 more possibilities.
Q 4. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves.
(a) maximum 19 nodes
(b) has exactly 19 nodes
(c) has exactly 17 nodes
(d) cannot have more than 17 nodes
Solution: Option (b)
Explanation:
The configuration of 10 leaves can only be of the following way:
Any tree with n-leaves, for strict binary tree has (2n-1) nodes.
Q5. What is the depth of a Complete Binary Tree with ‘n’ nodes is (log is to the base 2) ?
(a) log (n+1) -1
(b) log (n)
(c) log (n-1) +1
(d) log (n) +1
Solution: Option (a)
Explanation:
Try with values n=3 and check.
Q6. The result of preorder traversal is same as
(a) depth-first order
(b) breadth-first search
(c) topological order
(d) linear order
Solution: Option (a)
Q7. Which of the following traversal approach lists the nodes of a binary search tree in ascending order?
(a) Post-order
(b) In-order
(c) Pre-order
(d) None of these
Solution: Option (b)
Q8. How many binary trees are with possible with 3 nodes ?
(a) 12 (b) 13
(c) 5 (d) 15
Solution: Option (c)
Explanation:
The answer will be catalan’s number = 2nCn
(n+1)
= 6C3 (3+1)
= 6C3 = 5
Q9. How many binary trees are possible with 4 nodes ?
(a) 12 (b) 13
(c) 14 (d) 15
Solution: Option (c)
Q10. If the prefix traverse order of a tree is: * + ab – cd is then find the equivalent postfix order of tree .
(a) ab + cd – * (b) ab cd + – *
(c) ab + cd * – (d) ab + – cd *
Solution: Option (a)
Explanation:
*+ab – cd
The evaluation of the prefix order is (a+b)*(c – d) The corresponding tree is
Post-fix order is ab+cd– *
Q11. If a binary tree has n leaf nodes. The no. of nodes of degree 2 in this tree is:
(a) log2n (b) n-1
(c) n (d) 2n
Solution: Option (b)
Check for small values of n.
Q12. The number of Binary Trees with 3 nodes which when traversed by post-order gives the sequence A, B, C is
(a) 3 (b) 9
(c) 7 (d) 5
Solution: Option (d)
The possible configurations are as shown in following figure
Q13. A 3-ary tree is a tree in which every internal node has exactly 3 children. What will be total number of leaf nodes in such a tree if there are 6 internal nodes.
(a) 10 (b) 23
(c) 17 (d) 13
Solution: Option (d)
Explanation:
The no. of leaf nodes for n-array tree is:
L= (n-1) I +1
where I= no. of internal nodes Therefore, n=3, I=6, L= 13
Q14. Which of the following need not be binary tree?
(a) Heap (b) B-Tree
(c) AVL- Tree (d) None of these
Solution: Option (b)
Q15. If maximum height of binary tree is n then how many number of nodes will be there ?
(a) 2n-1 (b) 2n-1-1
(c) 2n+1-1 (d) 2n+1
Solution: Option (c)
Explanation:
Check for small values for n, For n=2
We get Option (c) 22+1 – 1= 23-1 = 7
Q16. The Inorder and Preorder traversal of a binary tree is d b e a f c g and a b d e c f g respectively. Which among the following is the correct Post Order Traversal Sequence for this tree ?
(a) d e b f g c a (b) e d b g f c a
(c) e d b f g c a (d) d e f g b c a
Solution: Option (a)
Explanation
Post Order Traversal Follow the rule Left, Right, Node
Q17. Modes of a binary search tree have the values —1, 2, 3, 4, 5, 6, 7 and 8. Which among the following will be the preorder traversal sequence of this binary search tree ?
(a) 5 3 1 2 4 7 8 6 (b) 5 3 1 2 6 4 8 7
(c) 5 3 2 4 1 6 7 8 (d) 5 3 1 2 4 7 6 8
Solution: Option (d)
Explanation
As per Preorder traverse Node , Left Right.
Note – Link for Data Structure Notes for GATE exam is given below. These notes will be helpful for students in preparing Data Structure subject for GATE exam.
