Cs301 MIDTERM EXAMINATION 2011 (MAY)

MIDTERM EXAMINATION 2011 (MAY)

1. What is function of length () method in the Queue

Answer: (page 111)

In Queue length() method, has a single statement i.e.

return size ;

This method returns the size of the queue, reflecting the number of elements in the queue. It is not the size of the array used internally to store the elements of the queue.

2. Explain the two cases in which we apply double rotation in An Avl tree

Answer: (Page 229)

Sometimes a single rotation is not sufficient to balance an unbalanced tree.

The two cases are following:

1.   Insertion into the right subtree of the left child of X node (RL)

2.   Insertion into the left subtree of the right child of X node (LR)

3. How can we perform level-order traversal on a tree? Answer:- (For More detail and code see Page 161 )

We can print a binary tree level by level by employing recursive or non-recursive method.

The idea of a level-order traversal is to visit the root, then visit all nodes "1 level away" (depth 2) from the root (left to right), then all nodes "2 levels away" (depth 3) from the root, etc. For the example tree, the goal is to visit the nodes in the following order:

A level-order traversal requires using a queue (rather than a recursive algorithm, which implicitly uses a stack). A queue is a FIFO structure, which can make the level-order traversal easier.

4. How can the dangling reference problem be avoided? Answer:- ( Page 200 )

To avoid dangling reference, don’t return the reference of a local variable (transient) from a function.