cs301 MIDTERM EXAMINATION 2011 (June)


MIDTERM EXAMINATION 2011 (MAY)


Q:1 What is complete binary tree? Answer: rep

Q:2 How single left rotation is performed in AVL tree? Answer: rep

What is binary tree breif it? Answer:- rep

Why queue is linear data structure. Answer:- rep

Q: Define const keyword, reference variable , Dangling reference
Answer: rep

Q:3 Describe the following
(i) Height of tree
Answer: rep

Q.21A: - Similarity between AVL and Binary Search Tree? Answer:- rep

Q.21B: - How AVL is different from Binary Search Tree?
A binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are
called left and right. One common use of binary trees is binary search trees; another is binary heaps.

While an AVL tree is a self-balancing binary search tree.
In an AVL tree the heights of the two child sub-trees of any node differ by at most one, therefore it is also called height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations.



Q.22: - What the maximum no of comparisons we have to perform during insertion in BST? Answer:- ( Page 139 )
If we have a complete binary tree with n numbers of nodes, the depth d of the tree can be found by the following
equation:
d=log2 (n + 1) – 1
If the tree is complete binary or near-to-complete, we need log2(n) number of comparison. Whereas in a
linked list, the comparisons required could be a maximum of n.

           

No comments:

Post a Comment