Cs301- current midterm paper-1

Cs301- current midterm paper-1(NOV 2011)

Q:1 What is complete binary tree? Answer:

"A complete binary tree is a binary tree with the additional property that every node must have exactly two

children if an internal node, and zero children if a leaf node."

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

This rotation is almost similar to the single right rotation. We start from tree node k1. k1 is the root whilet ree

node k2 is its right child. Due to the left rotation, the right child k2 of the root k1 will become the root. The k1 will go down to the left child of k2.

Q:3 describe the following

(i) Height of tree

(ii)  Balance of Node

(i) Height of tree

Answer: (Page 209)

The height of a binary tree is the maximum level of its leaves (also called the depth).

(ii) Balance of Node

Answer: (page 215)

The balance of a node in a binary search tree is defined as the height of its left subtree minus height of its right

subtree. In other words, at a particular node, the difference in heights of its left and right subtree gives the balance of the node.

Cs301- current midterm paper-2(NOV 2011)

Q1 what is binary tree brief it? Answer:-

“A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first

subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right sub-trees”.

Q2.what is different between binary tree and AVL tree

Answer:- (Page 212)

An AVL tree is identical to a BST, barring the following possible differences:

v  Height of the left and right subtrees may differ by at most 1.

v  Height of an empty tree is defined to be (–1).

Why queue is linear data structure. Answer:-(Page 87)

A queue is a linear data structure into which items can only be inserted at one end and removed from the other.

2

In contrast to the stack, which is a LIFO (Last In First Out) structure, a queue is a FIFO (First In First Out)

structure.

How we can delete a node with two Childs in a binary search tree using its right sub tree. Answer:- Page 263

The node to be deleted has either left child (subtree) or right child (subtree).In this case we bypass the node in

such a way that we find the inorder successor of this node and then link the parent of the node to be deleted to this successor node. Thus the node was deleted.

define const keyword, reference variable, Dangling reference

Answer: (Page 198) Const keyword

The const keyword is used for something to be constant. The actual meanings depend on where it occurs but it

generally means something is to held constant. There can be constant functions, constant variables or parameters etc.

Reference variable

The references are pointers internally, actually they are constant pointers. You cannot perform any kind of

arithmetic manipulation with references that you normally do with pointers.

Dangling reference

The pointer of the object (when object has already been deallocated or released) is called dangling pointer.