For a perfect binary tree of height 4. What will be the sum of heights of nodes?

# Vukwl- Virtual Education Solution

31 302726

For a perfect binary tree of height h, having N nodes, the sum of heights of nodes is _____________.

N – (h – 1)

**N – (h + 1)**

N – 1

N – 1 + h

If we want to find median of 50 elements, then after applying buildHeap method, how many times deleteMin method will be called ?

5

**25**

35

50

Which of the following heap method increase the value of key at position ‘p’ by the amount ‘delta’?

**increaseKey(p,delta)**

decreaseKey(p,delta)

preculateDown(p,delta)

remove(p,delta)

The main reason of using heap in priority queue is

**improve performance**

code is readable

less code

heap can't be used in priority queues

The total number of nodes on 10th level of a perfect binary tree are :

256

512

1024

**Can't be determined**

Which property of equivalence relation is satisfied if we say: Ahmad R(is related to) Ahmad

Reflexivity

**Symmetry**

Transitivity

All of the above

Which of the following heap method lowers the value of key at position ‘p’ by the amount ‘delta’?

**increaseKey(p,delta)**

decreaseKey(p,delta)

preculateDown(p,delta)

remove(p,delta)

We can build a heap in _____ time.

**Linear**

Exponential

Polynomial

None of the given options

we can build a heap in linear time using n calls of percolate_down()

If a tree has 50 nodes, then the total edges/links in the tree will be :

55

51

50

**49 N-1= 49**

Questions of 2 marks:

In the array representation of union what represents -1?

For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply." Justify why?

If we want to delete the node from BST which has left and right child then which rotation is applied ?

Collision in hashing definition?

In the array representation of union what represents -1?

For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply." Justify why?

If we want to delete the node from BST which has left and right child then which rotation is applied ?

Collision in hashing definition?

Question of 3 marks:

Algorithm union by weight?

One tree is given question is it heap or not if it is heap then write its type?

Which data structure is best for priority queue?

Questions of 5 marks:

Some numbers are given and using those make BST?

One array is given we require to sort it using bubble sort and write only 2 iterations?

One tree is given which not the heap but after minimum changes it becomes max heap make it?

Algorithm union by weight?

One tree is given question is it heap or not if it is heap then write its type?

Which data structure is best for priority queue?

Questions of 5 marks:

Some numbers are given and using those make BST?

One array is given we require to sort it using bubble sort and write only 2 iterations?

One tree is given which not the heap but after minimum changes it becomes max heap make it?

Another Paper:

Question 1: Write min heap after removal of root. 3 marks.

1 3 2 5 4 8 9 10 7

Question 2: Write In order and preorder traversal. 3 marks

Question 3: show steps of merge sort. 5 marks.

11 12 13 21 22 23 31 33 41 42

Question 4: correct the following code.

int isPresent(int *arr, int val, int N)

{ int low = 0;

int high = N - 1;

int mid;

while ( low >= high )

{ mid = ( low-high )/2;

if (arr[mid] == val)

return 1; // found!

else if (arr[mid] > val)

low = mid - 1;

else

high = mid + 1;

}

return 0; // not found

}

Question 5: Correct the code.5 marks

/* The inorder routine for threaded binary tree */

TreeNode* nextInorder(TreeNode* p){

if(p->RTH == thread)

return(p->R);

else {

p = p->R;

while(p->LTH == child)

p = p->L;

return p;

}

}

Question 6:

for telephone directory which is best linear or non-linear array. 2 marks

Question 1: Write min heap after removal of root. 3 marks.

1 3 2 5 4 8 9 10 7

Question 2: Write In order and preorder traversal. 3 marks

Question 3: show steps of merge sort. 5 marks.

11 12 13 21 22 23 31 33 41 42

Question 4: correct the following code.

int isPresent(int *arr, int val, int N)

{ int low = 0;

int high = N - 1;

int mid;

while ( low >= high )

{ mid = ( low-high )/2;

if (arr[mid] == val)

return 1; // found!

else if (arr[mid] > val)

low = mid - 1;

else

high = mid + 1;

}

return 0; // not found

}

