Question 1 |

The minimum height of an AVL tree with n nodes is

\text{Ceil } (\log_2(n+1)) | |

1.44\ \log_2n | |

\text{Floor } (\log_2(n+1)) | |

1.64\ \log_2n |

Question 1 Explanation:

Question 2 |

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.

\Theta (\log n ) | |

\Theta (\log n +k) | |

\Theta (k \log n ) | |

\Theta (n \log k ) |

Question 2 Explanation:

Question 3 |

What is the worst case time complexity of inserting n^2 elements into an AVL-tree with n elements initially?

\Theta (n^4) | |

\Theta (n^2) | |

\Theta (n^2 \log n) | |

\Theta (n^3) |

Question 3 Explanation:

Question 4 |

Access time of the symbolic table will be logarithmic if it is implemented by

Linear list | |

Search tree | |

Hash table | |

Self organization list |

Question 4 Explanation:

Question 5 |

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^{a}log^{b}n+m^{c}log^{d}n), the value of a + 10b + 100c + 1000d is _______.

100 | |

110 | |

10 | |

1010 |

Question 5 Explanation:

Question 6 |

The number of rotations required to insert a sequence of elements 9, 6, 5, 8, 7, 10 into an empty AVL tree is?

0 | |

1 | |

2 | |

3 |

Question 6 Explanation:

Question 7 |

The worst case running time to search for an element in a balanced binary search tree with n2^{n} elements is

\Theta (n log n) | |

\Theta n2^{n} | |

\Theta (n) | |

\Theta (log n) |

Question 7 Explanation:

Question 8 |

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.

2 | |

3 | |

4 | |

5 |

Question 8 Explanation:

Question 9 |

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is

\Theta (n) | |

\Theta (nlog n) | |

\Theta (n^{2}) | |

\Theta (n^{2}log n) |

Question 9 Explanation:

Question 10 |

A weight-balanced tree is a binary tree in which for each node, the number of
nodes in the let sub tree is at least half and at most twice the number of nodes in
the right sub tree. The maximum possible height (number of nodes on the path
from the root to the furthest leaf) of such a tree on n nodes is best described by
which of the following ?

log_{2}n | |

log_{4/3}n | |

log_{3}n | |

log_{3/2}n |

Question 10 Explanation:

There are 10 questions to complete.