CS301 Midterm Subjective by Talha Sajid

Q1. 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."

Q2. 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 while tree 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.

Q3. name of two divide and conquer algorithm (2 marks)

•  Merge Sort
•  Quick Sort
•  Heap Sort

These three algorithms fall under ‗divide and conquer category.

Q4. difference between call by value n call by reference?

In case of call by value, a copy of object is made and placed at the time of function calling in the activation record. By using the references, we are not making the copy but send the address of the variable that function can use the original value.

5. describe the following · (i) Height of tree · (ii) Balance of Node · (i) Height of tree

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

(ii) Balance of Node

Answer: 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.

Q6. heap and two types of heap?

Answer: Heap is a data structure of big use and benefit. It is used in priority queue. ―The definition of heap is that it is a complete binary tree that conforms to the heap order‖. Here heap order means the min and max heap. Max heap: In max heap, each node has a value greater than the value of its left and right child nodes. Moreover, the value of the root will be largest and will become lesser at downward levels. Min heap: in a (min) heap for every node X, the key in the parent is smaller than (or equal to) the key in X. This means that the value in the parent node is less than the value on its children nodes.

Q7. 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”.

Q8. height of a tree is 5 find sum of heights (2)?

Height = 5 Nodes = 2^h = 2^5 =32

Sum of Nodes = N-(h+1)= 32-(5+1) = 32-6 = 26

9. Here is an array with exactly 15 elements:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.

Suppose that we are doing a binary search for an element. Indicate any elements that will

be found by examining two or fewer numbers from the array.

Answer: If there is an array of 15 elements, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15} it wants to know which elements can be discovered by examining two or fewer elements. I want assume the divide and conquer aspect of a binary search, so that leads me to think these elements will be found 1, 2, 14, 15, 7, 3

rather; 1, 2, 3, 4, 6, 8, 14, 15

1 and 15 for heads and tails

2, and 14 for next elements (following or preceding)

1/2 of 15 is either 6, or 8, from 7.5

and 1/2 of 6 = 3

1/28=4

Q10. What is different between binary tree and AVL tree?

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

•  Height of the left and right subtrees may differ by at most 1.
•  Height of an empty tree is defined to be (–1).