Qualcomm Trees Quiz-1

Question 1

Time: 00:00:00

Level of a node is the distance from root to that node. For example, level of the root is 1 and levels of the left and right children of the root are 2. The maximum number of nodes on level i of a binary tree is

In the following answers, the operator '^' indicates power.

2^(i-1)

2^i

2^(i+1)

2^[(i+1)/2]

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 2

Time: 00:00:00

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

6

3

4

5

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 3

Time: 00:00:00

Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?

9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95

95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 4

Time: 00:00:00

In delete operation of BST, we need in order successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about in order successor needed in delete operation?

Inorder Successor is always a leaf node

Inorder successor is always either a leaf node or a node with empty left child

Inorder successor may be an ancestor of the node

Inorder successor is always either a leaf node or a node with empty right child

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 5

Time: 00:00:00

Consider the following Binary Search Tree

10
/ \
5 20
/ / \
4 15 30
/
11
If we randomly search one of the keys present in above BST, what would be the expected number of comparisons?

2.75

2.25

2.57

3.25

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 6

Time: 00:00:00

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

II and III only

I and III only

III and IV only

III only

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 7

Time: 00:00:00

Which of the following is AVL Tree?
A
100
/ \
50 200
/ \
10 300

B
100
/ \
50 200
/ / \
10 150 300
/
5

C
100
/ \
50 200
/ \ / \
10 60 150 300
/ \ \
5 180 400

Only A

A and C

A, B and C

Only B

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 8

Time: 00:00:00

Consider the following left-rotate and right-rotate functions commonly used in self-adjusting BSTs
T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on the right side)
y x
/ \ Right Rotation / \
x T3 – - – - – - – > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
Which of the following is tightest upper bound for left-rotate and right-rotate operations.

O(1)

O(Logn)

O(LogLogn)

O(n)

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Question 9

Time: 00:00:00

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. lf u is visited before v during the breadth-first traversal, which of the following statements is correct?

d(r, u) < d (r, v)

d(r, u) > d(r, v)

d(r, u) <= d (r, v)

None of the above

Good Job!

Oops!