CS301 Final Term Past Papers Set 3 by VUBuddy

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

Answer: (Page 488)

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

These three algorithms fall under ‗divide and conquer category‘.

Q2. difference between call by value n call by reference (2 marks)

Answer: (Page 202) 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.

Q3. heap and two types of heap(3)

Answer: (Page 333 ) 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.

Q4. Answer:-

Height = 5 · Nodes = 2^h = 2^5 =32 · Sum of Nodes = N-(h+1)= 32-(5+1) = 32-6 = 26

Q5. 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.

(Marks: 5)

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

Q6. Write one example of hashing?

Answer: (page 459) Hashing can be used to store the data. Suppose we have a list of fruits. The names of Fruits are in string. The key is the name of the fruit. We will pass it to the hash Function to get the hash key. HashCode ("apple") = 5 We pass it to the string ―apple‖. Resultantly, it returns a number 5.

Q7. Answer:- rep

Q8. How do we carry out degeneration of Complete Binary Tree?

Answer: Degeneration of the (original) binary tree is mainly reflected by degeneration of the internal infix trees and lessby degeneration of the external height of the PPbin tree.

Q9. What is a skip List?

Answer: (Page 446) A skip list for a set S of distinct (key, element) items is a series of lists S0, S1 , … , Sh such that Each list Si contains the special keys +∞ and -∞

• List S0 contains the keys of S in non-decreasing order
• Each list is a subsequence of the previous one, i.e., S0 ⊇ S1 ⊇ … ⊇ Sh
• List Sh contains only the two special keys

Q10. How we can generate a maze with the help of union

Answer: (Page 424) How can we generate maze? The algorithm is as follows:

•  Randomly remove walls until the entrance and exit cells are in the same set.
•  Removal of the wall is the same as doing a union operation.
•  Do not remove a randomly chosen wall if the cells it separates are already I the same set.

Q11. Following 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

Answer: Repeat

Q12. ( Marks: 10 )

Write down the C++ code to implement insertion sort algorithm.

Answer: (Page 483) Following is the code of the insertion sort in C++. void insertionSort(int *arr, int N)

int pos, count, val; for(count=1; count < N; count++)

val = arr[count]; for(pos=count-1; pos >= 0; pos--) if (arr[pos] > val) arr[pos+1]=arr[pos]; else break; arr[pos+1] = val;