# cs301 final paper feb3

FINAL TERM EXAMINATION

CS301 – Data Structure

FALL February 2012

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

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.