# Test: Trees- 2

Test Description

## 15 Questions MCQ Test Question Bank for GATE Computer Science Engineering | Test: Trees- 2

Test: Trees- 2 for Computer Science Engineering (CSE) 2022 is part of Question Bank for GATE Computer Science Engineering preparation. The Test: Trees- 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Trees- 2 MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Trees- 2 below.
Solutions of Test: Trees- 2 questions in English are available as part of our Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) & Test: Trees- 2 solutions in Hindi for Question Bank for GATE Computer Science Engineering course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Trees- 2 | 15 questions in 45 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Trees- 2 - Question 1

### Level order traversal of a rooted tree can be done by starting from the root and performing

Detailed Solution for Test: Trees- 2 - Question 1

Level order traversal of rooted tree can be done by starting from root and visiting all node at k level before visiting any node at k + 1 level, which is nothing but breadth first search.

Test: Trees- 2 - Question 2

### The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a maxHeap. The resultant maxHeap is

Detailed Solution for Test: Trees- 2 - Question 2

Input sequence 32,15, 20, 30,12, 25,16 If i is the root then A [i] > A [2i] for 1 < i < n/2 and A [i] > A [2i + 1] for 1 < i < n/2 where 2i is the left of i and 2i + 1 is the right of i of a max heap.

Test: Trees- 2 - Question 3

### Which one of the following binary trees has its inorder and preorder traversals as BCAD and ABCD, respectively?

Detailed Solution for Test: Trees- 2 - Question 3

Inorder traversal is BCAD and preorder traversal is ABCD.

Test: Trees- 2 - Question 4

The numbers 1 , 2 .... n are inserted in a binary search tree in some order, In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be

Detailed Solution for Test: Trees- 2 - Question 4

Number 1 ,2 , 3, ....... n are inserted into BST in some order.

Since we know total nodes = n
So, Left (root) + 1 + p = n
Left (root) = n - p - 1
Left (root) = n - (p + 1)
So, root element will be = left element + 1
= n - (p + 1) + 1
= n - p - 1 + 1
= n - p

Test: Trees- 2 - Question 5

A binary search tree contains the numbers 1,2, 3, 4, 5, 6, 7, 8, When the tree is traversed in preorder and the values in each node printed out, the sequence of values obtained is 5, 3,1, 2, 4, 6, 8, 7. If the tree is traversed in postorder, the sequence obtained would be

Detailed Solution for Test: Trees- 2 - Question 5

Test: Trees- 2 - Question 6

How many distinct binary search trees can be created out of 4 distinct keys?

Detailed Solution for Test: Trees- 2 - Question 6

Total number of distinct binary search tree with n nodes (key)

Test: Trees- 2 - Question 7

In a complete k-ary, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is

Detailed Solution for Test: Trees- 2 - Question 7

In a complete-k-ary tree. If every internal node has exacity k children then (k - 1) key contains no leaves, if there are n internal nodes, then number of leaves is n(k- 1) + 1.

Test: Trees- 2 - Question 8

In a binary max heap containing.n numbers, the smallest element can be found in time

Detailed Solution for Test: Trees- 2 - Question 8

MAX Heap used to identity max element in O(1) time for to identity min element require O(n), to apply the linear search.

Test: Trees- 2 - Question 9

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

Detailed Solution for Test: Trees- 2 - Question 9

Let number of vertices in binary tree = n Number of edges = n - 1
So, n - 1 = 1 x 5 + 2 x 10
n - 1 = 5 + 20
n = 26
Num ber of leaf nodes = 26 - 5 - 10 = 11

Test: Trees- 2 - Question 10

The inorder and preorder traversal of a binary tree are “dbeafcg" and “abdecfg’’ respectively. The postorder traversal of the binary tree is

Detailed Solution for Test: Trees- 2 - Question 10

The in order traversal sequence is dbeafcg and the pre order traversal sequence is abdecfg.
So the tree is

In the post order traversal the sequence is debfgca.

Test: Trees- 2 - Question 11

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is

Detailed Solution for Test: Trees- 2 - Question 11

After inserting an element at leaf in max heap we perform binary search on the path from the new leaf to the root to find the correct position for the newly inserted element. Comparisions will take θ(loglogn) but time will be θ(logn) because of swap operations.

Test: Trees- 2 - Question 12

How many distinct BSTs can be constructed with 3 distinct keys?

Detailed Solution for Test: Trees- 2 - Question 12

For distinct BST we apply this formula

n = 3 here so C(6, 3) = 20 and 20/4 = 5

Test: Trees- 2 - Question 13

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

Detailed Solution for Test: Trees- 2 - Question 13

Maximum height of any AVL-tree with 7.

(There may be different way to draw AVL with 7 nodes).

Test: Trees- 2 - Question 14

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

Detailed Solution for Test: Trees- 2 - Question 14

Test: Trees- 2 - Question 15

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

Detailed Solution for Test: Trees- 2 - Question 15

## Question Bank for GATE Computer Science Engineering

61 videos|7 docs|102 tests
 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code
Information about Test: Trees- 2 Page
In this test you can find the Exam questions for Test: Trees- 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Trees- 2, EduRev gives you an ample number of Online tests for practice

## Question Bank for GATE Computer Science Engineering

61 videos|7 docs|102 tests