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.

        

No comments:

Post a Comment