## Trees

 Question 1
The number of unused pointers in a complete binary tree of depth 5 is:
 A 4 B 8 C 16 D 32
Data-Structures       Trees       Nielit Scientist-B IT 4-12-2016
Question 1 Explanation:
It gives ambitious answer. It may give 32 if root start from 0. It start from means 16.
 Question 2
In a complete k-array, every internal node has exactly k children. The number of levels in such a tree with n internal nodes is
 A nk B (n-1)k+1 C n(k-1)+1 D n(k-1)
Data-Structures       Trees       Nielit Scientist-B CS 22-07-2017
Question 2 Explanation:
Total nodes = nk+1 (1 for root)
Leaves = total nodes - internal nodes
= nk+1-n
= n(k-1)+1
 Question 3

In a ternary tree, the number of internal nodes of degree 1,2 and 3 is 4,3 and 3 respectively. The number of leaf nodes in the ternary tree is

 A 11 B 12 C 10 D 9
Data-Structures       Trees       UGC-NET DEC Paper-2
Question 3 Explanation:
Number of internal nodes= 4+3+3 = 10
Number of leaf nodes = Sum of degrees of all internal nodes - number of internal nodes +1
= (4*1 + 3*2 + 3*3 ) - 10 + 1
= 19 - 10 + 1
= 10
Formula: nd - n + 1 where n is number of nodes and d is degree of the tree.
 Question 4
The following figure is a____ tree after zig-zig rotations A Heap B Bubble C Splay D Binary
Data-Structures       Trees       KVS DEC-2013
Question 4 Explanation:
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.
 Question 5
A complete n-ary tree is one in which every node has 0 or n children. If there are x internal nodes in a complete n-ary tree, the number of leaves is
 A (n-1)x+1 B (n-1)x-1 C nx+1 D nx-1
Data-Structures       Trees       KVS 30-12-2018 Part B
Question 5 Explanation:
Consider binary tree with two children.
Then n value is 2 and internal node is 1 then the number of leaves are (2-1)1+1=2 leaves.
 Question 6
Given a tree with k nodes, the sum of degrees of all nodes is
 A 2k-1 B 2*(k-1) C 2k+1 D 2((k+1)
Data-Structures       Trees       KVS 30-12-2018 Part B
Question 6 Explanation:
The number of edges in tree with “k” nodes are K-1..
According to the handshaking lemma , the sum of the degree is 2* number of edges So the option B is suitable one.
 Question 7
Let us assume that you construct ordered tree to represent the compound ​ proposition (~ (p ∧ q)) ↔ (~ p ∨ ~ q) Then, the prefix expression and post-fix​ expression determined using this ordered tree are given as ____ and _____ respectively.
 A ↔~∧pq∨ ~ ~ pq, pq∧~p~q~∨↔ B ↔~∧pq∨ ~ p~q, pq∧~p~q~∨↔ C ↔~∧pq∨ ~ ~ pq, pq∧~p~~q∨↔ D ↔~∧pq∨ ~ p~ q, pq∧~p~ ~q∨↔
Algorithms       Trees       UGC NET CS 2016 Aug- paper-2
Question 7 Explanation:
Step-1: Given compound proposition is
(~(p ∧ q))↔(~ p ∨ ~ q)
It is clearly specifying that
↔ is a root
(~(p ∧ q)) is left subtree
(~p ∨ ~q) is right subtree.
Step-2: Finally the tree is looks like Step-3: Prefix operation traverse through Root,left and Right ↔~∧pq∨ ~ p~q Step-4: Postfix operation traverse through Left,Right and Root.
pq∧~p~q~∨↔
 Question 8
In what tree, for every node the height of its left subtree and right subtree differ at least by one :
 A Binary search tree B AVL - tree C Threaded binary tree D Complete tree
Data-Structures       Trees       UGC NET CS 2005 Dec-Paper-2
Question 8 Explanation:
Threaded binary tree:​ A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.
1. Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right).
2. Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right).
 Question 9