Question 5: Correct the code.5 marks

/* The inorder routine for threaded binary tree */

TreeNode* nextInorder(TreeNode* p){

if(p->RTH == thread)

return(p->R);

else {

p = p->R;

while(p->LTH == child)

p = p->L;

return p;

}

}

Question 6:

for telephone directory which is best linear or non-linear array. 2 marks

# Vukwl- Virtual Education Solution

Q 41: Where is hashing suitable? 2 Marks

Q.42 When Hashing is not Suitable? 2 Marks

Q.45 How many parameters used in following operation? write their names,

0. Find,

1. Add

3. Remove 3 Marks

Q.46 Forgot

Q.49 Union by size tree formation, Assignment no4 was asked 5 Marks

Q.50 Code for Union and find operation in disjoints sets. 5Marks

Q.51 A function Hash(x) = (x*2)/ tablesize and is given index from 0 to 11, to find out the contents of tables of values in order 11, 29, 36, 22, 27 5Marks

Shared by Umair Saulat

Q.42 When Hashing is not Suitable? 2 Marks

Q.45 How many parameters used in following operation? write their names,

0. Find,

1. Add

3. Remove 3 Marks

Q.46 Forgot

Q.49 Union by size tree formation, Assignment no4 was asked 5 Marks

Q.50 Code for Union and find operation in disjoints sets. 5Marks

Q.51 A function Hash(x) = (x*2)/ tablesize and is given index from 0 to 11, to find out the contents of tables of values in order 11, 29, 36, 22, 27 5Marks

Shared by Umair Saulat

Total Number 80

Time 120 minutes

Total Question 52

40 MCQs from Past Papers

2 four-long questions

3 four-long questions

5 four-long questions

Q1. How we can implement Table ADT using Linked List (2)

Q2. What is hashing? (2)

Q3. Describe the conditions for second case of deletion in AVL Trees. (2)

Q4. What is an Equivalent relation? Give any two examples. (2)

Q1. Write down the parameter name of the following:- (3)

1. Delete

2. Insert

3. Find

Q2. Where Inorder Predecessor of a non leaf node is is present in a Binary Search Tree? :- (3)

Q3. How we can search an element in Skip List. (3)

Q4. Convert the given infix form to postfix form. Y-Z*X-Q^P-(3)

Q1. 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.? (5)

Q2. Here is an array of ten integers:

5 3 8 9 1 7 0 2 6 4

The array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest)? (5)

Q3. Consider the following array as input

Time 120 minutes

Total Question 52

40 MCQs from Past Papers

2 four-long questions

3 four-long questions

5 four-long questions

Q1. How we can implement Table ADT using Linked List (2)

Q2. What is hashing? (2)

Q3. Describe the conditions for second case of deletion in AVL Trees. (2)

Q4. What is an Equivalent relation? Give any two examples. (2)

Q1. Write down the parameter name of the following:- (3)

1. Delete

2. Insert

3. Find

Q2. Where Inorder Predecessor of a non leaf node is is present in a Binary Search Tree? :- (3)

Q3. How we can search an element in Skip List. (3)

Q4. Convert the given infix form to postfix form. Y-Z*X-Q^P-(3)

Q1. 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.? (5)

Q2. Here is an array of ten integers:

5 3 8 9 1 7 0 2 6 4

The array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest)? (5)

Q3. Consider the following array as input

13 | 4 | 6 | 8 | 9 | 7 | 10 | 15 |

Prove that it is a heap and also explain what type of heap it is.? Draw the final NOT for all?

Q4. Draw the following sequence of union commands on the set of elements {1,2,3,4, 5}:

union(4,2)

union(3,1)

union(5,4)

union(5,3)

Show the result when the unions are performed. We need only Final results of union NOT for all.?

Q4. Draw the following sequence of union commands on the set of elements {1,2,3,4, 5}:

union(4,2)

union(3,1)

union(5,4)

union(5,3)

Show the result when the unions are performed. We need only Final results of union NOT for all.?