CS301 Current Final Term Paper Fall 2013 File 1

Total Q = 52, Total Marks = 80  
60% MCQs are from past papers. Total mcqs 40.
Subjective(total 12 Qtnz) = 5+5+5+5+3+3+3+3+2+2+2+2 = 40
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 marks
Q2:  Suppose we have the following representation for a complete Binary Search Tree,

	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

Find

1. Left child
2. Right child
3. Parent node

of the node H and I?       5 marks
Q3:  “5, 7, 8, 9” implement these hash elements. Use array of size 13 and solve this collision by using hash code where h = key%14?     5 marks
Q4:  perform preorder and inorder by using the tree (implement manually not using any programming code).?     5 marks
Q5:  "For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply."     3 marks
Justify why?
Q6:          10
                / \
             6     9
            /  \   /  \
           2   5 7   8
Delete the root and show the resultant heap?   3 marks

Q7:  “2, 6, 5, 4, 7, 9, 8” show BST as tall height as possible?   3 marks
Q8:  Binary Search is much faster algorithm justify?   3 marks
Q9:  Show array of the given heap?   2 marks
                  16
                 /    \
             10      13
          /    \        /    \
       7       9    5       6
     /              /   \ 
  1              2     3
Q10:  Name two operations of link list?   2 marks
Q11:  Write two characteristics of skip list?   2 marks
Q12:  How can we apply union operation on two different set?   2 marks