Which of the following statement is false ?
 A Every tree is a bipartite graph B A tree contains a cycle C A tree with n nodes contains n-1 edges D A tree is a connected graph
Data-Structures       Trees       UGC NET CS 2005 june-paper-2
Question 9 Explanation:
A tree never contains cycles. If it contains a cycle, we are calling as graph but not tree.
Note: Minimum 1 edge and maximum n-1 edges.
 Question 10
Preorder is also known as :
 A Depth first order B Breadth first order C Topological order D Linear order
Data-Structures       Trees       UGC NET CS 2006 June-Paper-2
Question 10 Explanation:
Preorder is also known as topological order. Every preorder can be given a topology, and indeed, every preorder on a set is in one-to-one correspondence with an topology on that set.
 Question 11
Which of the following statement is false ?
 A Every tree is a bipartite graph B A tree contains a cycle C A tree with n nodes contains (n-1) edges D A tree is connected graph
Data-Structures       Trees       UGC NET CS 2006 June-Paper-2
Question 11 Explanation:
A tree never contains cycles. If it contains a cycle, we are calling as graph but not tree.
Note: Minimum 1 edge and maximum n-1 edges.
 Question 12
In a ternary tree, the number of internal nodes of degree 1,2 and 3 is 4,3 and 3 respectively. The number of leaf nodes in the ternary tree is
 A 11 B 12 C 10 D 9
Algorithms       Trees       UGC NET CS 2018-DEC Paper-2
Question 12 Explanation:
Number of internal nodes= 4+3+3= 10
Number of leaf nodes = Sum of degrees of all internal nodes - number of internal nodes +1
= (4*1 + 3*2 + 3*3 )-10 +1
= 19- 10 +1=10
Formula​ : nd-n +1 where ​ n ​ is number of nodes and d ​ is degree of the tree.
 Question 13
​ Consider the following minimax game tree search What will be the value propagated at the root ?
 A 6 B 3 C 5 D 4
Data-Structures       Trees       UGC NET CS 2018-DEC Paper-2
Question 13 Explanation: Question 14
A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be :
 A 30 B 33 C 45 D None of the above
Data-Structures       Trees       UGC NET CS 2018 JUNE Paper-2
Question 14 Explanation:
L = I(n-1)+ 1
Where, L= Number of leaf nodes
n= N-ary tree
I = Number of intermediate nodes
Now, L =8(5-1)+1
L =8(4)+1
L =33
Total Number of nodes in a tree = Number of Intermediate nodes+Number of Leaf nodes
Total Number of nodes in a tree = 8+33
Total Number of nodes in a tree = 41
 Question 15
Which of the following does not define a tree ?
 A A tree is a connected acyclic graph. B A tree is a connected graph with n-1 edges where ‘n’ is the number of vertices in the graph. C A tree is an acyclic graph with n-1 edges where ‘n’ is the number of vertices in the graph. D A tree is a graph with no cycles.
Data-Structures       Trees       UGC NET CS 2008-june-Paper-2
Question 15 Explanation:
→ An undirected graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected. An undirected graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints.
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas "A tree is a graph with no cycles." is not always correct as it can be bipartite.
Hence D does not define a tree.
 Question 16
Consider a rooted tree in which every node has at least three children. What is the minimum number of nodes at level i (i > 0) of the tree ? Assume that the root is at level 0 :
 A 3i B 3i C 3 D 3i + 1
Data-Structures       Trees       UGC NET CS 2007-Dec-Paper-2
Question 16 Explanation:
From the given question,
Given condition is every node has at least three children.
the root node is present at level 0, here only one is present(30)
at level 1, three nodes are present based upon the condition( 31 nodes)
at level 2, nine nodes will be present (32 nodes ) [Each node has at least three children]
and so on the at level "i", 3i nodes will be present.
There are 16 questions to complete.